HP Forums

Full Version: Convergents of a Continued Fraction
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
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 }
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
Reference URL's