(* :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.
*)
BeginPackage["NumberTheory`ContinuedFractions`"]
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."
Begin["`Private`"]
ContinuedFraction::incomp =
"Warning: ContinuedFraction either terminated or the argument was
unable to be evaluated to sufficient precision in `` attempts."
ContinuedFraction[x_?MachineNumberQ, n_Integer?Positive] :=
ContinuedFraction[SetPrecision[x, $MachinePrecision], n]
ContinuedFraction[x:(_Real | _Rational), n_Integer?Positive] :=
ContinuedFractionForm[Floor[Prepend[cf[x, n - 1], x]]]
(* :Note:
A comfortable overestimate for the required precision 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]]]
]
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]]
]
ContinuedFractionForm/: Normal[ContinuedFractionForm[a_List]] :=
Fold[ 1 / #1 + #2 &, Last[a], Rest[Reverse[a]]]
End[]
EndPackage[]
(* :Examples:
ContinuedFraction[Pi, 8]
ContinuedFraction[1234/4321, 10]
Table[Normal[ContinuedFraction[Pi, n]], {n, 1, 7}]
*)