https://en.wikipedia.org/wiki/Methods_of_computing_square_roots When borrowing material from Wikipedia, the information error rate may be reduced by taking the time to increase the font size to a more readable value (via CTRL+ keys), actually reading the text (apparently "Bakhshali" is doubled-up "Heron", and both are effectively equivalent to Newton's method); and of course, citing one's source. WFL On 10/7/20, jacobs@xmission.com <jacobs@xmission.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun