Continued fraction algorithm
- by Simon Plouffe
CECM
- 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 AT&T 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.
isc@cecm.sfu.ca