Continued Fractions
Continued fractions have been a fascinating and useful tool in mathematics
for well over three hundred years. Axiom implements continued fractions
for fractions of any Euclidean domain. In practice, this usually means
rational numbers. In this section we demonstrate some of the operations
available for manipulating both finite and infinite continued fractions.
It may be helpful if you review
Stream to remind yourself of some of the
operations with streams.
The ContinuedFraction domain is a
field and therefore you can add, subtract, multiply, and divide the
fractions. The
continuedFraction operation
converts its fractional argument to a continued fraction.
This display is the compact form of the bulkier
3 + 1
---------------------------
7 + 1
-----------------------
15 + 1
------------------
1 + 1
--------------
25 + 1
---------
1 + 1
-----
7 + 1
-
4
You can write any rational number in a similar form. The fraction will
be finite and you can always take the "numerators" to be 1. That is, any
rational number can be written as a simple, finite continued fraction of
the form
a(1) + 1
---------------------------
a(2) + 1
-----------------------
a(3) + 1
.
.
.
1
-----------------
a(n-1) + 1
---------
a(n)
The a(i) are called partial quotients and the operation
partialQuotients creates a
stream of them.
By considering more and more of the fraction, you get the
convergents. For example, the
first convergent is a(1), the second is a(1)+1/a(2) and so on.
Since this ia a finite continued fraction, the last convergent is the
original rational number, in reduced form. The result of
approximants is always an infinite
stream, though it may just repeat the "last" value.
Inverting c only changes the partial quotients of its fraction by
inserting a 0 at the beginning of the list.
Do this to recover the original continued fraction from this list of
partial quotients. The three argument form of the
continuedFraction operation takes
an element which is the whole part of the fraction, a stream of elements
which are the denominators of the fraction.
The streams need not be finite for
continuedFraction. Can you guess
which irrational number has the following continued fraction? See the end
of this section for the answer.
In 1737 Euler discovered the infinite continued fraction expansion
e - 1 1
----- = ---------------------------
p 2 + 1
-----------------------
6 + 1
------------------
10 + 1
--------------
14 + ...
We use this expansion to compute rational and floating point
approximations of e. (For this and other interesting expansions,
see C. D. Olds, Continued Fractions, New Mathematical Library,
Random House, New York, 1963 pp.134-139).
By looking at the above expansion, we see that the whole part is 0
and the numerators are all equal to 1. This constructs the stream of
denominators.
Therefore this is the continued fraction expansion for (e-1)/2.
These are the rational number convergents.
You can get rational convergents for e by multiplying by 2 and adding 1.
You can also compute the floating point approximations to these convergents.
Compare this to the value of e computed by the
exp operation in
Float.
In about 1658, Lord Brouncker established the following expansion for 4/pi.
1 + 1
---------------------------
2 + 9
-----------------------
2 + 25
------------------
2 + 49
--------------
2 + 81
---------
2 + ...
Let's use this expansion to compute rational and floating point
approximations for pi.
As you can see, the values are converging to
pi = 3.14159265358979323846..., but not very quickly.
You need not restrict yourself to continued fractions of integers. Here is
an expansion for a quotient of Gaussian integers.
This is an expansion for a quotient of polynomials in one variable with
rational number coefficients.
To conclude this section, we give you evidence that
z = 3 + 1
---------------------------
3 + 1
-----------------------
6 + 1
-------------------
3 + 1
--------------
6 + 1
---------
3 + ...
is the expansion of the square root of 11.
