Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by cperciva on Wednesday July 08, 2009 @12:16PM
(#694128)
This seems true empirically, but when I do the math, it looks like you only need to calculate F_n up to about N/2 to make the ratio precise enough.
True -- I oversimplified. But computing both F_n and F_{n+1} (as you need in order to compute the ratio) takes effectively the same amount of time as computing F_{2n}, so it still doesn't win you anything.
True -- I oversimplified. But computing both F_n and F_{n+1} (as you need in order to compute the ratio) takes effectively the same amount of time as computing F_{2n}, so it still doesn't win you anything.