1

(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.

6
  • Similar question here. It has a link to a formula. May 19, 2018 at 21:29
  • 3
    a) This seems like a math question, not a programming question. b) Your fib() is not O(n)... it is much, much, much worse than that. Perhaps a first step would be to actually make it O(n)?
    – Barry
    May 19, 2018 at 21:30
  • 1
    The 1000000001st Fibonacci number has 208987640 digits. You will certainly not save that in any standard C++ type, so directly computing the number won't do you any good. You need to find a more clever way.
    – Baum mit Augen
    May 19, 2018 at 21:35
  • Yes the number gets very large, that is why we find the remainder F[n]=F[n]%10^M. I only need last digits of the n-th number
    – katinas
    May 19, 2018 at 21:36
  • @ljjlaimis You are missing the point of my comment. Functions evaluating the Fibonacci numbers directly are of no use to you because you cannot save the result anyway.
    – Baum mit Augen
    May 19, 2018 at 21:41

1 Answer 1

7

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.

2
  • Since you can choose the elements of the starting vector, its not restricted to the starting values (1,1), is it? Neat, actually, took me a second to realize its potential benefit! May 19, 2018 at 22:24
  • Thank you, I was looking for this solution
    – katinas
    May 20, 2018 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.