Let M denote the 2by2 Matrix (1 1; 1 0), thus the first row of M is
(1,1), and the second row of M is (1,0).
Let X(n) denote the columned vector ( F(n+1); F(n) ), then we get the
equation as below:
X(n) = M.X(n-1); X(0) = ( F1; F0 ) = ( 1; 1 ).
It's easy to verify that X(n) = M^n.X(0). So calculate the M^n, we get
F(n).
If n is even, M^n = ( M^(n/2) )^2; else M^n = M ( M^((n-1)/2) )^2.
Using this strategy, we can calculate the M^n by O( log(n) ) matrix
multiplication.
On 4月3日, 下午6时31分, alex <[email protected]> wrote:
> Does anyone has some good algorithm for Fibonacci number question ,get
> the F(n) ,if n is a big number .......
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
