03-13-2022, 11:41 PM
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:
This the same program for the HP-15C:
Stack Diagram
We enter the program at label 00.
At that point you can consider \(\frac{w}{v} = 1\) and \(\frac{1}{v} = 0\).
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
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
…
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
…
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
…
\(\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
…
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 }
01 X<>Y
02 R↑
03 LASTX
04 ÷
05 LASTX
06 1/X
07 R↑
08▸LBL 00
09 +
10 X<>Y
11 LASTX
12 R↑
13 ×
14 LASTX
15 R↓
16 +
17 X<>Y
18 ÷
19 END
This the same program for the HP-15C:
Code:
001 { 34 } x↔y
002 { 43 33 } g R⬆
003 { 43 36 } g LSTx
004 { 10 } ÷
005 { 43 36 } g LSTx
006 { 15 } 1/x
007 { 43 33 } g R⬆
008 { 42 21 0 } f LBL 0
009 { 40 } +
010 { 34 } x↔y
011 { 43 36 } g LSTx
012 { 43 33 } g R⬆
013 { 20 } ×
014 { 43 36 } g LSTx
015 { 33 } R⬇
016 { 40 } +
017 { 34 } x↔y
018 { 10 } ÷
019 { 43 32 } g RTN
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 |
+----+----+-----+------+------+
| v | w | w | w' | a | X<>Y
| v | w | w | a | w' | R↑
| v | w | a | w' | w | LASTX
| v | a | w' | w | v | ÷
| v | a | a | w' | w/v | LASTX
| | a | w' | w/v | v | 1/X
| | a | w' | w/v | 1/v | R↑
| | w' | w/v | 1/v | a | LBL 00
| | w' | w/v | 1/v | a | +
| a | w' | w' | w/v | v' | X<>Y
| a | w' | w' | v' | w/v | LASTX
| | w' | v' | w/v | a | R↑
| | v' | w/v | a | w' | ×
| w' | v' | v' | w/v | a*w' | LASTX
| | v' | w/v | a*w' | w' | R↓
| | w' | v' | w/v | a*w' | +
| | w' | w' | v' | u' | X<>Y
| | w' | w' | u' | v' | ÷
| v' | w' | w' | w' | w" |
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
1 1.00000000000 1 1
5 0.83333333333 5 6
2 0.84615384615 11 13
2 0.84375000000 27 32
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
1 2.00000000000 2 1
1 1.50000000000 3 2
1 1.66666666667 5 3
1 1.60000000000 8 5
1 1.62500000000 13 8
1 1.61538461538 21 13
1 1.61904761905 34 21
1 1.61764705882 55 34
1 1.61818181818 89 55
1 1.61797752809 144 89
1 1.61805555556 233 144
1 1.61802575107 377 233
1 1.61803713528 610 377
1 1.61803278689 987 610
1 1.61803444782 1597 987
1 1.61803381340 2584 1597
1 1.61803405573 4181 2584
1 1.61803396317 6765 4181
1 1.61803399852 10946 67651
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
2 6.50000000000 13 2
12 6.48000000000 162 25
2 6.48076923077 337 52
12 6.48073959938 4206 649
2 6.48074074074 8749 1350
12 6.48074069678 109194 16849
2 6.48074069847 227137 35048
12 6.48074069841 2834838 437425
2 6.48074069841 5896813 909898
12 6.48074069841 73596594 11356201
2 6.48074069841 153090001 23622300
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
1 3.00000000000 3 1
2 2.66666666667 8 3
1 2.75000000000 11 4
1 2.71428571429 19 7
4 2.71875000000 87 32
1 2.71794871795 106 39
1 2.71830985915 193 71
6 2.71827956989 1264 465
1 2.71828358209 1457 536
1 2.71828171828 2721 1001
8 2.71828183521 23225 8544
1 2.71828182294 25946 9545
1 2.71828182874 49171 18089
10 2.71828182845 517656 190435
1 2.71828182847 566827 208524
1 2.71828182846 1084483 398959
12 2.71828182846 13580623 4996032
\(\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
7 3.14285714286 22 7
15 3.14150943396 333 106
1 3.14159292035 355 113
292 3.14159265301 103993 33102
1 3.14159265392 104348 33215
1 3.14159265347 208341 66317
1 3.14159265362 312689 99532
2 3.14159265358 833719 265381
1 3.14159265359 1146408 364913
3 3.14159265359 4272943 1360120
1 3.14159265359 5419351 1725033
14 3.14159265359 80143857 25510582