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.