thats not good enoguht, because you need to use multiplication of long numbers, and that is n^2, if you use simple algorithm for multiplication,because number of bits in numbers you get is \Theta(n)
and plain stupid algorithm has complexity n^2, which is exponential in input size, but O(n^2) in output size 2009/4/4 obtuseSword <obtusesw...@gmail.com> > > 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 <zch051383471...@gmail.com> 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
