Convergents of a Continued Fraction
|
03-13-2022, 11:41 PM
(This post was last modified: 11-25-2022 05:47 PM by Thomas Klemm.)
Post: #1
|
|||
|
|||
Convergents of a Continued Fraction
Convergents of a Continued Fraction
References Goal We want to calculate the convergents of a continued fraction. Formula For example, here are the convergents for \([0;1,5,2,2]\). \( \begin{matrix} n & −2 & −1 & 0 & 1 & 2 & 3 & 4 \\ a_n & & & 0 & 1 & 5 & 2 & 2 \\ h_n & 0 & 1 & 0 & 1 & 5 & 11 & 27 \\ k_n & 1 & 0 & 1 & 1 & 6 & 13 & 32 \\ \end{matrix} \) If successive convergents are found, with numerators \(h_1\), \(h_2\), ... and denominators \(k_1\), \(k_2\), ... then the relevant recursive relation is: \( \begin{align} h_n &= a_n h_{n − 1} + h_{n − 2} \\ k_n &= a_n k_{n − 1} + k_{n − 2} \\ \end{align} \) The successive convergents are given by the expression: \( \begin{align} \frac{h_n}{k_n} \end{align} \) Using this formula, we would need to track four values on the stack. However, I couldn't figure out how to do that without using registers. But we can divide all the equations by \(k_{n − 1}\) and get: \( \begin{align} \frac{h_n}{k_{n − 1}} &= a_n \frac{h_{n − 1}}{k_{n − 1}} + \frac{h_{n − 2}}{k_{n − 1}} \\ \\ \frac{k_n}{k_{n − 1}} &= a_n + \frac{k_{n − 2}}{k_{n − 1}} \\ \end{align} \) Now we introduce three variables \(u\), \(v\) and \(w\): \( \begin{align} u &= \frac{h_{n − 1}}{k_{n − 2}} \\ \\ v &= \frac{k_{n − 1}}{k_{n − 2}} \\ \\ w &= \frac{h_{n − 2}}{k_{n − 2}} \\ \end{align} \) With \(u{'}\), \(v{'}\) and \(w{'}\) we denote the successors: \( \begin{align} u{'} &= \frac{h_{n}}{k_{n − 1}} =& a_n w{'} + \frac{w}{v} \\ \\ v{'} &= \frac{k_{n}}{k_{n − 1}} =& a_n + \frac{1}{v} \\ \\ w{'} &= \frac{h_{n − 1}}{k_{n − 1}} =& \frac{u}{v} \\ \end{align} \) So we only need to keep track of the three values \(v\), \(w\), and \(w{'}\) on the stack. The sequence \(w, w{'}, w{''}, \cdots\) are the convergents of the continued fraction. Programs This program is for the HP-42S, but it will work on most HP calculators with little or no modification: Code: 00 { 18-Byte Prgm } This the same program for the HP-15C: Code: 001 { 34 } x↔y Stack Diagram We enter the program at label 00. At that point you can consider \(\frac{w}{v} = 1\) and \(\frac{1}{v} = 0\). Code: | L | T | Z | Y | X | Usage We start with the first two elements of the continued fraction and place them on the stack. However, we must enter the values \(1\) and \(0\) in between: \(a_0\) ENTER 1 ENTER 0 ENTER \(a_1\) ENTER XEQ 00 In the following examples we write only briefly: \(a_0\) 1 0 \(a_1\) XEQ 00 Now we can proceed with: \(a_2\) R/S \(a_3\) R/S \(a_4\) R/S \(a_5\) R/S … Examples Rational Numbers This is the finite continued fraction example from above and represents a rational number. \( [0; 1, 5, 2, 2] \) 0 1 0 1 XEQ 00 5 R/S 2 R/S 2 R/S Code: 0 0.00000000000 0 1 Golden Ratio The golden ratio \(\varphi\) has terms equal to \(1\) everywhere—the smallest values possible—which makes \(\varphi\) the most difficult number to approximate rationally. In this sense, therefore, it is the "most irrational" of all irrational numbers. \( \varphi = [\overline{1}] \) 1 1 0 1 XEQ 00 1 R/S 1 R/S 1 R/S 1 R/S 1 R/S 1 R/S 1 R/S 1 R/S … Code: 1 1.00000000000 1 1 Also it produces the Fibonacci sequence. Periodic Continued Fractions The numbers with periodic continued fraction expansion are precisely the irrational solutions of quadratic equations with rational coefficients. \( \sqrt{42} = [6; \overline{2, 12}] \) 6 1 0 2 XEQ 00 12 R/S 2 R/S 12 R/S 2 R/S 12 R/S 2 R/S 12 R/S 2 R/S 12 R/S 2 R/S … Code: 6 6.00000000000 6 1 Other Patterns While there is no discernible pattern in the simple continued fraction expansion of \(\pi\), there is one for \(e\), the base of the natural logarithm: \( e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, 1, 18, 1, 1, \cdots] \) 2 1 0 1 XEQ 00 2 R/S 1 R/S 1 R/S 4 R/S 1 R/S 1 R/S 6 R/S 1 R/S 1 R/S 8 R/S 1 R/S … Code: 2 2.00000000000 2 1 \(\pi\) No pattern has ever been found in this representation. \( \pi = [3; 7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,2,1,1,15,3,13, \cdots] \) 3 1 0 7 XEQ 00 15 R/S 1 R/S 292 R/S 1 R/S 1 R/S 1 R/S 2 R/S 1 R/S 3 R/S 1 R/S 14 R/S 2 R/S … Code: 3 3.00000000000 3 1 |
|||
« Next Oldest | Next Newest »
|
Messages In This Thread |
Convergents of a Continued Fraction - Thomas Klemm - 03-13-2022 11:41 PM
RE: Convergents of a Continued Fraction - Albert Chan - 09-18-2024, 04:50 PM
RE: Convergents of a Continued Fraction - Albert Chan - 09-18-2024, 08:24 PM
RE: Convergents of a Continued Fraction - Albert Chan - 09-20-2024, 12:04 AM
RE: Convergents of a Continued Fraction - Albert Chan - 09-20-2024, 05:27 PM
RE: Convergents of a Continued Fraction - C.Ret - 09-20-2024, 10:24 PM
RE: Convergents of a Continued Fraction - Thomas Klemm - 09-21-2024, 08:33 AM
|
User(s) browsing this thread: 1 Guest(s)