Project Euler 25 - x-digit Fibonacci Number

Question

I have solved the Problem 25 of the Euler Project:

The Fibonacci sequence is defined by the recurrence relation:

\$\qquad F_n = F_{n−1} + F_{n−2}\$, where \$F_1 = 1\$ and \$F_2 = 1\$.

Hence the first 12 terms will be:

\$\qquad F_1 = 1\$

\$\qquad F_2 = 1\$

\$\qquad F_3 = 2\$

\$\qquad F_4 = 3\$

\$\qquad F_5 = 5\$

\$\qquad F_6 = 8\$

\$\qquad F_7 = 13\$

\$\qquad F_8 = 21\$

\$\qquad F_9 = 34\$

\$\qquad F_{10} = 55\$

\$\qquad F_{11} = 89\$

\$\qquad F_{12} = 144\$

The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

---

It was pretty easy to get the result, but i also wanted a solution that is fast and well coded.

The solution of this has two major problems:

1. It is not possible to save a value of 1000 digits in a standard data type (like long)
2. Getting the length of the number

The first problem was very easy to solve with the BigInteger structure.

For the second problem i would like to provide the code first:

public class EulerHelper
{
    private readonly int digits;

    public EulerHelper(int digits)
    {
        this.digits = digits;
    }

    private List<BigInteger> RecentNumbers { get; } =
        new List<BigInteger>(new[] {new BigInteger(0), new BigInteger(1)});

    private BigInteger Fibonacci(int n)
    {
        if (RecentNumbers.Count > n)
        {
            return RecentNumbers[n];
        }

        for (var counter = RecentNumbers.Count; counter <= n; counter++)
        {
            var fibCounter = RecentNumbers[counter - 1] + RecentNumbers[counter - 2];
            RecentNumbers.Add(fibCounter);
        }

        return RecentNumbers[n];
    }

    public int NumberWithNDigits()
    {
        var counter = 1;
        while (IsXDigitsLong(Fibonacci(counter)))
        {
            counter++;
        }

        return counter;
    }

    public bool IsXDigitsLong(BigInteger number)
    {
        var calculatedLength = GetLength(number);
        return calculatedLength < digits;
    }

    private int GetLength(BigInteger number)
    {
        if (number == 1)
        {
            return 1;
        }

        return (int) Math.Floor(BigInteger.Log10(number) + 1);
    }
}

The above code is the final one. But before IsXDigitsLong was a "string-length-compare":

public bool IsXDigitsLong(BigInteger number)
{
    return number.ToString().Length < digits;
}

The final implementation is around 3.8 times faster as the string one which was a big win of performance.

---

The main looks like this:

static void Main(string[] args)
{
    Stopwatch sw = Stopwatch.StartNew();
    var executer = new EulerHelper(1000);
    var result = executer.NumberWithNDigits();
    sw.Stop();

    Console.WriteLine($"The result is {result}");
    Console.WriteLine($"Execution time: {sw.ElapsedTicks}");
    Console.ReadKey();
}

---

Results (Benchmark)

I have done some very rudamentary benchmarks between the .ToString() and the GetLength() implementation:

Method          Time in StopWatch ticks
ToString()      568476
GetLength()     143699

Answer 1

I feel like a class is not a good way to approach this problem.

C# forces you to write classes, but using static methods will allow you to ignore this.

The only method you should keep non-static is the on calculating the n-th fibonacci, as the memoization requires state, and a class is a way to keep state.

Getting the number of digits of a number is instead something without atate that depends only on the input number, so:

public static digitsLength(BigInteger n) {
    return number == 1 ? 1 : (int) Math.Floor(BigInteger.Log10(number) + 1);
}

Minor remarks are:

• Naming: You used get in the name, but in OO get has a precise meaning that is inappropriate here.

• Ternary: When the condition is simple, like here, using a ternary increases compactness and readability.

Now main is simply:

for (var i upto infinity) {
    if DigitsLength( Fibonacci(i) ) == REQUIRED_DIGITS {
        print( Fibonacci(i) )
    }
}

PS: Note that the above is pseudo-code, it is just to give you an idea.

Answer 2

private List<BigInteger> RecentNumbers { get; } =
    new List<BigInteger>(new[] {new BigInteger(0), new BigInteger(1)});  

There are constants (static properties) to use for BigIntegers representing 0 and 1 so you should use them.

But if we take a look at the problem statement we read

"where \$F_1 = 1\$ and \$F_2 = 1\$." so we shouldn't have 0 and 1 but 1 and 1.

---

If I hear fibonacci numbers I always have IEnumerable and yield return in my mind. Assume the following

private static IEnumerable<BigInteger> Fibonacci()
{
    var first = BigInteger.One;
    var second = BigInteger.One;

    while(true)
    {
        var fib = first + second;

        yield return fib;

        first = second;
        second = fib;
    }
} 

That is all you need to generate the fibonacci numbers. As you see this is a infinite loop, so a breaking condition needs to be present in the calling code.

This breaking condition will be checked in this method

public static int GetTermWithDigits(int maxDigits)
{
    int currentTerm = 2;
    foreach(BigInteger value in Fibonacci())
    {
        currentTerm++;
        if (DigitsLength(value) == maxDigits) { return currentTerm; }
    }
    throw new NotImplementedException();
}

together with the former GetLength method sligthly modified

private static int DigitsLength(BigInteger value)
{
    if (value.IsOne)
    {
        return 1;
    }

    return (int)Math.Floor(BigInteger.Log10(value) + 1);
} 

As you can see none of these methods use a state, so every method is static.