 Continued Fractions

Imagine that you're standing at the top of a sloped road, about to skate down, and you want to describe how steep it is. You could state the angle, expressed in degrees, radians, or turns, but in practice architects and engineers express slopes in rise over run, saying the road loses 100m per km or the stairway climbs 3:4.

Now imagine that you're looking at that stairway from the side, and the ratio of rise to run forms a rectangle. Multiplying rise and run calculates the area of the rectangle, but dividing them calculates the tangent of the diagonal, and thus indicates the diagonal angle.

Expressing an angle as rise/run works best if we normalize the run to a value of 1 - that way, we can easily compare two angles to see which is steeper. But the angle still has to be expressed as a real number, for instance as a decimal in base 10.

Here's a way to express that ratio without choosing any particular base. We start by constructing a square with the same width as the height of our rectangle, and we try to cover the rectangle with the square, as shown here: In this example, two of those squares (marked a₀) fit, with a chunk left over. So we do the same thing, but this time, the square's height is set to its width, not the other way around. Only one of those new squares (marked a₁) fits, with a smaller chunk left over. So we continue, adding one a₂ square and finally, two a₃ squares to fill the original rectangle.

It turns out that that sequence - 2 a₀ squares, 1 a₁ square, 1 a₂ square, and 2 a₃ squares - completely and uniquely defines that rectangle, as long as we keep each square inside the rectangle. But if we're willing to trespass beyond its boundaries, we can subtract squares to fill the rectangle. This time, we used a third a₀ square but subtracted the a₁ and a₂ squares. Now the sequence is {3; -2, 2}: shorter! (We could also have used a third red square and subtracted the two brown squares, but that wouldn't have been an improvement.)

A continued fraction (CF) is a way of expressing any real number in a unique and base-free way. It is an expression of the form

