1 Concepts

1.1 Introduction

A simple continued fraction is a number of the form a+1/(b+1/(c+...)), possibly infinite. They have the convenient property that terminating the expression at some point results in a rational that is "close" to the whole expression, in the sense that there is no rational closer with a smaller denominator. For instance, 14/3 = 4 + 2/3 = 4 + 1/(3/2) = 4 + 1/(1 + 1/2). When all the numerators are 1 like this, we can simply write (4 1 2). This process will always terminate for rational numbers since it is equivalent to the Euclidean algorithm.

Real solutions to quadratic equations with integer coefficients have repeating continued fractions. For example, √2 = (1; 2 ...) which is 1 + 1/(2 + 1/(2 + ...)). Other algebraics do not have a repeating simple continued fraction.

Simple continued fractions are unique, given a few caveats. As you can see from the 14/3 example, 4 + 1/(1 + 1/2) = 4 + 1/(1 + 1/(1 + 1)), which is to say that (a b ... c) is the same as (a b ... c-1 1). Additionally, interspersed zeroes can be put in such that (a b 0 n c ...) is the same as (a b+n c ...). Lastly, the representation of negative numbers is not unique, either. If B is a [possibly infinite] continued fraction (a b c ...) then there are two ways to write -B. The first is (-a -b -c ...) and the second is (-(a+1) 1 |b|-1 |c| ...). This library prefers the second form.

Many common functions or numbers have a continued fraction representation where the numerators are not all 1s, such as the continued fraction for pi which can be written 0 + 4/(1 + 1^2/(3 + 2^2/(5 + 3^2/(7 + ...)))). Such representations are not unique.

1.2 Precision

When considered as a regular continued fraction, terminating the continued fraction at some point yields a rational n/d, called a "convergent." Then the absolute value of the difference between this rational and the value of the full continued fraction is less than one divided the product of the denominators of this convergent and the next best convergent. This factor is a worst-case scenario, most continued fractions have convergents with much better precision. In fact, the golden ratio φ = (1+√5)/2 is the worst case, constantly staying just inside the bounds. Because of this, the golden ratio is sometimes called the "most irrational" number; that is, the number that is hardest to approximate by rationals.

1.3 The Arithmetic of Continued Fractions

Continued fractions are amendable to term-at-a-time arithmetic. Suppose we have a function f(x) = (ax+b)/(cx+d), where x is a continued fraction of the form x = t + 1/x’, x’ being the rest of the continued fraction. Then when f consumes the leading term t, x goes to t+1/x’, which after multiplication to get f back in the same form, has updated the coefficients. If the continued fraciton x is in standard form, then we have guarantees about every term except the first nonzero term, namely, that it will lie somewhere between 1 and infinity (a terminated continued fraction). Then if the limits of f as x goes to 1 and as x goes to infinity agree it does not matter what the value of x’ is as the leading term of f is already determined. We can take a quotient term out of the function, and f then goes to t + 1/f’.

For further details, reference the MIT HAKMEM memo 239 (Gosper).

1.4 Purpose

Because of the term-at-a-time aspect of continued fraction arithmetic, calculating terms and quotients proceeds without unnecessary calculation. Because of the precision guarantees, calculation can be terminated when the desired precision is exceeded. Combining these facts give us a picture of exact arithmetic of rationals and irrationals which only calculate as far as needed and yield the rational with the smallest denominator possible for the given precision.