Continued fraction algorithm
- By Simon Plouffe
- The basic algorithm starts with a number x=x(0 ) and
successively calculates the y(n) by using this formula.
-
- This will yield a sequence [y(0),y(1),y(2),...,y(k)] called
the convergents of the continued fraction expansion of x. Usually
n digits of x will yield approximately n convergents
[Knuth]. In order to detect any pattern we need enough
digits, which in turn will yield enough convergents. A good test
starts with 16 digits, just enough for
GFUN
to detect a generating function.
Example : with x = tan(1) = 1.557407724654902... we obtain:
1.557407724654902 =
1
1 + -------------------------------------------
1
1 + ---------------------------------------
1
1 + -----------------------------------
1
3 + -------------------------------
1
1 + ---------------------------
1
5 + -----------------------
1
1 + -------------------
1
7 + ---------------
1
1 + -----------
1
9 + -------
1 + ...
Which gives us the sequence of convergents :
[1,
1, 1, 3, 1, 5, 1, 7, 1,9, 1, 11, 1, 13, 1]. We are now in a
position to ask GFUN to try to guess a generating function. GFUN
is part of the Share Library of Maple. Clicking on that sequence
will launch a request to the Sequence Server at ATT Research Labs.
sample MapleV session , ... (we now take the sequence),...
[1, 1, 1, 3, 1, 5, 1, 7, 1, 9, 1, 11, 1, 13, 1] ;
> with(share);readshare(gfun,calculus);guessgf(",x):factor(");
2 3
1 + x - x + x
[-----------------, ogf]
2 2
(x - 1) (x + 1)
So the program detected a pattern in the continued fraction
expansion of the real number X.
NOTE: no attempts are made yet to reconstruct the actual
expression for x using the generating function found.
References
Computing
the generating function of a series given its first few terms,
by François Bergeron and Simon Plouffe, Experimental
Mathematics, Vol. 1 #4, 1992.
An
Introduction to the Theory of Numbers,
by G.H. Hardy and E.M.
Wright, Oxford Univ. Press.
Hanbook of mathematical functions,
by M. Abramowitz and Irene Stegun,
Dover 1964.
The Art of Computing Programming,
by Donald E. Knuth, vol. 2 ,
semi-numerical algorithms.