hypertex/pages/CONTFRAC.ht

% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\ContinuedFractionXmpTitle}{ContinuedFraction}
\newcommand{\ContinuedFractionXmpNumber}{9.12}
%
% =====================================================================
\begin{page}{ContinuedFractionXmpPage}{9.12 ContinuedFraction}
% =====================================================================
\beginscroll

%
%
%
%
%


Continued fractions have been a fascinating and useful tool in mathematics
%-% \HDindex{fraction!continued}{ContinuedFractionXmpPage}{9.12}{ContinuedFraction}
for well over three hundred years.
\Language{} implements continued fractions for fractions of any Euclidean
%-% \HDindex{continued fraction}{ContinuedFractionXmpPage}{9.12}{ContinuedFraction}
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 \downlink{`Stream'}{StreamXmpPage}\ignore{Stream} to remind yourself of some
of the operations with streams.

The \spadtype{ContinuedFraction} domain is a field and therefore you can
add, subtract, multiply and divide the fractions.
\xtc{
The \spadfunFrom{continuedFraction}{ContinuedFraction} operation
converts its fractional argument to a continued fraction.
}{
\spadpaste{c := continuedFraction(314159/100000) \bound{c}}
}
%
This display is a compact form of the bulkier
\begin{verbatim}
        3 +                 1
            -------------------------------
            7 +               1
                ---------------------------
                15 +            1
                     ----------------------
                     1 +          1
                         ------------------
                         25 +       1
                              -------------
                              1 +     1
                                  ---------
                                  7 +   1
                                      -----
                                        4
\end{verbatim}
You can write any rational number in a similar form.
The fraction will be finite and you can always take the ``numerators'' to
be \spad{1}.
That is, any rational number can be written as a simple, finite continued
fraction of the form
\begin{verbatim}
        a(1) +           1
               -------------------------
               a(2) +          1
                      --------------------
                      a(3) +
                             .
                              .
                               .
                                     1
                               -------------
                               a(n-1) +  1
                                        ----
                                        a(n)
\end{verbatim}
\xtc{
The \spad{a(i)} are called partial quotients and the operation
\spadfunFrom{partialQuotients}{ContinuedFraction} creates a stream of them.
}{
\spadpaste{partialQuotients c \free{c}}
}
\xtc{
By considering more and more of the fraction, you get the
\spadfunFrom{convergents}{ContinuedFraction}.
For example, the first convergent is \spad{a(1)},
the second is
\spad{a(1) + 1/a(2)} and so on.
}{
\spadpaste{convergents c \free{c}}
}
%
\xtc{
Since this is a finite continued fraction, the last convergent is
the original rational number, in reduced form.
The result of \spadfunFrom{approximants}{ContinuedFraction}
is always an infinite stream, though it may just repeat the ``last''
value.
}{
\spadpaste{approximants c \free{c}}
}
\xtc{
Inverting \spad{c} only changes the partial quotients of its fraction
by inserting a \spad{0} at the beginning of the list.
}{
\spadpaste{pq := partialQuotients(1/c) \free{c}\bound{pq}}
}
\xtc{
Do this to recover the original continued fraction from this list of
partial quotients.
The three-argument form of the
\spadfunFrom{continuedFraction}{ContinuedFraction} operation takes an
element which is the whole part of the fraction, a stream of elements
which are the numerators of the fraction, and a stream of elements which
are the denominators of the fraction.
}{
\spadpaste{continuedFraction(first pq,repeating [1],rest pq) \free{pq}}
}
\xtc{
The streams need not be finite for
\spadfunFrom{continuedFraction}{ContinuedFraction}.
Can you guess which irrational number has the following continued
fraction?
See the end of this section for the answer.
}{
\spadpaste{z:=continuedFraction(3,repeating [1],repeating [3,6]) \bound{z}}
}
%

In 1737 Euler discovered the infinite continued fraction expansion
\begin{verbatim}
        e - 1             1
        ----- = ---------------------
          2     1 +         1
                    -----------------
                    6 +       1
                        -------------
                        10 +    1
                             --------
                             14 + ...
\end{verbatim}
We use this expansion to compute rational and floating point
approximations of \spad{e}.\footnote{For this and other interesting
expansions, see C. D. Olds, {\it Continued Fractions,}
New Mathematical Library, (New York: Random House, 1963), pp.
134--139.}

\xtc{
By looking at the above expansion, we see that the whole part is \spad{0}
and the numerators are all equal to \spad{1}.
This constructs the stream of denominators.
}{
\spadpaste{dens : Stream Integer := cons(1, stream((x +-> x + 4), 6)) \bound{dens}}
}
\xtc{
Therefore this is the continued fraction expansion for
\spad{(e-1)/2}.
}{
\spadpaste{cf := continuedFraction(0,repeating [1],dens) \free{dens}\bound{cf}}
}
\xtc{
These are the rational number convergents.
}{
\spadpaste{ccf := convergents cf \free{cf}\bound{ccf}}
}
\xtc{
You can get rational convergents for \spad{e} by multiplying by \spad{2} and
adding \spad{1}.
}{
\spadpaste{eConvergents := [2*e + 1 for e in ccf] \bound{ec}\free{ccf}}
}
%
\xtc{
You can also compute the floating point approximations to these convergents.
}{
\spadpaste{eConvergents :: Stream Float \free{ec}}
}
\xtc{
Compare this to the value of \spad{e} computed by the
\spadfunFrom{exp}{Float} operation in \spadtype{Float}.
}{
\spadpaste{exp 1.0}
}

In about 1658, Lord Brouncker established the following expansion
for \spad{4/pi}.
\begin{verbatim}
        1 +            1
            -----------------------
            2 +          9
                -------------------
                2 +        25
                    ---------------
                    2 +      49
                        -----------
                        2 +    81
                            -------
                            2 + ...
\end{verbatim}
\xtc{
Let's use this expansion to compute rational and floating point
approximations for \spad{pi}.
}{
\spadpaste{cf := continuedFraction(1,[(2*i+1)^2 for i in 0..],repeating [2])\bound{cf1}}
}
\xtc{
}{
\spadpaste{ccf := convergents cf \free{cf1}\bound{ccf1}}
}
\xtc{
}{
\spadpaste{piConvergents := [4/p for p in ccf] \bound{piConvergents}\free{ccf1}}
}
\xtc{
As you can see, the values are converging to
\spad{pi} = 3.14159265358979323846...,
but not very quickly.
}{
\spadpaste{piConvergents :: Stream Float \free{piConvergents}}
}

\xtc{
You need not restrict yourself to continued fractions of integers.
Here is an expansion for a quotient of Gaussian integers.
%-% \HDindex{Gaussian integer}{ContinuedFractionXmpPage}{9.12}{ContinuedFraction}
}{
\spadpaste{continuedFraction((- 122 + 597*\%i)/(4 - 4*\%i))}
}
\xtc{
This is an expansion for a quotient of polynomials in one variable
with rational number coefficients.
}{
\spadpaste{r : Fraction UnivariatePolynomial(x,Fraction Integer) \bound{rdec}}
}
\xtc{
}{
\spadpaste{r := ((x - 1) * (x - 2)) / ((x-3) * (x-4)) \free{rdec}\bound{r}}
}
\xtc{
}{
\spadpaste{continuedFraction r \free{r}}
}

\xtc{
To conclude this section, we give you evidence that
}{
\spadpaste{z \free{z}}
}
is the expansion of the square root of \spad{11}.
%
\xtc{
}{
\spadpaste{[i*i for i in convergents(z) :: Stream Float] \free{z}}
}
\xtc{
}{
\spadpaste{continuedFraction sqrt 11.0}
}
\endscroll
\autobuttons
\end{page}
%