©2022 Compass Learning Technologies → GXWeb Showcase → GXWeb Continued Fraction Collection → GXWeb Continued Fraction Arithmetic
GXWeb Continued Fraction Arithmetic
Saltire Software, home of Geometry Expressions and GXWeb
Symbolic computations on this page use the Nerdamer Symbolic JavaScript to complement the in-built computer algebra system of GXWeb.
Bill Gosper (1972) Appendix 2: Continued Fraction Arithmetic.
Rosetta Code: Continued Fraction Arithmetic.
An Introduction to Continued Fractions by Dr Ron Knott
Continued Fractions by Ben Lynne
Introduction
’Contrary to everybody, this self contained paper will show that continued fractions are not only perfectly amenable to arithmetic, they are amenable to perfect arithmetic.’ (Bill Gosper, 1972)
For Gosper, the appealing concept of perfect arithmetic may well have involved using continued fractions to perform calculations to any desired degree of accuracy. Continued fractions are ideal tools for successive approximation.
The examples explored here may offer a glimpse into one of the enduring questions regarding continued fractions: they are wonderful at representing numbers, both rational and irrational, but can they also serve as practical tools for computation?
While some of these examples involve simple, finite rational values, it is unlikely that anyone would realistically wheel in continued fraction arithmetic for such questions as 107+225.
But for those convoluted rationals and especially those infinite irrationals? Well... it was made for such as these!
Two distinct approaches are offered here: in addition to an implementation of Gosper's original method, you are offered a simpler matrix process, and an even simpler approach, both based on the essential definition of continued fractions as sequences of convergents, at each step approaching the final value of the real number (or numbers) in question.
These last two are offered as suggestions with an invitation to explore, as they do not seem to be documented elsewhere.
Convergence methods require the computation of convergents up to the desired limit of accuracy for BOTH values, and it might be argued that the computational cost is likely to be greater than that required for Gosper's method.
However, simple approaches - such as the Magic Table method - make this process simple and relatively efficient.
For example, consider the product of √(2) and √(3).
The Gosper method requires 39 steps to achieve accuracy to 8 terms of the resultant continued fraction.
The magic table will compute a result accurate to 10 terms in just 21 steps - 10 steps for each input, and the final product of the two resulting fractions!
Explore the Magic Table
Introduction: What is a Magic Table?
To convert a real number to a continued fraction is easy! Try this yourself?
But what if you want to go in the other direction? If you have a continued fraction, and would like to know the real number that it represents?
For some rational numbers (and approximations of irrationals), this is (relatively) easy, since the continued fraction is finite. For most, though, it can be quite arduous.
The most commonly used method involves starting from the bottom and working upwards. This approach, however, does not reveal the successive approximations, the convergents, which in many cases may be just as useful as the final result.
107=1+37=1+173=1+12+13=[1,2,3]
[1,2,3]=1+12+13=1+173=1+37=107
Alternatively, you might try the Magic Table method!
The magic table 1, 2 (first described by Gosper (1972) - credit for the name goes to Associate Professor Terry Gagen of the University of Sydney) offers an efficient and (relatively) simple way to generate the convergents of a continued fraction - it can even be used, in 1 or 2 dimensions, on linear fractional transformations of continued fractions and, in 3 dimensions, forms the basis for Gosper's algorithm for continued fraction arithmetic.
For example, the continued fraction of
√(37)=>a(n)=[6,12,12,12,12,12,12,...]b(n)=[1,1,1,1,1,1,1...] 6+112+112+112+112+112+112+112...Using the approaches described here is much simpler than, for example, matrix methods to calculate a result such as
√37+47=[1407]⋅√(37)=[1407]⋅[√(37)001]where the linear fractional transformation is the matrix
[1407] and [1001]represents the identity matrix.
... 12 12 12 12 12 6 a(n) ... 1 1 1 1 1 (1) b(n) ... 213442 17665 1462 121 10 1 4 ... 148183 12264 1015 84 7 0 7
Introducing the Magic Table: Dimension 1
Gosper's original (dimension 1) version of the magic table was presented horizontally, reading from right to left. A simplified form (which delivers each convergent in turn) might be represented as shown above.
Note that Gosper dealt only with simple continued fractions for which all b(n) (numerator) terms may be assumed to be 1. We go a step further here, adding a b(n) row to support general continued fractions.
Can you see how the pairs of numbers below the continued fraction terms are calculated? (Notice that the first convergent is calculated directly from the terms of the linear fractional transformation.)
Tap on these pairs to see, or tap on the red continued fraction terms - from right to left - to see Gosper's Magic Table in action!
Introducing the Magic Table: Dimension 2
More importantly, Gosper was not really interested in simply outputting the convergents of continued fractions.
His real goal was to take a continued fraction, operate on it in some way - initially, using a linear fractional transformation, but leading to arithmetic operations with another continued fraction - and output the result directly as a continued fraction: true continued fraction arithmetic!
For this, he needed more dimensions for his magic table!
Teasing Out the Resultant Continued Fraction
It should be noted that drawing out each term of the resultant continued fraction is not always a straightforward operation.
Consider the first TWO convergents of
√37+47=[1407]⋅√(37) =>107 and 12184Taking the floor or integer part of both delivers the same result (|107|=|12184|=1), so we can be confident in the first term of our resultant continued fraction.
To continue, we need the dimension 2 table, since we now move one step down and one step to the left (in the table above, or to the right in the table below). The next two convergents to consider are 8437 and 1015447. If the floor values of both agree (which they do in this case), we continue this process, moving down and horizontally forward.
If NOT, then we simply move one step horizontally forward, and try the next pair of convergents, until we find two that agree, and this process gives each subsequent term of our resultant continued fraction.
For a more interesting example, consider Gosper's case of e with linear fractional transformation, [1,-1,1,1]:
tanh(12)=e−1e+1Here we see that the first convergent pair (13 and 24) both deliver floor values of 0. The second pair (115 and 42) give us the next resultant term of 2.
Subsequently, though, |51|=5 and |71|=7. We must continue to the next terms, 122 and (with a little calculation) 559 (4⋅12+1⋅7=55 and 4⋅2+1⋅1=9) to confirm the floor result of 6.
The floor values of pairs of adjacent convergents must differ by no more than 1 to deliver the next term of the resultant continued fraction.
For ease of presentation, in our versions, the terms are displayed vertically, with the terms of the linear fractional transformation found at the top of the numerator and denominator columns (rotated -90°).
Step by Step
Tap to view:
Simple Convergent Form 1
Simple Convergent Form 2
Gosper Magic Table 1
Gosper Magic Table 2
Gosper Magic Table 3
Gosper Magic Table 4
Gosper Magic Table 5
In its simplest form, Gosper's Magic Table initially offers a convenient way to generate the convergents for a given continued fraction, along with a linear fractional transformation, expressed as a 2x2 matrix.
(Tap for an example) ⇑
General Continued Fractions: Some Examples
Note that the Magic Table presented here represents an extension of Gosper's method, supporting general continued fractions in addition to simple ones. For example, did you know that
π≈0+41+13+45+97+169+2511+3613+4915+6417+8119...a(n)=[0,1,3,5,7,9,11,13,15,17,19]b(n)=[4,1,4,9,16,25,36,49,64,81]
And what about the Farey and Stern-Brocot Continued Fractions: if you wanted to start a list of every rational number, then these amazing continued fractions are perfect for that!
0+13−11−13−11=0+13+1−1+13+1−1 ⇒[0,13,12,23,1]
Farey Sequence Level 3:mtable([[0,3,-1,3,-1],[1,1,1,1,1]],[1,0,0,1])
OR mtable([[0,3,1,3,1],[1,-1,-1,-1,-1]],[1,0,0,1])
0+14−11−13−11−15−11−13−11 ⇒[0,14,13,25,12,35,34,23,1] Farey Sequence Level 4:
mtable([[0,4,-1,3,-1,5,-1,3,-1],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])
OR mtable([[0,4,1,3,1,5,1,3,1],[1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1])
0+13−11−13−11−15−11−13−11 ⇒[0,13,12,23,1,32,21,31,10] Stern-Brocot Sequence Level 3:
mtable([[0,3,-1,3,-1,5,-1,3,-1],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])
OR mtable([[0,3,1,3,1,5,1,3],[1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1])
Stern-Brocot Sequence Level 4:
0+14−11−13−11−15−11−13−11−17−11−13−11−15−11−13−11 ⇒[0,14,13,25,12,35,34,23,1,32,43,53,21,52,31,41,10]mtable([[0,4,-1,3,-1,5,-1,3,-1,7,-1,3,-1,5,-1,3],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]],[1,0,0,1],0,17)
OR mtable([[0,4,1,3,1,5,1,3,1,7,1,3,1,5,1,3],[1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1],0,17)
Try More Examples
Simple (Convergent)
Magic Table
Dimension 1Gosper
Magic Table
Dimension 2Enter mtable(), or
mtable(sqrt(37)), or
mtable(sqrt(37),[1,4,0,7]), or even
mtable(sqrt(37),[1,4,0,7],0,12)Try one of Gosper's examples:
mtable(sqrt(2),[0,2,-1,3],0,12)You can also enter arrays: mtable([1,2,3,4,5],[1,0,0,1],0,12) or
mtable([[1,2,3,4],[4,3,2,1],[1,0,0,1],0,12)Try mtable([[2,1,2,3,4,5,6,7,8,9,10],[1,1,2,3,4,5,6,7,8,9,10]],[1,0,0,1],0,12)
Enter gmt(), or
gmt(sqrt(37)), or
gmt(sqrt(37),[1,4,0,7]), or even
gmt(sqrt(37),[1,4,0,7],0,12)Try one of Gosper's examples:
gmt(sqrt(2),[0,2,-1,3],0,12)You can also enter arrays: gmt([1,2,3,4,5],[1,0,0,1],0,12) or
gmt([[1,2,3,4],[4,3,2,1],[1,0,0,1],0,12)Try gmt([[2,1,2,3,4,5,6,7,8,9,10],[1,1,2,3,4,5,6,7,8,9,10]],[1,0,0,1],0,12)
mtable([[0,1,3,5,7,9,11,13,15,17,19],[4,1,4,9,16,25,36,49,64,81,100]],[1,0,0,1],0,12).
Perhaps even compare
mtable([[4,2,2,2,2,2,2,17,294],[-1,-1,-1,-1,-1,-1,-1,-1,-1]],[1,0,0,1]) with
mtable([[4,-2,2,-2,2,-2,2,-17,294],[1,1,1,1,1,1,1,1,1]],[1,0,0,1])?
Gosper's Method
Although continued fractions have been around in some form since the time of Euclid, Gosper's breakthrough in seeing how they could be useful arithmetically came through his ability to see the problem from both mathematical and programming perspectives.
We might begin with a relatively straightforward example of arithmetic involving a single continued fraction.
If √37=6+112+112+112+112+...=>[6110]⋅[12110]⋅[12110]⋅[12110]⋅[12110]... Then 4+√(37)7=[1407]⋅√37=>[1407]⋅[6110]⋅[12110]⋅[12110]⋅[12110]⋅[12110]...It is easy to see how such a process can serve to generate successively more accurate results - in fact, leading to a result of essentially any desired degree of accuracy, unhampered by the fixed accuracy of your calculating device!
This is likely what Gosper was referring to in relation to continued fractions and perfect arithmetic - by taking successive convergents, the process may continue for as long as desired, each new result progressively more accurate.
Gosper described the above function as homographic (based upon the linear fractional transformation encountered previously), defined in terms of a function of the form
z=a⋅x+bc⋅x+dThe process described next comes from the wonderful Rosetta Code site which not only clearly captures Gosper's fuller intent, but includes multiple examples in a range of coding languages (although not, sadly for me, in JavaScript - I had to work this out for myself!).
This task performs the basic mathematical functions on 2 continued fractions, x and y, and requires a 2 x 4 matrix:
[a12a1a2ab12b1b2b]For example,
[01100001] ⇒0⋅x⋅y+1⋅x+1⋅y+00⋅x⋅y+0⋅x+0⋅y+1representing x+y.
With this process, I may perform perform the following operations:
Input the next term of continued fraction x
Input the next term of continued fraction y
Output a term of the continued fraction resulting from the operation.
I output a term if the integer parts of a12b12 and a1b1 and a2b2 and ab are equal.
Otherwise I input a term from continued fraction x or continued fraction y. If I need a term from either fraction but it has no more terms I inject ∞ (which is just the empty continued fraction []).
When I input a term t from continued fraction x I change my internal state:
[a12a1a2ab12b1b2b]⇒[a2+a12⋅ta+a1⋅ta12a1b2+b12⋅tb+b1⋅tb12b1]When I need a term from exhausted continued fraction x I change my internal state:
[a12a1a2ab12b1b2b]⇒[a12a1a12a1b12b1b12b1]When I input a term t from continued fraction y I change my internal state:
[a12a1a2ab12b1b2b]⇒[a1+a12⋅ta12a+a2⋅ta2b1+b12⋅tb12b+b2⋅tb2]When I need a term from exhausted continued fraction y I change my internal state:
[a12a1a2ab12b1b2b]⇒[a12a12a2a2b12b12b2b2]When I output a term t I change my internal state:
[a12a1a2ab12b1b2b]⇒[b12b1b2ba12−b12⋅ta1−b1⋅ta2−b2⋅ta−b⋅t]When I need to choose to input from x or y I act:
if b and b2 are zero I choose x
if b is zero I choose y
if b2 is zero I choose y
if abs(a1b1−ab) is greater than abs(a2b2−ab) I choose x otherwise I choose y
In brief, we may define a 2 x 4 matrix: [a12a1a2ab12b1b2b]
which when "applied" to two continued fractions x and y gives a new continued fraction z such that:
z=a12⋅x⋅y+a1⋅x+a2⋅y+ab12⋅x⋅y+b1⋅x+b2⋅y+b
For example, let
x=107and
y=225We wish to apply the following linear fractional transformations to x and y:
(3⋅x+4)(2⋅x−1)+(y+3)(2⋅y−1) =8⋅x⋅y+3⋅x+7⋅y−74⋅x⋅y−2⋅x−2⋅y+1 ⇒[837−74−2−21]
[837−74−2−21] abs(a1b1−ab)>abs(a2b2−ab)so choose from x
x=[1,2,3]=107=>[1] y=[4,2,2]=225=>[] Input(t)=1 [a12a1a2ab12b1b2b]⇒[a2+a12⋅ta+a1⋅ta12a1b2+b12⋅tb+b1⋅tb12b1] [837−74−2−21] ⇒[7+8⋅1−7+3⋅183−2+4⋅11+(−2)⋅14−2] ⇒[15−4832−14−2] Floor:[7,4,2,−2] Output=>[]
⇒[15−4832−14−2] abs(a1b1−ab)>abs(a2b2−ab)so choose from x
x=[1,2,3]=107=>[1,2] y=[4,2,2]=225=>[] Input(t)=2 [a12a1a2ab12b1b2b]⇒[a2+a12⋅ta+a1⋅ta12a1b2+b12⋅tb+b1⋅tb12b1] [15−4832−14−2] ⇒[8+15⋅23+(−4)⋅2834+2⋅2−2+(−1)⋅24−2] ⇒[38−515−48−42−2] Floor:[4,1,7,4] Output=>[]
⇒[38−515−48−42−2] abs(a1b1−ab)<=abs(a2b2−ab)(or undefined) so choose from y
x=[1,2,3]=107=>[1,2] y=[4,2,2]=225=>[4] Input(t)=4 [a12a1a2ab12b1b2b]⇒[a1+a12⋅ta12a+a2⋅ta2b1+b12⋅tb12b+b2⋅tb2] [38−515−48−42−2] ⇒[−5+38⋅438−4+15⋅415−4+8⋅48−2+2⋅42] ⇒[14738561528862] Floor:[5,4,9,7] Output=>[]
⇒[14738561528862] abs(a1b1−ab)>abs(a2b2−ab)so choose from x
x=[1,2,3]=107=>[1,2,3] y=[4,2,2]=225=>[4] Input(t)=3 [a12a1a2ab12b1b2b]⇒[a2+a12⋅ta+a1⋅ta12a1b2+b12⋅tb+b1⋅tb12b1] [14738561528862] ⇒[56+147⋅315+38⋅3147387+28⋅32+8⋅34−2] ⇒[497129147389126288] Floor:[5,4,5,4] Output=>[]
⇒[497129147389126288] abs(a1b1−ab)<=abs(a2b2−ab)(or undefined) so choose from y
x=[1,2,3]=107=>[1,2,3] y=[4,2,2]=225=>[4,2] Input(t)=2 [a12a1a2ab12b1b2b]⇒[a1+a12⋅ta12a+a2⋅ta2b1+b12⋅tb12b+b2⋅tb2] [497129147389126288] ⇒[129+497⋅249738+147⋅214726+91⋅2918+28⋅228] ⇒[1123497332147208916428] Floor:[5,5,5,5] Output=>[5]When I output a term t I change my internal state:
[a12a1a2ab12b1b2b]⇒[b12b1b2ba12−b12⋅ta1−b1⋅ta2−b2⋅ta−b⋅t] [1123497332147208916428] ⇒[2089164281123−208⋅5497−91⋅5332−64⋅5147−28⋅5] ⇒[2089164288342127]
⇒[2089164288342127] abs(a1b1−ab)>abs(a2b2−ab)but x is exhausted so I change my internal state:
[a12a1a2ab12b1b2b]⇒[a12a1a12a1b12b1b12b1] [2089164288342127] ⇒[208912089183428342] Floor:[2,2,2,2] Output=>[5,2]=112When I output a term t I change my internal state:
[a12a1a2ab12b1b2b]⇒[b12b1b2ba12−b12⋅ta1−b1⋅ta2−b2⋅ta−b⋅t] [208912089183428342] ⇒[83428342208−83⋅291−42⋅2208−83⋅291−42⋅2] ⇒[83428342427427]
⇒[83428342427427] abs(a1b1−ab)<=abs(a2b2−ab)(or undefined) so choose from y
x=[1,2,3]=107=>[1,2,3] y = [4,2,2] = \frac{22}{5} => [4,2,2] Input (t) = 2 \begin{bmatrix} a_{12} & a_{1} & a_{2} & a \\ b_{12} & b_{1} & b_{2} & b \end{bmatrix} ⇒ \begin{bmatrix} a_{1}+a_{12}\cdot t & a_{12} & a + a_{2} \cdot t & a_{2} \\ b_{1}+b_{12} \cdot t & b_{12} & b+b_{2} \cdot t & b_{2} \end{bmatrix} \begin{bmatrix} 83 & 42 & 83 & 42 \\ 42 & 7 & 42 & 7 \end{bmatrix} ⇒ \begin{bmatrix} 42+83\cdot 2 & 83 & 42+83\cdot 2 & 42 \\ 7+42\cdot 2 & 42 & 7 + 42 \cdot 2 & 42 \end{bmatrix} ⇒ \begin{bmatrix} 208 & 83 & 208 & 42 \\ 91 & 83 & 91 & 42 \end{bmatrix} Floor: [2,1,2,1] Output => []
⇒ \begin{bmatrix} 208 & 83 & 208 & 42 \\ 91 & 83 & 91 & 42 \end{bmatrix} abs(\frac{a1}{b1}-\frac{a}{b}) <= abs(\frac{a2}{b2}-\frac{a}{b})(or undefined) but y is exhausted so I change my internal state:
\begin{bmatrix} a_{12} & a_{1} & a_{2} & a \\ b_{12} & b_{1} & b_{2} & b \end{bmatrix} ⇒ \begin{bmatrix} a_{12} & a_{12} & a_{2} & a_{2} \\ b_{12} & b_{12} & b_{2} & b_{2} \end{bmatrix} \begin{bmatrix} 208 & 83 & 208 & 42 \\ 91 & 83 & 91 & 42 \end{bmatrix} ⇒ \begin{bmatrix} 208 & 208 & 208 & 208 \\ 91 & 91 & 91 & 91 \end{bmatrix} Floor: [2,2,2,2] Output => [5,2,2] = \frac{27}{5}When I output a term t I change my internal state:
\begin{bmatrix} a_{12} & a_{1} & a_{2} & a \\ b_{12} & b_{1} & b_{2} & b \end{bmatrix} ⇒ \begin{bmatrix} b_{12} & b_{1} & b_{2} & b \\ a_{12}-b_{12} \cdot t & a_{1}-b_{1} \cdot t & a_{2}-b_{2} \cdot t & a - b \cdot t \end{bmatrix} \begin{bmatrix} 208 & 208 & 208 & 208 \\ 91 & 91 & 91 & 91 \end{bmatrix} ⇒ \begin{bmatrix} 91 & 91 & 91 & 91 \\ 208 - 91 \cdot 2 & 208 - 91 \cdot 2 & 208 - 91 \cdot 2 & 208 - 91 \cdot 2 \end{bmatrix} ⇒ \begin{bmatrix} 91 & 91 & 91 & 91 \\ 26 & 26 & 26 & 26 \end{bmatrix}
⇒ \begin{bmatrix} 91 & 91 & 91 & 91 \\ 26 & 26 & 26 & 26 \end{bmatrix} abs(\frac{a1}{b1}-\frac{a}{b}) <= abs(\frac{a2}{b2}-\frac{a}{b})(or undefined) but y is exhausted so I change my internal state:
\begin{bmatrix} a_{12} & a_{1} & a_{2} & a \\ b_{12} & b_{1} & b_{2} & b \end{bmatrix} ⇒ \begin{bmatrix} a_{12} & a_{12} & a_{2} & a_{2} \\ b_{12} & b_{12} & b_{2} & b_{2} \end{bmatrix} \begin{bmatrix} 91 & 91 & 91 & 91 \\ 26 & 26 & 26 & 26 \end{bmatrix} ⇒ \begin{bmatrix} 91 & 91 & 91 & 91 \\ 26 & 26 & 26 & 26 \end{bmatrix} Floor: [3,3,3,3] Output => [5,2,2,3] = \frac{92}{17}When I output a term t I change my internal state:
\begin{bmatrix} a_{12} & a_{1} & a_{2} & a \\ b_{12} & b_{1} & b_{2} & b \end{bmatrix} ⇒ \begin{bmatrix} b_{12} & b_{1} & b_{2} & b \\ a_{12}-b_{12} \cdot t & a_{1}-b_{1} \cdot t & a_{2}-b_{2} \cdot t & a - b \cdot t \end{bmatrix} \begin{bmatrix} 91 & 91 & 91 & 91 \\ 26 & 26 & 26 & 26 \end{bmatrix} ⇒ \begin{bmatrix} 26 & 26 & 26 & 26 \\ 91 - 26 \cdot 3 & 91 - 26 \cdot 3 & 91 - 26 \cdot 3 & 91 - 26 \cdot 3 \end{bmatrix} ⇒ \begin{bmatrix} 26 & 26 & 26 & 26 \\ 13 & 13 & 13 & 13 \end{bmatrix}
⇒ \begin{bmatrix} 26 & 26 & 26 & 26 \\ 13 & 13 & 13 & 13 \end{bmatrix} abs(\frac{a1}{b1}-\frac{a}{b}) <= abs(\frac{a2}{b2}-\frac{a}{b})(or undefined) but y is exhausted so I change my internal state:
\begin{bmatrix} a_{12} & a_{1} & a_{2} & a \\ b_{12} & b_{1} & b_{2} & b \end{bmatrix} ⇒ \begin{bmatrix} a_{12} & a_{12} & a_{2} & a_{2} \\ b_{12} & b_{12} & b_{2} & b_{2} \end{bmatrix} \begin{bmatrix} 26 & 26 & 26 & 26 \\ 13 & 13 & 13 & 13 \end{bmatrix} ⇒ \begin{bmatrix} 26 & 26 & 26 & 26 \\ 13 & 13 & 13 & 13 \end{bmatrix} Floor: [2,2,2,2] Output => [5,2,2,3,2] = \frac{211}{39}When I output a term t I change my internal state:
\begin{bmatrix} a_{12} & a_{1} & a_{2} & a \\ b_{12} & b_{1} & b_{2} & b \end{bmatrix} ⇒ \begin{bmatrix} b_{12} & b_{1} & b_{2} & b \\ a_{12}-b_{12} \cdot t & a_{1}-b_{1} \cdot t & a_{2}-b_{2} \cdot t & a - b \cdot t \end{bmatrix} ⇒ \begin{bmatrix} 26 & 26 & 26 & 26 \\ 13 & 13 & 13 & 13 \end{bmatrix} ⇒ \begin{bmatrix} 13 & 13 & 13 & 13 \\ 26 - 13\cdot 2 & 26 - 13\cdot 2 & 26 - 13\cdot 2 & 26 - 13\cdot 2 \end{bmatrix} ⇒ \begin{bmatrix} 13 & 13 & 13 & 13 \\ 0 & 0 & 0 & 0 \end{bmatrix}And here we stop!
Output => [5,2,2,3,2] = \frac{211}{39}
Convergent Method
Continued fractions are perfect tools for highly accurate approximation of real numbers, and so it follows that they might also serve to perform arithmetic operations in the same way, taking a pair of convergents at each step.
If one term has more convergents than the other, simply reuse the final value of the shorter array!
Study the method detailed here, and then compare it with the Gosper process above.
This method is essentially a simpler version of the matrix process described later - both enable successive approximation using convergents - and both appear to do so in a more efficient manner than the established Gosper approach.
= \frac{990}{157}= [6,3,3,1,2,4]
\frac{225}{157}= [1,2,3,4,4,1]= 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{4 + \cfrac{1}{1}}}}}Convergents:1,\frac{3}{2},\frac{10}{7}, \frac{43}{30}, \frac{182}{127}, \frac{225}{157} \ * \ \frac{22}{5}= [4,2,1,1]= 4 + \cfrac{1}{2 + \cfrac{1}{1 + \cfrac{1}{1}}}Convergents:1,\frac{9}{2},\frac{13}{3}, \frac{22}{5}
1*4 = 4\approx 4(error = 36.5656565659\%)[3,1]
\frac{3}{2}*\frac{9}{2} = \frac{27}{4}\approx 6.75(error = -7.0454545451\%)[6,1,2,1]
\frac{10}{7}*\frac{13}{3} = \frac{130}{21}\approx 6.1904761905(error = 1.8278018282\%)[6,5,3,1]
\frac{43}{30}*\frac{22}{5} = \frac{473}{75}\approx 6.3066666667(error = -0.0148148144\%)[6,3,3,1,4,1]
\frac{182}{127}*\frac{22}{5} = \frac{4004}{635}\approx 6.305511811(error = 0.0034995629\%)[6,3,3,1,1,1,16,1]
\frac{225}{157}*\frac{22}{5} = \frac{990}{157}\approx 6.3057324841(error = 4e^{-10}\%)[6,3,3,1,2,4]
Negative (or Reversal) Continued Fractions
Did you know that there are TWO classical forms for continued fractions?
\frac{10}{7} = [1,2,3] = 1+\cfrac{1}{2+\cfrac{1}{3}} \frac{10}{7} = [2,2,4]^- = 2-\cfrac{1}{2-\cfrac{1}{4}}= [2,-2,4] = 2+\cfrac{1}{-2+\cfrac{1}{4}} The simple or general form is built by taking the floor (or whole number part) of the fraction at each level and adding the reciprocal of the tail.
The reversal or negative form takes instead the ceiling or next whole number value above, and subtracts the value of the term to form the tail! The reciprocal of this tail then forms the next term in the process.
To convert a real number (n) to a continued fraction is easy!
To convert a real number (n) to a negative or reversal continued fraction is just as easy!
Try this yourself?
Step 1: Take the integer part of the number - floor[n] or Math.floor(n): This is your first index (call it a_0 ), and first convergent.
Step 2: Subtract the integer part to leave the decimal part - the tail. Tail = n - floor(n)
Step 3: Calculate the reciprocal of the tail ( 1 \over Tail ) - this should give a number greater than or equal to 1.
Step 4: Take the integer part of this reciprocal value (a_1 = floor({ 1 \over Tail }) ): This is your next index - call it a_1 , and {a_0 + {1 \over a_1}} the next convergent.
Step 5: Return to Step 2 and repeat the process...
Try this yourself?
Step 1: Round up to the integer above the number - ceil[n] or Math.ceil(n): This is your first index (call it a_0 ), and first convergent.
Step 2: Subtract the current value from the integer part to leave the decimal part - the tail. Tail = ceil(n) - n
Step 3: Calculate the reciprocal of the tail ( 1 \over Tail ) - this should give a number greater than or equal to 1.
Step 4: Take the ceiling of this reciprocal value (a_1 = ceil({ 1 \over Tail }) ): This is your next index - call it a_1 , and {a_0 + {1 \over a_1}} the next convergent.
Step 5: Return to Step 2 and repeat the process...
\frac{10}{7} = [1,2,2,1] = 1 + \cfrac{1}{2 + \cfrac{1}{2+\cfrac{1}{1}}} (Enter 10/7 or 1,2,3 or 1,2,2,1)
[\frac{10}{7}]^{-} = [2,2,4]^{-} = 2 - \cfrac{1}{2 - \cfrac{1}{4}} (Enter [10/7]^- or [2,2,4]^-
or [10/7]{neg} or [2,2,4]{neg})\frac{43}{30} = [1,2,3,4] = 1 + \cfrac{1}{2 + \cfrac{1}{3+\cfrac{1}{4}}} (Enter 43/30 or 1,2,3,4)
[\frac{43}{30}]^{-} = [2,2,5,2,2,2]^{-} = 2 - \cfrac{1}{2 - \cfrac{1}{5-\cfrac{1}{2-\cfrac{1}{2-\cfrac{1}{2}}}}} (Enter [43/30]^- or [2,2,5,2,2,2]^-
or [43/30]{neg} or [2,2,5,2,2,2]{neg})
Now suppose we were to apply such negative continued fractions to our convergents method of continued fraction arithmetic!
Since the usual (positive) method produces convergents that approach the true value from below, and the negative method approaches from above, then using the positive method for the x numeric term and the negative method for y, we might expect to potentially achieve an even more efficient convergence, particularly when dealing with irrationals!
For example, when calculating the product of \sqrt(2) and \sqrt(3), the actual continued fraction of \sqrt(6) reaches 12 step accuracy after 12 convergents ([2,2,4,2,4,2,4,2,4,2,4,2]). The negative form of the convergents method achieves 9 steps, while the positive form has only 6 step accuracy.
= \frac{990}{157}= [6,3,3,1,2,4]
\frac{225}{157}= [1,2,3,4,4,1]= 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{4 + \cfrac{1}{4 + \cfrac{1}{1}}}}}Convergents:1,\frac{3}{2},\frac{10}{7}, \frac{43}{30}, \frac{182}{127}, \frac{225}{157} \ * \ \frac{22}{5}= [5,-2,3]= 5 + \cfrac{1}{-2 + \cfrac{1}{3}}Convergents:5,\frac{9}{2}, \frac{22}{5}
Positive y
1*4 = 4\approx 4(error = 36.5656565659\%)[3,1]
\frac{3}{2}*\frac{9}{2} = \frac{27}{4}\approx 6.75(error = -7.0454545451\%)[6,1,2,1]
\frac{10}{7}*\frac{13}{3} = \frac{130}{21}\approx 6.1904761905(error = 1.8278018282\%)[6,5,3,1]
\frac{43}{30}*\frac{22}{5} = \frac{473}{75}\approx 6.3066666667(error = -0.0148148144\%)[6,3,3,1,4,1]
\frac{182}{127}*\frac{22}{5} = \frac{4004}{635}\approx 6.305511811(error = 0.0034995629\%)[6,3,3,1,1,1,16,1]
\frac{225}{157}*\frac{22}{5} = \frac{990}{157}\approx 6.3057324841(error = 4e^{-10}\%)[6,3,3,1,2,4]Negative y
1*5 = 5\approx 5(error = 20.707065\%)[4,1]
\frac{3}{2}*\frac{9}{2} = \frac{27}{4}\approx 6.75(error = -7.0454545451\%)[6,1,2,1]
\frac{10}{7}*\frac{22}{5} = \frac{44}{7}\approx 6.285714(error = 0.317453\%)[6,3,1,1]
\frac{43}{30}*\frac{22}{5} = \frac{473}{75}\approx 6.3066666667(error = -0.0148148144\%)[6,3,3,1,4,1]
\frac{182}{127}*\frac{22}{5} = \frac{4004}{635}\approx 6.305511811(error = 0.0034995629\%)[6,3,3,1,1,1,16,1]
\frac{225}{157}*\frac{22}{5} = \frac{990}{157}\approx 6.3057324841(error = 4e^{-10}\%)[6,3,3,1,2,4]
A Matrix Alternative?
A potentially simpler approach than that which Gosper describes to the use of continued fractions in achieving efficient successive approximation may lie in a more direct use of matrix operations.
Begin this process with TWO linear fractional (homographic) functions expressed as 2x2 matrices, N1 and N2, as shown above. Each will operate upon a continued fraction, N1 with x and N2 with y.
N1 = \begin{bmatrix} a_0 & a_1 \\ a_2 & a_3 \end{bmatrix} = \frac{(a_0\cdot x+a_1)}{(a_2\cdot x+a_3)}and
N2 = \begin{bmatrix} b_0 & b_1 \\ b_2 & b_3 \end{bmatrix} = \frac{(b_0\cdot y+b_1)}{(b_2\cdot y+b_3)}For example,
N1 = \begin{bmatrix} 3 & 4 \\ 2 & -1 \end{bmatrix} = \frac{(3x+4)}{(2x-1)}and
N2 = \begin{bmatrix} 1 & 3 \\ 2 & -1 \end{bmatrix} = \frac{(y+3)}{(2y-1)}Let the continued fractions be x = \frac{10}{7} = [1,2,3] and y = \frac{22}{5} = [4,2,2].
As shown above, these might also be defined as the product of 2x2 matrices:
\frac{10}{7} = 1+ \cfrac{1}{2+\cfrac{1}{3}}=> \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 10 & 3 \\ 7 & 2 \\ \end{bmatrix}and
\frac{22}{5} = 4+ \cfrac{1}{2+\cfrac{1}{2}}=> \begin{bmatrix} 4 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 22 & 9 \\ 5 & 2 \\ \end{bmatrix}We might then represent operations such as the sum - or difference, or product, or quotient - of the two functions of continued fractions using matrix representation.
However, the sum and difference of two matrices do not directly correspond to the sum and difference of two continued fractions expressed in matrix form!
Normal matrix addition is defined as:
\begin{bmatrix} a_0 & a_1 \\ a_2 & a_3 \end{bmatrix} + \begin{bmatrix} b_0 & b_1 \\ b_2 & b_3 \end{bmatrix} = \begin{bmatrix} a_0+b_0 & a_1+b_1 \\ a_2+b_2 & a_3+b_3 \end{bmatrix}For example,
\begin{bmatrix} 10 & 3 \\ 7 & 2 \end{bmatrix} + \begin{bmatrix} 22 & 9 \\ 5 & 2 \end{bmatrix} = \begin{bmatrix} 32 & 12 \\ 12 & 4 \end{bmatrix}The matrix representation for \frac{10}{7} and \frac{22}{5}, however, serves to display the final two rational convergents of the continued fractions for these numbers.
\frac{10}{7} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 10 & 3 \\ 7 & 2 \\ \end{bmatrix} \frac{22}{5} = \begin{bmatrix} 4 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 22 & 9 \\ 5 & 2 \\ \end{bmatrix}
In order to represent, not just the static values but the dynamic arithmetic required here, we will define new matrix operations, here denoted by
[+] (for Gosper matrix addition)
[-] (for Gosper matrix subtraction)
[*] (for Gosper matrix multiplication)
[/] (for Gosper matrix division)
While multiplication and division do actually correspond closely with the usual forms, not surprisingly, addition and subtraction may be redefined as follows.
\begin{bmatrix} a_0 & a_1 \\ a_2 & a_3 \end{bmatrix} [+] \begin{bmatrix} b_0 & b_1 \\ b_2 & b_3 \end{bmatrix} = \begin{bmatrix} gcd_{red}(a_0*b_2+b_0*a_2) & gcd_{red}(a_1*b_3+b_1*a_3) \\ gcd_{red}(a_2*b_2) & gcd_{red}(a_3*b_3) \end{bmatrix} \begin{bmatrix} 10 & 3 \\ 7 & 2 \end{bmatrix} [+] \begin{bmatrix} 22 & 9 \\ 5 & 2 \end{bmatrix} = \begin{bmatrix} 204 & 6 \\ 35 & 1 \end{bmatrix} \begin{bmatrix} a_0 & a_1 \\ a_2 & a_3 \end{bmatrix} [-] \begin{bmatrix} b_0 & b_1 \\ b_2 & b_3 \end{bmatrix} = \begin{bmatrix} gcd_{red}(a_0*b_2-b_0*a_2) & gcd_{red}(a_1*b_3-b_1*a_3) \\ gcd_{red}(a_2*b_2) & gcd_{red}(a_3*b_3) \end{bmatrix} \begin{bmatrix} 10 & 3 \\ 7 & 2 \end{bmatrix} [-] \begin{bmatrix} 22 & 9 \\ 5 & 2 \end{bmatrix} = \begin{bmatrix} 104 & 3 \\ 35 & 1 \end{bmatrix}NOTE: Let the resultant matrix equal
\begin{bmatrix} m_0 & m_1 \\ m_2 & m_3 \end{bmatrix}
The resultant matrix does NOT represent a continued fraction - the determinant is not equal to 1 or -1.
Rather it serves as a placeholder for the rational values \frac{m_0}{m_2}, and \frac{m_1}{m_3}, the last two convergents for the successive approximation of the result.
gcd_{red} indicates that common factors are removed between corresponding pairs of terms m_0 and m_2, and m_1 and m_3 presenting \frac{m_0}{m_2}, and \frac{m_1}{m_3} in their simplest forms.
\begin{bmatrix} 3 & 4 \\ 2 & -1 \\ \end{bmatrix} \cdot \begin{bmatrix} 10 & 3 \\ 7 & 2 \end{bmatrix} [+] \begin{bmatrix} 1 & 3 \\ 2 & -1 \end{bmatrix} \cdot \begin{bmatrix} 22 & 9 \\ 5 & 2 \end{bmatrix} \begin{bmatrix} 58 & 17 \\ 13 & 4 \end{bmatrix} [+] \begin{bmatrix} 37 & 15 \\ 39 & 16 \end{bmatrix} = \begin{bmatrix} 211 & 83 \\ 39 & 16 \end{bmatrix} [5,2,2,3,2] = \frac{211}{39} mgosper([\frac{(3x+4)}{(2x-1)}][+][\frac{(y+3)}{(2y-1)}],[\frac{10}{7}],[\frac{22}{5}])
\begin{bmatrix} 3 & 4 \\ 2 & -1 \\ \end{bmatrix} \cdot \begin{bmatrix} 10 & 3 \\ 7 & 2 \end{bmatrix} [-] \begin{bmatrix} 1 & 3 \\ 2 & -1 \end{bmatrix} \cdot \begin{bmatrix} 22 & 9 \\ 5 & 2 \end{bmatrix} \begin{bmatrix} 58 & 17 \\ 13 & 4 \end{bmatrix} [-] \begin{bmatrix} 37 & 15 \\ 39 & 16 \end{bmatrix} = \begin{bmatrix} 137 & 53 \\ 39 & 16 \end{bmatrix} [3,1,1,19] = \frac{137}{39} mgosper([\frac{(3x+4)}{(2x-1)}][-][\frac{(y+3)}{(2y-1)}],[\frac{10}{7}],[\frac{22}{5}])
\begin{bmatrix} 3 & 4 \\ 2 & -1 \\ \end{bmatrix} \cdot \begin{bmatrix} 10 & 3 \\ 7 & 2 \end{bmatrix} [*] \begin{bmatrix} 1 & 3 \\ 2 & -1 \end{bmatrix} \cdot \begin{bmatrix} 22 & 9 \\ 5 & 2 \end{bmatrix} \begin{bmatrix} 58 & 17 \\ 13 & 4 \end{bmatrix} [*] \begin{bmatrix} 37 & 15 \\ 39 & 16 \end{bmatrix} = \begin{bmatrix} 2146 & 255 \\ 507 & 64 \end{bmatrix} [4,4,3,2,1,2,4] = \frac{2146}{507} mgosper([\frac{(3x+4)}{(2x-1)}][*][\frac{(y+3)}{(2y-1)}],[\frac{10}{7}],[\frac{22}{5}])
\frac{\begin{bmatrix} 3 & 4 \\ 2 & -1 \\ \end{bmatrix} \cdot \begin{bmatrix} 10 & 3 \\ 7 & 2 \end{bmatrix}}{\begin{bmatrix} 1 & 3 \\ 2 & -1 \end{bmatrix} \cdot \begin{bmatrix} 22 & 9 \\ 5 & 2 \end{bmatrix}} \begin{bmatrix} 58 & 17 \\ 13 & 4 \end{bmatrix} [/] \begin{bmatrix} 37 & 15 \\ 39 & 16 \end{bmatrix} = \begin{bmatrix} 174 & 68 \\ 37 & 15 \end{bmatrix} [4,1,2,2,1,3] = \frac{174}{37} mgosper([\frac{(3x+4)}{(2x-1)}][/][\frac{(y+3)}{(2y-1)}],[\frac{10}{7}],[\frac{22}{5}])
Just as the convergent method described above, using this matrix approach even allows us to achieve Gosper's perfect arithmetic by taking the terms of the continued fractions one matrix at a time and so delivering successive increasingly accurate approximations!
And both methods do so in a far more efficient - and far less complicated - manner!
Step 1:
\begin{bmatrix} 3 & 4 \\ 2 & -1 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} [+] \begin{bmatrix} 1 & 3 \\ 2 & -1 \end{bmatrix} \cdot \begin{bmatrix} 4 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 8 & 8 \\ 1 & 1 \end{bmatrix} ⇒ 8Step 2:
\begin{bmatrix} 3 & 4 \\ 2 & -1 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} [+] \begin{bmatrix} 1 & 3 \\ 2 & -1 \end{bmatrix} \cdot \begin{bmatrix} 4 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 83 & 8 \\ 16 & 1 \end{bmatrix} ⇒ [5,5,3] = \frac{83}{16}Step 3:
\begin{bmatrix} 3 & 4 \\ 2 & -1 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \end{bmatrix} [+] \begin{bmatrix} 1 & 3 \\ 2 & -1 \end{bmatrix} \cdot \begin{bmatrix} 4 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 211 & 83 \\ 39 & 16 \end{bmatrix} ⇒ [5,2,2,3,2] = \frac{211}{39}
mgosper([\frac{(3x+4)}{(2x-1)}][+][\frac{(y+3)}{(2y-1)}],[\frac{10}{7}],[\frac{22}{5}])
Examples: Try These!
Mathematics ToolBox
About the MathBoxes...
Hint: When entering mathematical expressions in the math boxes below (f, g and h), use the space key to step out of fractions, powers, etc. On Android, begin entry by pressing Enter.
Type simple mathematical expressions and equations as you would normally enter these: for example, "x^2[space]-4x+3", and "2/3[space]". For more interesting elements, use Latex notation (prefix commands such as "sqrt" and "nthroot3" with a backslash (\)): for example: "\sqrt(2)[space][space]". More?
a = -1 5 1 b = -1 5 1 c = -1 5 1 (d) -1 0 5 (e) -1 0 5 App generated by GXWeb
Timing: Key Signature:
Continued Fraction Spreadsheet Explorer
This browser-based spreadsheet uses the handsontable JavaScript library.
WolframAlpha: CAS+
Sometimes, to deal with those stubborn, hard to reach problems, you need something stronger!
The powerful Wolfram Alpha online CAS engine will answer almost anything you care to ask - within reason! From the continued fraction of pi to Solve x^2=x+1 to the population of Australia!
GeoGebra
GeoGebra offers another fast and accurate CAS alternative. You may also like to explore the GeoGebra web app.
Timing: Key Signature:
Share with QR Code
QR Codes are a great way to share data and information with others, even when no Internet connection is available. Most modern devices either come equipped with QR readers in-built, or freely available.
The default link here is the GXWeb Jigsaws and Quizzes, but you can use it as an alternative to sending your assessment data via email, web or share with others in your class. You can even use it to send your own messages!
GXWeb Jigsaws and Quizzes
Share Your Results
Enter your name:
My class:
Email to:
Session report length: 0 characters.
Continued Logarithms
Bill Gosper's historic unpublished 1972 paper not only laid the foundation for realistic continued fraction arithmetic but, in the last few pages, introduced a new "mutation on continued fractions" - (binary) continued logarithms!
In the newly dawning age of personal computers, Gosper recognised both the limitations of continued fractions in dealing with very large and very small numbers, and the possibilities for a new type of binary representation, reducing such numbers to highly accurate arrays of zeros and ones. Gosper described it as a "sort of recursive version of scientific notation" (1972).
While we might generally count ourselves lucky to know of one or two generalized continued fraction forms for most reals, this approach reveals the relatively simple processes which deliver up to five distinct forms for most numbers - in any base of your choosing!
Continued Logarithms (base b) (Gosper, 1972) are defined by
g(x) = \left\{ \begin{array}{ll} \frac{x}{b} & x\geq b \\ \frac{b-1}{x-1} & 1\lt x\lt b \\ terminate & x=1 \\ \end{array} \right.
19 = [4,2,1,1]_{cl(2)} ⇒ 2^4+\cfrac{2^4}{2^2+\cfrac{2^2}{2^1+\cfrac{2^1}{2^1}}}
\frac{21}{5} = [1,1,1]_{cl(3)} ⇒ 3^1+\cfrac{2\cdot 3^1}{3^1+\cfrac{2\cdot 3^1}{3^1}}
Construct your own Model with GXWeb
Behind the Scenes
©2023 Compass Learning Technologies ← GXWeb Showcase ← GXWeb Continued Fraction Collection ← GXWeb Continued Fraction Arithmetic