Yes, I agree with you. If n is so large that we can't use computers' built-in arithmetics, calculating the terms one by one is a good idea. If one insist on looking for a fast algorithm, he might use FFT to implemente multiplication, and the complexity is O( nlog(n) ).
On 4月5日, 下午4时35分, Miroslav Balaz <[email protected]> wrote: > 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 <[email protected]> > > > > > 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 -~----------~----~----~----~------~----~------~--~---
