Problem 25: 1000-digit Fibonacci number

Problem:

Please find the problem here.

Solution:

It is not hard to find online the Binet formula to compute Fibonacci number.
$ F_n = (\frac{\sqrt{5} + 1}{2})^n + (\frac{\sqrt{5} - 1}{2})^n $

Note that the second term is an exponential of a number less than 1, that goes to 0 quickly, so let's just ignore that and we get a good approximation

$ \begin{eqnarray*} F_n & \simeq & (\frac{\sqrt{5} + 1}{2})^n \\ \log(F_n) & \simeq & n \log (\frac{\sqrt{5} + 1}{2}) \end{eqnarray*} $

This gives us $ n \simeq 4785 $ when $ \log(F_n) \simeq 1000 $. That means if we use the trivial algorithm for computing Fibonacci number, it takes around 4785 additions and we will get the answer. However, since we know the answer will be approximately 4785, we have a much faster algorithm that allow us to compute $ F_{4785} $.

The algorithm start with observing the matrix

$ \begin{eqnarray*} \left(\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right)^n = \left(\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & 0\end{matrix}\right) \end{eqnarray*} $

With that, we can easily compute $ F_n $ by repeated squaring. Observing the matrix is symmetric we can reduce some arithmetic operations as well.

Once we get to the approximate solution, we need to walk to the solution. By some computation I know $ F_{4785} $ has 1,000 digits, so we need to walk backwards to see when it get started to become 999 digits, and that's when we can stop.

namespace Euler
{
    using System;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem025()
        {
            new Solution025().Execute();
        }

        private class Solution025
        {
            public void Execute()
            {
                FibMatrix one = new FibMatrix
                {
                    a = 1,
                    b = 1,
                    d = 0
                };

                // By Binet formula approximation, we know the solution is around this
                int n = 4784;
                FibMatrix m = Power(one, n, one, Multiply);

                BigInteger big = m.a;
                BigInteger small = m.b;
                // small is the nth Fibonacci number

                // I already know small has 1000 digits by debugging, so I know I need to going backwards
                // in full generality I need to check if I need forward as well
                while (small.ToString().Length >= 1000)
                {
                    BigInteger prev = big - small;
                    big = small;
                    small = prev;
                    n--;
                    // small is still the nth Fibonacci number after the line
                }

                // Small has 999 digits, big has 1000 digit, so the answer is n + 1
                Console.WriteLine(n + 1);
            }

            private FibMatrix Multiply(FibMatrix p, FibMatrix q)
            {
                FibMatrix result = new FibMatrix();
                result.a = p.a * q.a + p.b * q.b;
                result.b = p.a * q.b + p.b * q.d;
                result.d = p.b * q.b + p.d * q.d;
                return result;
            }

            private class FibMatrix
            {
                public BigInteger a;
                public BigInteger b;
                public BigInteger d;
            }
        }
    }
}

Answer: 4782

Note how close is it for our analytic approximation.