Fast calculation of Fibonacci numbers

Question

• I was wondering how can i find $n$-th Fibonacci number using the recurrence equation

  $F(n)=F(n-1)+F(n-2)$

• if starting $a$,$b$ is given some different random number say $a=5$,$b=8$ than $c=a+b$
• than it follows $5,8,13,21,34$.
• After googling, I came to know about Binet's formula but it is not appropriate for values of $n>79$. And also it's for Fibonacci series starting from $0,1,1,2$ so on.
• Is there way to calculate it fast like a mathematical formula.
• [Edit] I tried using computer to calculate using dynamic programming, but it is taking long for say $n=2000000$.

Answer 1

Binet's formula is fine for any $n$. If it overflows on your computer, you need to have some way to handle large numbers. Python switches over to arbitrary precision integers automatically.

If you use different starting numbers, the constants multiplying $\phi^n$ and $\psi^n$ change, but the basic formula does not. Your formula will be $a\phi^n+b\psi^n$ and you can evaluate $a,b$ from your starting numbers.

Answer 2

Given $F_n$ and $F_{n+1}$, you can "double" the index by using the formulas $$\begin{cases} F_{2n}=F_{n}(2F_{n + 1} - F_{n}) \\ F_{2n + 1} =F_{n}^2 + F_{n + 1}^2. \end{cases}$$ More details can be find here: Fast doubling.