Fast Doubling method to find nth Fibonacci number
Before Fast Doubling Method, lets discuss some naïve method to find nth fibonacci number.
1. Recursive Method :
Recursive method is quite known approach to count fibonacci number but its very slow.
Here is the formula to find nth fibonacci number ,
F(0) = 0;
F(1) = 1;
F(n) = F(n-1) + F(n-2) ;
As an example n = 6;
using this above table , F(n) = 5+3 = 8;
// Here is the sample program ,
Its complexity is O(2^n).
2. Iterative method :
This method is too popular but its also very slow to count large fibonacci number. Its use the same formula I have discussed avobe.
// Here is the sample program.
Its complexity O(n).
3. Fast Doubling Method :
This is the faster method than the above two method. We have few methods to calculate fibonacci number in faster way. Out of them matrix exponentiation is most commonly used concept. Another well known concept is fast doubling method. It is called fast doubling method because every time you will found the twice fibonacci number for each n.
Please don't feel shy to comment to improve these program and if you have better program please let me know.
 |
| Fibonacci Table |
1. Recursive Method :
Recursive method is quite known approach to count fibonacci number but its very slow.
Here is the formula to find nth fibonacci number ,
F(0) = 0;
F(1) = 1;
F(n) = F(n-1) + F(n-2) ;
As an example n = 6;
using this above table , F(n) = 5+3 = 8;
// Here is the sample program ,
Its complexity is O(2^n).
2. Iterative method :
This method is too popular but its also very slow to count large fibonacci number. Its use the same formula I have discussed avobe.
// Here is the sample program.
Its complexity O(n).
3. Fast Doubling Method :
This is the faster method than the above two method. We have few methods to calculate fibonacci number in faster way. Out of them matrix exponentiation is most commonly used concept. Another well known concept is fast doubling method. It is called fast doubling method because every time you will found the twice fibonacci number for each n.
Fast doubling is based on two formula.
F(2n) = F(n)[2*F(n+1) – F(n)]
F(2n + 1) = F(n)2 + F(n+1)2
F(2n + 1) = F(n)2 + F(n+1)2
Lets see an example, n = 4;
F(2*4) = F(4) [ 2*F(5) – F(4)]; // follow the above table
=> F(8) = F(4) [ 2*5 – 3];
=> F(8) = 3 * 7;
=> F(8) = 21; // Here we get the F(8) nth fibonacci number.
The 2nd equation is as same as it.
F(9) = F(4)2 +F(5)2 ;
=> F(9) = 32 +52 ;
=> F(9) = 34 ;
// Here is the program.
This code has a complexity of O(log n) which is way too faster than previously discussed function.Please don't feel shy to comment to improve these program and if you have better program please let me know.
