2

  • 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$.
Robert Z
  • 145,942
Shadab Sayeed
  • 67
  • 6
  • Dynamic programming is the way to go. I don't know what you want if you think it's too slow. It's super fast. I just wrote a quick script and quickly computed n=10000 – Rushabh Mehta Oct 19 '19 at 19:32
  • Binet formula is definitely approprioate for $n >79$. If you have troubles with that, it is probably because you get numbers which are way too big, and then nothing else can help. – N. S. Oct 19 '19 at 19:33
  • @N.S. I'm pretty sure dynamic programming is probably faster, but yea, Binet's shouldn't be a problem. – Rushabh Mehta Oct 19 '19 at 19:35
  • Sorry I wrote n=10000 i meant big number like if n=4000000 – Shadab Sayeed Oct 19 '19 at 19:50
  • See the last paragraph of https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form – lhf Nov 11 '19 at 15:30

2 Answers2

4

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.

Robert Z
  • 145,942
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.

Ross Millikan
  • 374,822