Search code examples
c++c++14sequencefibonaccisequences

Fibonacci sequence faster, but with different starting numbers (F[n]=F[n-1]+F[n-2])

(beginner here)

I want to know how to find n-th number of the sequence F[n]=F[n-1]+F[n-2].

Input:

F[0] =  a;
F[1] =  b;
a,b < 101
N < 1000000001 
M < 8; M=10^M;

a and b are starting sequence numbers.

n is the n-th number of the sequence i need to find.

M is modulo, the number gets very large quickly so F[n]=F[n]%10^M, we find the remainder, because only last digits of the n-th number are needed

The recursive approach is too slow:

int fib(int n)
{
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}

The dynamic programming solution which takes O(n) time is also too slow:

f[i] = f[i-1] + f[i-2];

While there are solutions on how to find n-th number faster if first numbers of the sequence are 0 and 1 (n-th number can be found in O(log n)) by using this formula:

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

(link to formula and code implementation with it: https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)

But this formula does not work if starting numbers are something like 25 and 60. And the recursive approach is too slow.

So I want to know how can I find the n-th number of a sequence faster than O(n). Partial code would be helpful.

Thank you.

Solution

  • This matrix:

    A = / 1  1 \
    \ 1  0 /

    When multiplied by the column vector (fn+1, fn), where fn is the nth number in a Fibonacci sequence, will give you the column vector (fn+2, fn+1), i.e. it will advance you by one step. This works no matter what the initial elements of the sequence were.

    For example:

    / 1  1 \ / 8 \  =  / 13 \
\ 1  0 / \ 5 /     \ 8  /

    So the nth fibonacci number is the first element of An-1v, where v is a column vector containing f1 and f0, the first two numbers in your sequence.

    Therefore, if you can quickly calculate An-1 modulo some number, this will give you fn. This can be done using Exponentiation by squaring, which works in O(logn). Just make sure to perform the modulo after every multiplication and addition to prevent the numbers from getting too big.