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<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
((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! \$\endgroup\$((-1)/phi)^n
we can search for a solution forfloor(n * logbase10(phi) - logbase10(5)/2 + 1) = x
wherex
is the number of decimal digits. We can ignore the floor too, here and thus the solution isn = 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 ;-) \$\endgroup\$log(2)
,log(5)
, andlog(1+sqrt(5))
. (is log(2) not a constant in C#?) You can replace the last one withlog(2) + asinh(1/2)
to get it down to-(log(20)-x*log(100))/(2*asinh(1/2))
. Problem: noasinh
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. \$\endgroup\$10^999 = phi^n/sqrt 5
yieldsn=(log(5)/2+999)/log(phi)
. Then take the ceiling to find the index of an actual Fibonacci number. \$\endgroup\$