Finding out nth fibonacci number for very large 'n'

algorithm math fibonacci
kunal18 picture kunal18 · Feb 2, 2013 · Viewed 83k times · Source

I was wondering about how can one find the nth term of fibonacci sequence for a very large value of n say, 1000000. Using the grade-school recurrence equation fib(n)=fib(n-1)+fib(n-2), it takes 2-3 min to find the 50th term!

After googling, I came to know about Binet's formula but it is not appropriate for values of n>79 as it is said here

Is there an algorithm to do so just like we have for finding prime numbers?

Answer

Wayne Rooney picture Wayne Rooney · Feb 2, 2013

You can use the matrix exponentiation method (linear recurrence method). You can find detailed explanation and procedure in this blog. Run time is O(log n).

I don't think there is a better way of doing this.

Related questions

Test if a number is fibonacci

I know how to make the list of the Fibonacci numbers, but i don't know how can i test if a given number belongs to the fibonacci list - one way that comes in mind is generate the list of …

Read More
nth fibonacci number in sublinear time

Is there any algorithm to compute the nth fibonacci number in sub linear time?

Read More
Why are Fibonacci numbers significant in computer science?

Fibonacci numbers have become a popular introduction to recursion for Computer Science students and there's a strong argument that they persist within nature. For these reasons, many of us are familiar with them. They also exist within Computer Science elsewhere …

Read More