Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by RiderOfGiraffes on Tuesday July 07, 2009 @11:53AM
(#691694)
I think you've misunderstood me. You don't evaluate the CF for Phi, you compute with it directly.
Gosper showed that it's possible to compute the CF of Phi^2 (say) directly, without evaluating the CF of Phi. Lather, rinse, repeat. The numbers involved are all similar in size to F(n) and so the complexity is linear. The number of multiplications and squarings is log(n), so I think the whole thing is sub-quadratic. Possibly it's n log(n) rather than linear.
The point is that there are fast ways of doing these sorts of things, but they tend to be little-known and subtle. I've not gone into the details, there may be something I've missed.
Gosper showed that it's possible to compute the CF of Phi^2 (say) directly, without evaluating the CF of Phi. Lather, rinse, repeat. The numbers involved are all similar in size to F(n) and so the complexity is linear. The number of multiplications and squarings is log(n), so I think the whole thing is sub-quadratic. Possibly it's n log(n) rather than linear.
The point is that there are fast ways of doing these sorts of things, but they tend to be little-known and subtle. I've not gone into the details, there may be something I've missed.