Continued Fractions

by Stephen Wolfram and Ilan Vardi

This Notebook generates continued fraction approximations to real numbers, represented as ContinuedFractionForm objects.  It extends the Normal function to convert such objects to rational numbers.

Reference

Context

NumberTheory`ContinuedFractions`

Package Version

1.4

Mathematica Version

2.0

Copyright

Copyright 1987-1993, Wolfram Research, Inc.

History

Modified by John Novak (Wolfram Research), May 1992, to allow nonrational nonfloating-point numbers.
Modified by John Novak (Wolfram Research), March 1992, to allow rational numbers.
Revised by Ilan Vardi (Wolfram Research), September 1989.
Version 1.1 by Stephen Wolfram (Wolfram Research), May 1987.

Keywords

number theory, continued fraction, rational approximation, partial quotient

Source

Hardy and Wright: "An Introduction to the Theory of Numbers", Cambridge University Press.

Warning

Loading this package extends the definition of Normal.

Limitation

This package does not define mathematical operations on ContinuedFractionForm objects.

Discussion

The continued fraction of a real number x  is ContinuedFractionForm[{a0,a1,a2,...}] if x  equals a0+1/(a1+1/(a2+...)).  All numbers are forced to bignums, minimizing roundoff error problems.  If a nonrational nonfloating-point number is given, ContinuedFraction estimates the precision needed to get a continued fraction of the correct order.  Each term in a continued fraction expansion requires an expected 0.429017 decimal digits (i.e., Log[10, Khinchin], cf. Ilan Vardi's book, p. 163).  Thus, a comfortable overestimate might be to start with one decimal digit for every two continued fraction coefficients requested.

Examples

In the case of non-numeric numbers such as Pi,  ContinuedFraction attempts to numericalize the number to a precision that will give the desired continued fraction order.

ContinuedFraction[Pi, 8]

You can also use ContinuedFraction on rational numbers.

ContinuedFraction[1234/4321, 10]

We got fewer terms than we asked for, because the expansion became exact before the tenth term.

You can use the Normal function to turn a ContinuedFraction object into a rational number.  This gives a list of some rational approximations of Pi:

Table[Normal[ContinuedFraction[Pi, n]], {n, 1, 7}]

You can see why 355/113 is the best rational approximation that most people know, because after that they get pretty ugly.

Implementation

Preparation

Create the context for this Notebook:

Usage messages:

ContinuedFraction::usage =
"ContinuedFraction[x, n] generates the continued fraction
representation for the number x to order n.  Note that the
order returned may be less than n if the continued fraction
terminates before n steps."

ContinuedFractionForm::usage =
"ContinuedFractionForm[{a0,a1,...}] is a continued fraction;
it is converted to an ordinary rational using Normal."

Definitions

Begin["`Private`"]

ContinuedFraction error messages:

ContinuedFraction::incomp =
"Warning: ContinuedFraction either terminated or the argument
was unable to be evaluated to sufficient precision in ``
attempts."

ContinuedFraction for machine numbers:

ContinuedFraction[x_?MachineNumberQ, n_Integer?Positive] :=
  ContinuedFraction[SetPrecision[x, $MachinePrecision], n]

ContinuedFraction for reals and rationals:

ContinuedFraction[x:(_Real | _Rational), n_Integer?Positive] :=
  ContinuedFractionForm[Floor[Prepend[cf[x, n - 1], x]]]

ContinuedFraction for non-numeric numbers:

Note:   A comfortable overestimate for the required precision of a non-numeric number is to start with one decimal digit for every two continued fraction coefficients required.

ContinuedFraction[x_?(Not[NumberQ[#]] && NumberQ[N[#]] &),
        n_Integer?Positive] :=
        Module[{nx, prec = n/2 + 10, out = {}, i = 0},
                While[Length[out] < n && i++ < n,
                        nx = N[x, prec];
                        out = cf[nx, n-1];
                        prec += (n - Length[out])/2 + 10
                ];
                If[Length[out] < n-1,
                        Message[ContinuedFraction::incomp, n]
                ];
                ContinuedFractionForm[Floor[Prepend[out, nx]]]
        ]

Implement the private cf function:

cf[num_, 0] := {}
cf[num_, ord_] := {} /; ((num - Floor[num]) == 0)
cf[num_, ord_] :=
        Module[{tmp = 1/(num - Floor[num])},
                Join[{tmp}, cf[tmp, ord - 1]]
        ]

Normal for ContinuedFractionForm objects:

ContinuedFractionForm/: Normal[ContinuedFractionForm[a_List]] :=
        Fold[ 1 / #1 + #2 &, Last[a], Rest[Reverse[a]]]

End[]

Finish

EndPackage[]