[math-fun] Lucas, Fibo, Phi, capital O
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
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
And, of course, Heron’s method is identical to Newton’s method, but derived geometrically. It’s always fun in an introductory numerical analysis class to show students the geometric proof. And, I also show them what Newton actually did, which was a terrible way of solving polynomial equations. Raphson improved it, but it was still only applicable to polynomials. We had to wait for Simpson (more famous for his approximate rule for integration) until what we now know as Newton’s method was actually derived. And while Bahkshali is quartic, if you go through the steps that build it, it is identical to two steps of Newton’s method. Like many problems, quartic algorithms turn out to be identical to two steps of a quadratic one. The first continued-fraction-like approximation for sqrt(2) actually goes back to Theon of Alexandria. We think he looked at a sequence of squares, and noticed that twice some of them were one off from another, which gave a sequence of approximations to sqrt(2) that had exactly the continued fraction convergents pattern. Steve On Oct 7, 2020, at 9:53 AM, jacobs@xmission.com<mailto:jacobs@xmission.com> wrote: CAUTION: This email originated from outside of JMU. Do not click links or open attachments unless you recognize the sender and know the content is safe. ________________________________ 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<mailto: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<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...
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
participants (4)
-
Fred Lunnon -
jacobs＠xmission.com -
Lucas, Stephen K - lucassk -
Steve Witham