Some popular methods for computing sqrt(N) are Heron's method with quadratic convergence, and Bahkshall method with quartic convergence. Quoting Steve Witham <sw@tiac.net>:
Lucas(n=0, 1, 2...) = 2, 1, 3, 4, 7, 11, 18... = phi^n + (-phi)^(-n)
Fibonacci(n=0, 1, 2...) = 0, 1, 1, 2, 3, 5, 8... = (phi^n - (-phi)^(-n)) / sqrt(5)
(True for n < 0 also.)
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!!
But then I thought, continued fractions probably solve the general sqrt(int) problem just as fast.
And the work that Newton's method does is also about the same because the divisions only need 1, 2, 4... 2^(n-1), 2^n digits of precision.
This is math. This is my brain on math.
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun