Project Euler #44

Question

I'm having trouble optimizing my code for the exercise in Project Euler #44

Pentagonal numbers are generated by the formula, \$P_n=\frac{n(3n−1)}{2}\$. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that \$P_4 + P_7 = 22 + 70 = 92 = P_8\$. However, their difference, \$70 − 22 = 48\$, is not pentagonal.

Find the pair of pentagonal numbers, \$P_j\$ and \$P_k\$, for which their sum and difference are pentagonal and D = \$|P_k − P_j|\$ is minimised; what is the value of D?

Link to the exercise : https://projecteuler.net/problem=44

My code is working and it's running on my machine for about ~850 ms. I'm quite unhappy with that, so I would like to see some answer's concerning the performance of the code more specifically the parts where it runs slow and why is x function faster than y function, because I have quite a few questions here on Code Review about Project Euler. They all concern the performance which basically means I obviously haven't learned what the people answering me were recommending in order to be able to fix performance issues at my own, maybe links to some comparisons for example for vs foreach etc. and of course tips that will speed up my code.

The task itself is quite simple. We already have the formula that generates the pentagonal numbers all we need to do is find the inverse of that function so we can use to compare if a number is pentagonal, because storing them in an array and using LINQ.Contains() of course would be a lot more inefficient. Using Mathway (a site that help's you solve math equations step by step) to generate the inverse function of the current given I found (1 + Sqrt(1 + 24n)) / 6 that this is the inverse we are looking for. Implementing it like this :

    private static bool IsPentagonal(int inputN)
    {
        double result = (Math.Sqrt(24*inputN + 1) + 1)/6;
        int parseInt;
        return int.TryParse(result.ToString(), out parseInt);
    }

    private static int GetPentagonNumber(int inputN)
    {
        return inputN * (3 * inputN - 1) / 2;
    }

All that's left is just to put it all together in a for loop

    private static void Main()
    {
        bool found = false;
        int n = 2;
        Stopwatch sw = Stopwatch.StartNew();
        while (!found)
        {
            for (int i = n - 1; i > 0; i--)
            {
                int number1 = GetPentagonNumber(n);
                int number2 = GetPentagonNumber(n - i);
                if (IsPentagonal(number1 + number2) && IsPentagonal(number1 - number2))
                {
                    found = true;
                    Console.WriteLine(Math.Abs(GetPentagonNumber(n - i) - GetPentagonNumber(n)));
                    break;
                }
            }
            n++;
        }
        sw.Stop();
        Console.WriteLine("Time to calculate in milliseconds : {0}", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }

Initially I used 2 loop which resulted in 450k+ ms total time to calculate. I figured out that I can reduce that simply by using the current nTH number and just one for loop like shown above. It's pretty much self-explanatory pretty simple code still bad performance..

Answer 1

You could use a List<int> of dynamically precalculated pentagonals and/or HashSet<int> of them instead of the IsPentagonal method:

List<int> pentagonalsList = new List<int> { 0, 1 };
HashSet<int> pentagonalsHashSet = new HashSet<int> { 1 };

bool found = false;
int n = 1;
while (!found)
{
    int number1 = pentagonalsList[n];

    // Precaclulate pentagonals up to number1 * 2
    int k = pentagonalsList.Count;
    int lastPentagonal = pentagonalsList.Last();
    while (lastPentagonal < number1 * 2)
    {
        lastPentagonal = GetPentagonalNumber(k++);
        pentagonalsList.Add(lastPentagonal);
        pentagonalsHashSet.Add(lastPentagonal);
    }

    for (int i = n - 1; i > 0; i--)
    {
        int number2 = pentagonalsList[n - i];
        if (pentagonalsHashSet.Contains(number1 + number2) && pentagonalsHashSet.Contains(number1 - number2))
        {
            found = true;
            Console.WriteLine(number1 - number2);
            break;
        }
    }
    n++;
}

Answer 2

Converting numbers to Strings (and back) is slow

In your IsPentagonal(int inputN) function, you convert the float to a string and then attempt to parse it back to an int. Almost always, keeping numbers in numeric form is faster than converting to a string for character manipulation.

This question has lots of different ways to convert floats to ints.

Instead try something like:

private static bool IsPentagonal(int inputN)
{
    double result = (Math.Sqrt(24*inputN + 1) + 1)/6;
    return fabsf(roundf(result) - result) <= 0.00001f);
}