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.