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
use memorization u will get in 0(logn)..
On Fri, Apr 3, 2009 at 4:01 PM, alex zch051383471...@gmail.com wrote:
Does anyone has some good algorithm for Fibonacci number question ,get
the F(n) ,if n is a big number ...
--
CHERUVU JAANU