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
 Thomas Klemm Senior Member Posts: 2,059 Joined: Dec 2013
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 } 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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)