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

• hmakholm left over Monica: Note that Binet's formula allows you to solve this without any programming, just few minutes with a scientific calculator (of which most will be spent on trying smaller examples to convince yourself you've counted the fenceposts right). The ((1-sqrt(5))/2)^n term is always less than 1, so finding the index of the first Fibonacci number that is larger than 10^999 is just a matter of taking a logarithm!
• deamentiaemundi: @HenningMakholm It's a bit more than one ;-) Ignoring the term ((-1)/phi)^n we can search for a solution for floor(n * logbase10(phi) - logbase10(5)/2 + 1) = x where x is the number of decimal digits. We can ignore the floor too, here and thus the solution is n = floor((x*(2*log(2)+2*log(5)))/(2*(log(1+sqrt(5))-log(2)))+(2*log(2)+log(5))/(2*(log(2)-log(1+sqrt(5))))) and it took me some time to get all the parentheses right, I can tell you ;-)
• hmakholm left over Monica: @deamentiaemundi: Well, you don't need to expand all those logs just because you can. I'll grant you need two or three logs for computing it in practice without overflow, but not more than that.
• deamentiaemundi: @HenningMakholm that was the onyl way I could come up with the least number of logarithms: log(2), log(5), and log(1+sqrt(5)). (is log(2) not a constant in C#?) You can replace the last one with log(2) + asinh(1/2) to get it down to -(log(20)-x*log(100))/(2*asinh(1/2)). Problem: no asinh in C#. But the Maclaurin series gives about 1 dec. digit per term, 4 terms would suffice for the Euler problem. So: yes, you were right, no need to expand all of the logs.
• hmakholm left over Monica: @deamentiaemundi: Since I'm specifying a scientific calculator rather than a programming language, I'm assuming we have base-10 logs as a primitive. :-) So solving 10^999 = phi^n/sqrt 5 yields n=(log(5)/2+999)/log(phi). Then take the ceiling to find the index of an actual Fibonacci number.

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.

• Jens: Thanks for the response. For sure creating a class is not that optimal. The naming is a littlebit bad. the tip with the ternary oparator is a good point!

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.

• Jens: i have choosen the 0 and 1 implementation because it better fits the array / list. so list[x] matches to \$\qquad F_x\$. I think the other tips are very good and useful! Specially the yield return.