algorithm - Finding out nth fibonacci number for very large 'n'

Question

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 1

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.