From papanik@cdc.Informatik.TH-Darmstadt.DE Wed Apr 2 17:36:46 1997
Date: Wed, 2 Apr 1997 14:02:15 -0500
From: Thomas Papanikolaou
To: NMBRTHRY@LISTSERV.NODAK.EDU
Subject: Euler's constant to 1,000,000 decimals
Dear All,
we would like to announce the computation of Euler's constant to
1,000,000 digits. The algorithm used is the one presented in the
paper of McMillan and Brent [1] (the second variant) accelerated
by binary splitting [2]. This calculation verified the previous
500,000-digits record to 499927 digits. Using 500,000 digits
of gamma and a LiDIA version of a program by H.J.J. te Riele,
CWI Amsterdam [3], we were also able to compute 475006 partial
quotients of its continued fraction. Computing the 475006-th
convergent proved the following [4]
THEOREM
-------
If Euler's constant is a rational number P/Q, for integers P, Q
then its integer denominator |Q| > 10^244663
TIMINGS
-------
Machine Algorithm Binary Splitting Digits Time
----------------------------------------------------------------------------
HP 9000/712 Brent (1) no 400,000 6 days 8 hours
Sparc Ultra 167 Mhz Brent (2) no 500,000 6 days 16 hours
Sparc Ultra 167 Mhz Brent (2) yes 1,000,000 42 hours
----------------------------------------------------------------------------
The computation of the 475006 partial quotients required 2 hour 18 min 15 sec
on an Intel Pentium with 133 Mhz. The computation of the convergents using the
forward evaluation required 1 hour 39 min 22 sec 95 hsec on the same machine.
IMPLEMENTATION
--------------
The algorithm was implemented using the LiDIA library for computational
number theory and it will be part of the multiprecision floating-point
arithmetic of the package in release 1.4. The current version of LiDIA
(1.3) is available from
ftp.informatik.th-darmstadt.de:/pub/TI/systems/LiDIA
http://www.informatik.th-darmstadt.de/TI/LiDIA
We have replaced LiDIA's kernel by Bruno Haible's CLN package which is
available from
ma2s2.mathematik.uni-karlsruhe.de:/pub/gnu/cln.tar.z
via anonymous FTP. This package contains beside an implementation
of Schoenhage-Strassen's multiplication algorithm, the first implementation
of a binary splitting device for rational series as described in [2]. For
more information and the computational data please visit
http://www.informatik.th-darmstadt.de/TI/Mitarbeiter/papanik/Welcome.html
ACKNOWLEDGEMENTS
----------------
The computation of the continued fraction would not have been possible
without the help and motivation from Herman J.J. te Riele and Richard
P. Brent.
Best
Bruno Haible & Thomas Papanikolaou
REFERENCES
----------
[1] R. P. Brent and E. M. McMillan, Some new algorithms for
high-precision computation of Euler's constant, Math.
Comp. 34 (1980) 305-312.
[2] Bruno Haible, Thomas Papanikolaou, Fast multiprecision
evaluation of series of rational numbers, Technical
Report No. TI-7/97, 18.03.1997. Available from
http://www.informatik.th-darmstadt.de/TI/Veroeffentlichung/TR/Welcome.html
(contains sample code)
[3] Richard P. Brent, Alfred J. van der Poorten and Herman J.J. te Riele,
A comparative study of algorithms for computing continued fractions
of algebraic numbers, pp. 37-49 in: H. Cohen (editor), Algorithmic
Number Theory: Second International Symposium, ANTS-II, Talence,
France, 18-23.05.1996, Springer, Berlin etc., 1996.
[4] Thomas Papanikolaou, Entwurf und Entwicklung einer objektorientierten
Bibliothek f\"ur algorithmische Zahlentheorie, PhD Thesis, to appear.