> 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:

  |phi - (F_(n+1)/F_n)| < (F_n)^(-2) = phi^(-2n)/sqrt(5) (approximately)

And, if |a|>>|b|, then:

  |(a+b)^n - a^n| = n a^(n-1) b (approximately)

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.