----------------------------------------------------------------------------
Grand Challenges in Computer Algebra
----------------------------------------------------------------------------
Fast multiprecision evaluation of series of rational numbers
How to compute Euler's constant to 1,000,000 decimals (Fast
multiprecision evaluation of series of rational numbers)
Calculating Euler's constant gamma has not attracted the same public
intrigue as calculating pi, but it has still inspired the dedication of
a few. While we presently know millions of decimal places of pi, till
the early 1997 only several thousand places of gamma are known. The
evaluation of gamma is considerably more difficult [1]. For pi, one has
the Borweins' quartically convergent AGM algorithm [2]: each successive
iteration approximately quadruples the number of correct digits. By
contrast, for gamma, not even a quadratically convergent algorithm is
known [3].
Knuth [1] obtained 1271 places of Euler's constant in 1962, using
Euler-Maclaurin summation. Sweeney [4] obtained 3683 places the
following year, using an expansion of the exponential integral Ei(x),
which was subsequently extended by others [5] to 20700 places by 1977.
Brent and McMillan [6] computed 30100 places in 1980 using certain
identities involving modified Bessel functions. They also calculated
the first 29200 partial quotients in the regular continued fraction
expansion for gamma and deduced that if gamma is a rational number,
then its integer denominator must exceed 10**15000. This is compelling
evidence that Euler's constant is not rational. A proof of
irrationality (let alone transcendence) is still beyond our reach.
We will present a new technique for fast multiprecision evaluation of
series of rational numbers [7] which allows to improve the asymptotic
and practical efficiency of many algorithms. Applications include fast
algorithms for elementary functions, pi, hypergeometric functions at
rational points, Euler's, Catalan's and Ap'ery's constant. We will give
an example computation of Euler's constant to 1,000,000 decimals using
the new technique. Extensive measurements suggest that the using the
new technique results in exteremely efficient code which is superior to
available Computer Algebra Systems implementations.
[1] D. E. Knuth, Euler's constant to 1271 places, Math. Comp. 16 (1962)
275-281
[2] J. M. Borwein and P. B. Borwein, Pi and the AGM: A study in
analytic number theory and computational complexity, Wiley 1987.
[3] D. H. Bailey, Numerical results on the transcendence of constants
involving , e and Euler's constant, Math. Comp. 50 (1988) 275-281.
[4] D. W. Sweeney, On the computation of Euler's constant, Math. Comp.
17 (1963) 170-178.
[5] R. P. Brent, Computation of the regular continued fraction for
Euler's constant, Math. Comp. 31 (1977) 771-777.
[6] R. P. Brent and E. M. McMillan, Some new algorithms for
high-precision computation of Euler's constant, Math. Comp. 34 (1980)
305-312.
[7] Bruno Haible, Thomas Papanikolaou, Fast multiprecision evaluation
of series of rational numbers, Technical Report No. TI-7/97, 1997
Bruno Haible Thomas Papanikolaou
ILOG, France TH Darmstadt / Univ. des Saarlandes,
haible@ilog.fr Germany
papanik@cs.uni-sb.de