> The precision to which you need to compute phi in order to compute the Nth Fibonacci number by exponentiation is the precision you'd obtain by computing the ratio of the Nth and (N-1)th Fibonacci numbers
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. (Since:
So our error just has to be < 1/(n phi^(n-1)), which should be true for roughly the N/2 convergent.) In either case, the algorithm is still basically quadratic.
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.
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. (Since:
And, if |a|>>|b|, then: So our error just has to be < 1/(n phi^(n-1)), which should be true for roughly the N/2 convergent.) In either case, the algorithm is still basically quadratic.