My first thought seeing this was that      Lucas(n) / Fibo(n) --> sqrt(5) and the int sequences can be done by repeated squaring, so you could get O(2^n) digits of sqrt(5) with O(n) int multiplications and only one division!!

Ugh, using "n" for two different things.  Lucas(n) and Fibo(n) do have O(n) digits, but the following is wrong:

And the work that Newton's method does is also about the same because the divisions need only 1, 2, 4... 2^(n-1), 2^n digits of precision.

Sorry, instead say 2^1, 2^2, 2^4... 2^(k/2), 2^k digits in k steps. The point is that the order of work is that of the last division.  --Steve