Project Euler 25 - x-digit Fibonacci Number 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:


It is not possible to save a value of 1000 digits in a standard data type (like long)
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&lt;BigInteger&gt; RecentNumbers { get; } =
        new List&lt;BigInteger&gt;(new[] {new BigInteger(0), new BigInteger(1)});

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

        for (var counter = RecentNumbers.Count; counter &lt;= 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 &lt; 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 &lt; 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
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.