©2020 Compass Learning Technologies ← Live Mathematics on the Web ← GXWeb Showcase →GXWeb Fractured Functions
GXWeb Fractured Functions
Saltire Software, home of Geometry Expressions and GXWeb
Download a Geometry Expressions Model for Fractured Fractions
Symbolic computations on this page use Nerdamer Symbolic JavaScript to complement the in-built CAS of GXWeb
Wikipedia: Generalized Continued Fractions
Continued Fraction Arithmetic by Ross Dempsey
An Introduction to Continued Fractions by Dr Ron Knott
GXWeb Fractured Fractions OR try a simpler version of this task.
Online Mathematics Research: The Ramanujan Machine
Introduction
As we have seen, continued fractions come in more than one flavour. Finding a finite (closed) form for the real number represented by a continued fraction can be very useful in understanding the patterns and applications involved.
For rational numbers, this is easy, since the continued fraction is finite. For most irrationals, the closed form is much harder, but not for quadratic irrationals, which are periodic.
For any periodic continued fraction, we need to isolate the periodic part and use this to form a quadratic equation. For example...
[1,2,3,1,2,3,1,2,3...]=1+12+13+11+12+13+... x=1+12+13+1x=4+√(37)7This may also be expressed in another form - using matrices!
Now we dig more deeply into the non-simple form - generalised continued fractions.
π≈41+123+225+327+429+5211+6213+⋯
e≈3−14−25−36−47−58−69+⋯
But where do these remarkable fractions come from? Calculating simple continued fractions is relatively easy, but these monsters?
Here, too, is where we see the true power of continued fractions in helping us to better understand the nature of irrational numbers. Even for simple continued fractions, the sequences which define all but the quadratic irrationals remain as random and unpredictable as their decimal counterparts - such numbers throughout history have been described as essentially unknowable.
Generalised continued fractions, however, reveal that most if not all irrationals ARE knowable - they can be expressed in forms that are predictable and can readily be calulated to any desired degree of accuracy. Students learning about irrational numbers should be introduced to continued fractions so that they may understand them better, not be put off with a wave of the hand and reference to them as, more or less, simply mysterious entities.
Once again, if mathematics is to be taught and learned as a search for patterns and relationships, then the multitude of patterns and relationships to be found within continued fractions should be part of that journey.
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])?
Negative (or Reversal) Continued Fractions
Before considering general continued fractions in detail, a note about the continued fractions of negative numbers.
107=[1,2,3]=1+12+13Begin by observing that
−107≠−1−1−2−1−3(=−25)AND
−107≠1−12−13(=25)However
−107=[−1,−2,−3]=−1+1−2+1−3and (perhaps surprisingly?)
107=[2,2,4]−=2−12−14
Did you know that there are TWO classical forms for continued fractions? I only found this out recently.
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.
To convert a real number (n) to a continued fraction is easy!
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 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 a0), 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 (1Tail) - this should give a number greater than or equal to 1.
Step 4: Take the integer part of this reciprocal value (a1=floor(1Tail)): This is your next index - call it a1, and a0+1a1 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 a0), 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 (1Tail) - this should give a number greater than or equal to 1.
Step 4: Take the ceiling of this reciprocal value (a1=ceil(1Tail)): This is your next index - call it a1, and a0+1a1 the next convergent.
Step 5: Return to Step 2 and repeat the process...
107=[1,2,2,1]=1+12+12+11 (Enter 10/7 or 1,2,3 or 1,2,2,1)
[107]−=[2,2,4]−=2−12−14 (Enter [10/7]^- or [2,2,4]^-
or [10/7]{neg} or [2,2,4]{neg})4330=[1,2,3,4]=1+12+13+14 (Enter 43/30 or 1,2,3,4)
[4330]−=[2,2,5,2,2,2]−=2−12−15−12−12−12 (Enter [43/30]^- or [2,2,5,2,2,2]^-
or [43/30]{neg} or [2,2,5,2,2,2]{neg})Try a few more examples and see if you can see a pattern...
HINT: It helps if your simple continued fraction form has an EVEN number of terms!
Converting to the Negative Form
With thanks to Morier-Genoud and Ovsienko (2019)
Let r and s be two coprime positive integers, and assume that r>s. The rational number rs has unique expansions
rs=a1+1a2+1a3+1...a2m =c1−1c2−1c3−1...ckwhere ai≥1 and ci≥2 for all i. The first is called a simple continued fraction and the second, a negative or reversal continued fraction.
Note that we can always assume a simple continued fraction has an even number of terms since every such continued fraction can be expressed in both a compact form (with last term not equal to 1) and an expanded form:
[a1,a2,...,an]=[a1,a2,...,an−1,1]Then the terms of a negative or reversal continued fraction may be derived from those of the equivalent simple form as follows:
[c1,c2,c3,...,ck−1,ck]= [a1+1,2 (repeated a2−1 times)...,a3+1,2 (repeated a4−1 times)...,a2m−1+1,2 (repeated a2m times)]
Negative Terms in a Continued Fraction
As noted by Knott, LaGrange points out that it is a simple matter of algebra to show that we can remove subtractions in favour of addtions.
Wherever there is a subtraction, "push" it into the rest of the CF making positive numbers into negatives. We use C to represent the rest of a CF which may be empty or consist of one or more terms:
a−1b+C=a+−1b+C=a+1−b−CThen if
C=1c+1d+1e+...note that a negative value in a numerator ONLY changes the signs of the subsequent pair of numerator and denominator - this then flows on through the remaining terms to deliver an equal result without requiring any further sign changes.
a−1b+1c+1d+1e+... =a+−1b+1c+1d+1e+... = a + \frac{1}{-b-\frac{1}{c+\frac{1}{d + \frac{1}{e+...}}}} = a + \frac{1}{-b-\frac{1}{c+\frac{1}{d + \frac{1}{e+...}}}}Observe from the linked example that this holds for any occurrence within the terms of the continued fraction.
And for a pair of consecutive negative numerators?
a + \frac{1}{b-\frac{1}{c-\frac{1}{d + \frac{1}{e+...}}}} = a + \frac{1}{b+\frac{-1}{c+\frac{-1}{d + \frac{1}{e+...}}}} = a + \frac{1}{b+\frac{1}{-c+\frac{1}{d + \frac{1}{e+...}}}}Simpler still!
Each consecutive pair of negative numerator values results in just a single negative leading term (denominator) in the second level. All other negative values cancel.
A string of sequential negative numerators, then, will result in alternating positive and negative leading terms.
Some Matrix Fraction Magic
As seen already, continued fractions can be represented in matrix form, offering some interesting possibilities - and applicable to both simple and generalised continued fractions.
1. Continued Fraction Matrices
The most-commonly documented approach involves the product of 2 x 2 matrices.
a_0+\cfrac{b_0}{a_1 + \cfrac{b_1}{a_2 + \cfrac{b_2}{a_3 + \cfrac{b_3}{a_4...}}}} = \begin{bmatrix} a_0 & b_0 \\ 1 & 0 \end{bmatrix}\cdot \begin{bmatrix} a_1 & b_1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_2 & b_2 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_3 & b_3 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_4 & 1 \\ 1 & 0 \end{bmatrix}...
For example, arithmetic operations can be readily expressed.
[1,2,3,1,2,3,1,2,3,1...] =>1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{1...}}}}}}\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} \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} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ... x = 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{x}}} = \frac{4+\sqrt(37)}{7} If... \sqrt{37}= 6+ \cfrac{1}{12+\cfrac{1}{12+\cfrac{1}{12+\cfrac{1}{12+...}}}}=> \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} ... Then... \frac{4+\sqrt(37)}{7} = \begin{bmatrix} 1 & 4 \\ 0 & 7 \\ \end{bmatrix} \cdot \sqrt{37} => \begin{bmatrix} 1 & 4 \\ 0 & 7 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 12 & 1 \\ 1 & 0 \\ \end{bmatrix} ...Even less predictable ones:
[2,2,3,1,1,2,3,1,1,2,3...] =>2 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{1}{3...}}}}}} \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 2 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \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} ... x-1 = 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{x-1}}}} x-1 = 1 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{x-1}{x}}} = \frac{4+\sqrt(11)}{3} If...\sqrt{11}= 3+ \cfrac{1}{3+\cfrac{1}{6+\cfrac{1}{3+\cfrac{1}{6+...}}}}=> \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} ... Then... \frac{4+\sqrt(11)}{3} = \begin{bmatrix} 1 & 4 \\ 0 & 3 \\ \end{bmatrix} \cdot \sqrt{11} => \begin{bmatrix} 1 & 4 \\ 0 & 3 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 1 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} 6 & 1 \\ 1 & 0 \\ \end{bmatrix} ...
2. Tridiagonal Matrix Continued Fractions
Two alternative approaches involve larger square (tridiagonal) matrices. (eg Frommer, Kahl and Tsolakis (2021) and Qi, Wen Guo and Lim (2020))
Let \ M = \begin{bmatrix} a_0 & b_0 & 0 & 0 & 0 \\ -1 & a_1 & b_1 & 0 & 0 \\ 0 & -1 & a_2 & b_2 & 0 \\ 0 & 0 & -1 & a_3 & b_3 \\ 0 & 0 & 0 & -1 & a_4\end{bmatrix}Then taking the inverse of M, the first ([1,1]) term gives the reciprocal of the final convergent of the continued fraction:
\frac{1}{inv(M)[1,1]} = a_0+\cfrac{b_0}{a_1 + \cfrac{b_1}{a_2 + \cfrac{b_2}{a_3 + \cfrac{b_3}{a_4}}}}A second approach involves the determinants of two square matrices, p and q as follows:
a_0+\cfrac{b_0}{a_1 + \cfrac{b_1}{a_2 + \cfrac{b_2}{a_3 + \cfrac{b_3}{a_4}}}} = \frac{det(p)}{det(q)}
Some expected relationships...
And even some unexpected ones!
Tap on the matrix examples above and follow the directions. Then just press h (at the end, you may need to press the TextBoxes button to lay out the result correctly).
3. Matrix as Mediant: Building the Stern-Brocot Tree
Returning to 2 x 2 matrices, we find another surprisingly simple and powerful matrix approach to building the Stern-Brocot Tree (van der Poorten van der Poorten and Wildberger), and consequently, listing all possible rationals.
We begin by viewing 2 x 2 matrices in a new way, defining the mediant:
\begin{bmatrix} a & b \\ c & d \end{bmatrix} => \frac{a}{c} ⊕ \frac{b}{d} = \frac{a+b}{c+d}Then the familiar identity matrix becomes
\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} =>\frac{1}{0} ⊕ \frac{0}{1} = \frac{1+0}{0+1} = \frac{1}{1}Now we define two matrices, which will serve as left (L) and right (R) steps for our tree:
L = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \ and \ R = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}Then any term of our Stern-Brocot Tree can be represented by a matrix
M = \begin{bmatrix} a & b \\ c & d \end{bmatrix}with parents \frac{a}{c} and \frac{b}{d} and determinant 1. Such a matrix can serve as the parent for two further matrices:
M \cdot L = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \ and \ M \cdot R = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} M\cdot L = \begin{bmatrix} a+b & b \\ c+d & d \end{bmatrix} \ and \ M\cdot R = \begin{bmatrix} a & a+b \\ c & c+d \end{bmatrix} M\cdot L => \frac{a+2\cdot b}{c+2\cdot d} \ and \ M\cdot R => \frac{2\cdot a+ b}{2\cdot c+ d}
Beginning with our identity matrix
M = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} => \frac{1+0}{0+1} = \frac{1}{1}Notice the parents of \frac{1}{1} are \frac{0}{1} and \frac{1}{0}?
We quickly see the effects of a Left and Right step:
M \cdot L = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \ and \ M \cdot R = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} M\cdot L = \begin{bmatrix} 1+0 & 0+0 \\ 0+1 & 0+1 \end{bmatrix} \ and \ M\cdot R = \begin{bmatrix} 1+0 & 1+0 \\ 0+0 & 0+1 \end{bmatrix} M\cdot L = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \ and \ M\cdot R = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} * M\cdot L => \frac{1+0}{1+1} \ and \ M\cdot R => \frac{1+ 1}{0+ 1} M\cdot L => \frac{1}{2} \ and \ M\cdot R => \frac{2}{1}Line * shows that the parents of \frac{1}{2} are \frac{0}{1} and \frac{1}{1} and the parents of \frac{2}{1} are \frac{1}{1} and \frac{1}{0}?
Refer back to the section Building the Fraction Trees to see this process in more detail, and try some for yourself!
See a live demo?
Play more with continued fractions?
Quadratic Continued Fractions
Before we plunge more deeply into the dark and mysterious world of transcendental continued fractions, we should revisit something much more familiar - the humble quadratic!
Begin with the simplest of quadratic equations: x^2=m for some number, m.
Now any value m can be expressed in terms of its difference from a perfect square: m=a^2+b
For example, 7=2^2+3, and 11=3^2+2. Note that this is not necessarily unique: 11 can also equal 2^2+7. We could also always choose to use 1^2 (= 1) and m - 1.
We can now apply a difference of two squares to produce a continued fraction form for the \sqrt{m}:
x^2 = m
x^2 = a^2+b
x^2 - a^2 = b
(x - a)\cdot (x + a) = b
x - a = \frac{b}{a + x}
x = a + \frac{b}{a + x}
x = a + \cfrac{b}{a + a + \cfrac{b}{a + a + \cfrac{b}{a + a + ...}}}
x = a + \cfrac{b}{2\cdot a + \cfrac{b}{2\cdot a + \cfrac{b}{2\cdot a + ...}}}
Think about and explore this simple form. Consider, for example, the case where b=1 - those numbers which are one more than a perfect square, such as 5, 10, 17...
For such numbers, this method gives us the simple continued fraction form immediately. For example, since 10 = 3^2 + 1, then
\sqrt{10} = 3 + \cfrac{1}{6 + \cfrac{1}{6 + \cfrac{1}{6 + ...}}}
We can readily predict that any number m one more than a perfect square a^2 will have \sqrt{m} = [a, 2\cdot a, 2\cdot a, 2\cdot a...].
Further, consider a number which is, say, 2 more than a perfect square: m = a^2 + b, such as 11 = 3^2+2.
Our method predicts that
\sqrt{11} = 3 + \cfrac{2}{6 + \cfrac{2}{6 + \cfrac{2}{6 + ...}}}
But we can readily show that, in simplified form, \sqrt{11} = [3, 3, 6, 3, 6, 3, 6...].
Is there a connection? Is there a way to use our very simple difference of two squares method to quickly and easily predict the simplified continued fraction form for at least some integers? Explore!
Now consider a general (monic) quadratic equation (any quadratic can be made monic by dividing through by the leading term).
x^2+b\cdot x + c = 0
x \cdot (x+b) = -c
x = \frac{-c}{b+x}
x = \cfrac{-c}{b-\cfrac{c}{b-\cfrac{c}{x}}}
So within every quadratic equation lies a hidden continued fraction! But, just as not every quadratic has real solutions, so not all of these quadratics converge to a real value in their continued fraction form. Tap above to try some for yourself...
You might also explore the metallic means x=a + \cfrac{1}{x} => x^2=a\cdot x+1 => \frac{(a+\sqrt(4+a^2)}{2} and the noble numbers x=a + \cfrac{1}{1-a+x} => (2\cdot (x-a)+1)^2 = 5 => \frac{(\sqrt(5)+2a-1)}{2} (Try different values for a using the a-slider and then press f(x)!)
Euler and his Numbers
While certain such generalised continued fractions have been known for centuries, important work was done by the great Leonhard Euler, who developed a formula which transformed numerical sequences into continued fractions. Various such sequences were known for common irrationals, often leading to multiple continued fraction forms. For example...
e^x = \frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \cdots = \cfrac{1}{1 - \cfrac{x}{1+x- \cfrac{\frac{x}{2}}{1+\frac{x}{2} - \cfrac{\frac{x}{3}}{1+\frac{x}{3} - \cdots}}}} = \cfrac{1}{1 - \cfrac{x}{1+x- \cfrac{1x}{2+x - \cfrac{2x}{3+x - \cdots}}}}
Note that such forms were often not efficient and would converge very slowly to their final value (in some cases, requiring thousands of repetitions!). However, a little patience, some algebraic manipulation - and perhaps a dash of insight, or even genius - could bend these forms to better ones...
e = 2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{2}{3 + \cfrac{3}{4 + \cdots}}}}
A related form follows similarly:
log(1+\frac{x}{y}) = \frac{x^1}{1!} - \frac{x^2}{2!} + \frac{x^3}{3!} - \frac{x^4}{4!} + \cdots = \cfrac{2\cdot x}{2\cdot y + x - \cfrac{(1\cdot x)^2}{3\cdot (2\cdot y + x) - \cfrac{(2\cdot x)^2}{5\cdot (2\cdot y + x) - \cfrac{(3\cdot x)^2}{7\cdot (2\cdot y + x) - \cdots}}}}
log(2) = log(1+1) = \frac{1}{1} - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + \cdots = \cfrac{1}{1 - \cfrac{1}{1 - \cfrac{4}{1 - \cfrac{9}{1 - \cdots}}}}
Continued Fraction Arithmetic
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 \frac{10}{7} + \frac{22}{5}.
But for those convoluted rationals and especially those infinite irrationals? Well... it was made for such as these!
Continued Logarithms
While continued fractions may formally trace their origins to the time of Euclid, continued (binary) logarithms owe their inception to Bill Gosper in his 1972 unpublished paper on continued fraction arithmetic.
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).
This exploration introduces just a taste of the wonderful research of the past decade, exploring these unusual mathematical creatures. The particular focus here is on the multiple continued fraction-like representations for real numbers made explicit through continued logarithms.
While we count ourselves lucky to know of one or two generalized continued fraction forms for most reals, this exploration reveals the relatively simple processes which deliver five distinct forms for most numbers!
Simple Continued Fractions may be defined as follows:
f(x) = \left\{ \begin{array}{ll} (x-1) & x\geq 1 \\ \frac{1}{x} & 0\lt x\lt 1 \\ terminate & x=0 \\ \end{array} \right.
Count the number of times we encounter x ⇒ x - 1 before we either reciprocate or terminate. These counts are the terms [a_0, a_1,...] of our continued fraction.
Continued Logarithms (base b) (Gosper, 1972) are defined in a similar way 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.
For x \geq b, divide by b until the result lies between 1 and b. Count the number of divisions. Continue until you reach 1.
For 1 < x < b, subtract 1 from base b then divide by (x-1). Repeat until the result is equal to 1 (and terminate) or greater than or equal to b (and start dividing by b again)..
The continued logarithm for 19 => [1,1,1,1,0,1,1,0,1,0,1]_{cl(2)} => [4,2,1,1]_{cl(2)}
19 = 2^4+\cfrac{2^4}{2^2+\cfrac{2^2}{2^1+\cfrac{2^1}{2^1}}} = 16+\cfrac{16}{4+\cfrac{4}{2+\cfrac{2}{2}}}
The continued logarithm for \frac{21}{5} => [1,0,1,0,1]_{cl(3)} => [1,1,1]_{cl(3)}
\frac{21}{5} = 3^1+\cfrac{2\cdot 3^1}{3^1+\cfrac{2\cdot 3^1}{3^1}} = 3+\cfrac{6}{3+\cfrac{6}{3}}
Pieces of Pi
Now consider the well-known relationship relating the arctan function with \pi: tan^{-1}(1) = \frac{\pi}{4} \approx 0.7854.
tan^{-1}(\frac{x}{y}) = \cfrac{x}{1y + \cfrac{(1x)^2}{3y + \cfrac{(2x)^2}{5y + \cfrac{(3x)^2}{7y + \cdots}}}}
tan^{-1}(1) = \frac{\pi}{4} = \cfrac{1}{1 + \cfrac{(1)^2}{3 + \cfrac{(2)^2}{5 + \cfrac{(3)^2}{7 + \cdots}}}} 4\cdot tan^{-1}(1) = \pi = \cfrac{4}{1 + \cfrac{(1)^2}{3 + \cfrac{(2)^2}{5 + \cfrac{(3)^2}{7 + \cdots}}}}
Can you see how simply this expansion of \frac{\pi}{4} is transformed to the expansion of \pi shown above?
Not so AbSurd After All
The nth root of any positive number z^m can be expressed by restating z = x^n + y, resulting in the following result. Tap on the continued function to try different values.
\sqrt[n]{z^m} = \sqrt[n]{(x^n+y)^m} = x^m + \cfrac{my}{nx^{n-m} + \cfrac{(n-m)y}{2x^m + \cfrac{(n+m)y}{3nx^{n-m} + \cfrac{(2n-m)y}{2x^m + \cfrac{(2n+m)y}{5nx^{n-m} + \cfrac{(3n-m)y}{2x^m + \cdots}}}}}}
The cube root of two (2^{1/3} or \sqrt[3]{2} \approx 1.259921\cdots ): x = 1, y = 1, x^n+y=2 with n = 3 and m = 1: \sqrt[3]{2} = 1 + \cfrac{1}{3 + \cfrac{2}{2 + \cfrac{4}{9 + \cfrac{5}{2 + \cfrac{7}{15 + \cfrac{8}{2 + \cdots}}}}}}
For the cube root of two, you might also like to try thinking of it as the cube root of 128^{1/7} with x = 5 and y = 3. Tap on the continued function above to try these and other values!
What about the basis for the modern (well-tempered) musical scale, \sqrt[12](2)?
Visualise Continued Fractions with GXWeb
About the MathBoxes...
Hint: When entering mathematical expressions in the math boxes below (f(x), g(x) and h(x)), 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]". Learn More?
Use the Continued Fractions button or enter coordinates in the text boxes to explore (and even ♬ listen to!) your own continued fractions.
| About Continued fractions are awesome. Every real number, rational and irrational, can be represented by a continued fraction - the rational ones are finite, of course, but both finite and infinite offer some wonderful patterns and opportunities to explore! Use the f(x) MathBox or the x-value box above to enter a value to express as a continued fraction. You can even share your current continued fraction as a QR Code or use them to encrypt short messages! For example, try 43 \over 30, \pi, \phi or even \frac{225}{157}. About Use the Table button to display function table values for f(x), g(x) or h(x). For example, try x^2-x-1 and \frac{d}{dx}(x^2-x-1). Reference: Nerdamer Symbolic JavaScript Use the CAS Evaluate option from the dropdown menu above to solve an expression or equation in the f(x) MathBox. Click on the following to try:
Notice the difference between these two results? Adding an extra ,x at the end forces an exact rather than a numeric result! And some more to try (just click on each line):
Use the Solve option from the dropdown menu above to solve an expression or equation in the f(x) MathBox, or enter solve(an equation) in f(x), g(x) or h(x). Use the Derivative option from the dropdown menu above to differentiate a function in the f(x) MathBox, or enter d/dx(a function) in f(x), g(x) or h(x). Use the Integral option from the dropdown menu above to integrate a function in the f(x) MathBox, or enter int(a function) in f(x). For definite integrals, perform the integration as described using the dropdown, and enter end values when requested. Try \int(x^2-x-1,0,x) for example. Use the x box or slider to vary this. Display the tangent (or Normal) of f(x) for the current value of x using the Tangent/Normal button, or enter tangent (or tngnt) or normal directly into the graph mathBoxes - set the desired x-value first. Encryption? Enter a brief message to encrypt ⇓ Or enter a list of numbers to decrypt ⇓ Graph Controls |
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 offers another fast and accurate CAS alternative. Use the button above ⇑ for quick computation, or you may like to explore the full GeoGebra web app. ⇒
Continued Fraction Spreadsheet Explorer
This browser-based spreadsheet uses the handsontable JavaScript library.
Share with Different Senses
Geometry Expressions Showcase
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 Geometry Expressions Showcase, but you can use it as an alternative to sending your assessment data via email, web or Google Cloud. You can even use it to send your own messages!
Why not Listen to your Continued Fraction?
Construct your own Model with GXWeb
Behind the Scenes
©2020 Compass Learning Technologies ← Live Mathematics on the Web ← GXWeb Showcase ← GXWeb Fractured Functions