r = a0 + 1/(a1 + 1/(a2 + 1/(a3 + 1/(a4 + 1/(a5 + 1/(a6 + 1/(a7 + …

where r is the real number to be represented, a₀ is an integer - the integer part of r, which might be negative or zero - and a₁…aₙ are non-zero positive integer terms in a converging approximation.

It turns out that these CFs have several interesting properties. As mentioned, each number has an essentially unique CF (it can be rewritten in a couple of closely related ways). Rational numbers have terminating CFs, while irrationals don't. And the CFs converge: adding more terms results in a closer approximation.

This presentation is going to explore the use of signed numbers - the aₙ may be positive or negative integers - since Musa is so good at writing negative numbers. One hope is that the series would converge faster; another is that two series may be more easily compared. I'll call the CFs above positive (since they restrict themselves to positive integers) and common when the terms are added. They're also called simple because the numerators are all 1 - I won't consider non-simple CFs.

Let's start with an example: the number of inches in a meter. An inch is defined as 2.54cm, so there are 100/2.54 inches in a meter. We can make that 10000/254 to express it as the quotient of two integers: a rational number. That's 39.370078… in decimal (the ellipsis … indicates that there are more digits to the right).

As a CF, start with the integer part 39 as a first approximation. Calculate the remainder 254×39 = 9906, 10000-9906 = 94. So

10000/254 = 39 + (94/254) = 39 + 1/(254/94)

Now we calculate that last fraction, 254/94, the same way - it's 2.7021276…, or 2 + 66/94:

10000/254 = 39 + 1/(2 + 66/94) = 39 + 1/(2 + 1/(94/66))

94/66 = 1.42 or 1 + 28/66:

10000/254 = 39 + 1/(2 + 1/(1 + 1/(66/28)))

66/28 = 2.3571428 or 2 + 10/28:

10000/254 = 39 + 1/(2 + 1/(1 + 1/(2 + 1/(28/10))))

28/10 = 2.8 or 2 + 8/10:

10000/254 = 39 + 1/(2 + 1/(1 + 1/(2 + 1/(2 + 1/(10/8)))))

10/8 = 1.25 or 1 +2/8:

10000/254 = 39 + 1/(2 + 1/(1 + 1/(2 + 1/(2 + 1/(1 + 1/(8/2))))))

8/2 = 4:

10000/254 = 39 + 1/(2 + 1/(1 + 1/(2 + 1/(2 + 1/(1 + 1/(4))))))

The sequence {a₀; a₁, a₂,…} (by convention, a₀ is followed by a semicolon) thus turns out to be {39; 2, 1, 2, 2, 1, 4}. That's the positive CF of 10000/254.

We calculated the value of 10000/254 as 39.370078… in decimal. If we were now to calculate the value of 10001/254, it's 39.374015…, a larger number. Of course! The numerator is larger, and the denominator is the same.

But we might wonder about 9998/253, for example. Is it larger or smaller than 10000/254? Hard to tell in rational form: the numerator is smaller, but so is the denominator. But it's very easy to see in decimal form: 9998/253 is 39.417786…, slightly larger than 10000/254.

Now here's the positive CF of 9998/253:

9998/253 = 39 + 1/(1 + 1/(1 + 1/(13 + 1/(1 + 1/(1+ 1/(4))))))

or {39; 1, 1, 13, 1, 1, 4}

Comparing {39; 2, 1, 2, 2, 1, 4} to {39; 1, 1, 13, 1, 1, 4}, it would seem that the former is larger. They first differ in the a₁ term: 2 is larger than 1. But we already know the second is larger, so there's a problem.

You can't just naively compare the sequences to determine ordering. This is because every odd term is in fact a denominator, and a larger denominator implies a smaller quotient. Referring back to the rectangle diagrams at the top, you can't mix width with height: taller implies a steeper diagonal, but wider implies a shallower diagonal.

There's a simple low-tech solution. We could write CFs with a semicolon after every even term, and we just have to remember to reverse the comparison when the terms end in commas: a larger denominator means a smaller quotient. But can we do better?

Let's try signed CFs. They use the closest integer approximation, even if it's greater. In other words, they round instead of truncating. The remainder might then turn out to be negative instead of positive. Quotients halfway in between two integers round away from zero. Go back to the first step:

10000/254 = 39 + 1/(254/94)

This time, we're going to point out that the best integer approximation of 254/94 is not 2 - it's 3. So we're going to express 2.7021276… as 3 - 28/94, with a negative remainder.

10000/254 = 39 + 1/(3 - 1/(94/28)), or
10000/254 = 39 + 1/(3 + 1/(-94/28))
10000/254 = 39 + 1/(3 + 1/(-3 + 1/(-28/10)))
10000/254 = 39 + 1/(3 + 1/(-3 + 1/(-3 + 1/(-10/2))))
10000/254 = 39 + 1/(3 + 1/(-3 + 1/(-3 + 1/(-5))))

So the signed CF of 10000/254 is {39; 3, -3, -3, -5}. It's two terms shorter than the positive form; it converges more quickly. In the positive - truncated - calculation, each remainder was less than 1; in the signed - rounded - form, each remainder is less than ±½. And of course, in Musa it's very easy to write the negative remainders.



And when we compare the signed CFs, {39; 3, -3, -3, -5} looks smaller than {40; -2, -14, 2, 4}, so this comparison works.

Let's try some other tricks. One is to replace addition with subtraction in the chain, so that each term detracts from the previous approximation. That might obviate the need to reverse comparisons.

r = a0 - 1/(a1 - 1/(a2 - 1/(a3 - 1/(a4 - 1/(a5 - 1/(a6 - 1/(a7 - 1/(a8 - …

We'll call this a negative CF, but we'll still round to the nearest integer and use a signed remainder, so it's a negative signed CF (NSCF).

10000/254 = 39 - 1/(-254/94)
10000/254 = 39 - 1/(-3 - 1/(94/28))
10000/254 = 39 - 1/(-3 - 1/(3 - 1/(-28/10)))
10000/254 = 39 - 1/(-3 - 1/(3 - 1/(-3 - 1/(5))))

So the negative signed CF of 10000/254 is {39; -3, 3, -3, 5}.

9998/253 = 40 - 1/(253/122)
9998/253 = 40 - 1/(2 - 1/(-122/9))
9998/253 = 40 - 1/(2 - 1/(-14 - 1/(-9/4)))
9998/253 = 40 - 1/(2 - 1/(-14 - 1/(-2 - 1/(-4))))

The negative signed CF of 9998/253 is {40; 2, -14, -2, -4}, and the comparison is correct as it stands, with no reverse comparisons.

But a comparison between NSCFs doesn't always work. For example, the NSCF of 3/4 is {1; 4}, while the NSCF of 5/4 is {1; -4}.

It turns out that when the two terms being compared have different signs, you have to reverse the comparison. In the comparison of 3/4 with 5/4, note that in the second term - the first one they differ in - the two terms have different signs: +4 and -4. So we have to reverse the comparison and recognize that the one with +4 is actually smaller: 3/4 < 5/4. If one NSCF is shorter, you can pad it with zeroes, but those zeroes also count as a different sign: -x > 0 > +x.

In fact, the comparison function is exactly ƒ(x) = -1/x (with ƒ(0) defined as 0), paralleling the chaining function between terms. On this graph, you can see that all the negative numbers are worth more than all the positive numbers, even though the sort order is normal between two numbers on the same side. And zero is between the two sides.

And that fixes the last problem! So we now have a notation - negative signed continued fractions - that has the following properties:

• Every real number has a unique NSCF: a sequence of integers. (Only the first can be 0, and the last can never be 1.)
• Rational numbers have terminating NSCFs.
• The NSCFs of irrationals don't terminate, but those that repeat represent quadratic irrationals.
• They're convergent: more terms gives you a closer approximation (and faster than decimals).
• You can compare two NSCFs by comparing each term in sequence, but if the two terms differ in sign, the comparison is reversed: -x > 0 > +x.
• The complement (negation) of a NSCF just complements all the digits.
• The reciprocal of a NSCF just adds a 0 term to the beginning if there isn't one there already, and removes it if there is. And the signs change.
• NSCFs that differ by integers just change the first term.

Because Musa writes negative numbers without a minus sign, it's easier to keep track of the polarity than with the traditional notation. Here's the NSCF{39; -3, 3, -3, 5} written in Musa.



And here's a toy you can use to play around with NSCFs of rational numbers:

Numerator: Denominator:

 < Numerals Arithmetic Notation >