On the rapid computation of various polylogarithmic constants

Authors:
David Bailey, Peter Borwein and Simon Plouffe

Journal:
Math. Comp. **66** (1997), 903-913

MSC (1991):
Primary 11A05, 11Y16, 68Q25

DOI:
https://doi.org/10.1090/S0025-5718-97-00856-9

MathSciNet review:
1415794

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give algorithms for the computation of the -th digit of certain transcendental numbers in various bases. These algorithms can be easily implemented (multiple precision arithmetic is not needed), require virtually no memory, and feature run times that scale nearly linearly with the order of the digit desired. They make it feasible to compute, for example, the billionth binary digit of or on a modest work station in a few hours run time. We demonstrate this technique by computing the ten billionth hexadecimal digit of , the billionth hexadecimal digits of and , and the ten billionth decimal digit of . These calculations rest on the observation that very special types of identities exist for certain numbers like , , and . These are essentially polylogarithmic ladders in an integer base. A number of these identities that we derive in this work appear to be new, for example the critical identity for :

**1.**M. Abramowitz and I.A. Stegun,*Handbook of Mathematical Functions*, Dover, New York, NY, 1966. MR**34:8606****2.**V. Adamchik and S. Wagon,*Pi: A 2000-year search changes direction (preprint)*.**3.**A. V. Aho, J.E. Hopcroft, and J. D. Ullman,*The Design and Analysis of Computer Algorithms*, Addison-Wesley, Reading, MA, 1975. MR**54:1706****4.**D. H. Bailey, J. Borwein and R. Girgensohn,*Experimental evaluation of Euler sums*, Experimental Mathematics**3**(1994), 17-30. MR**96e:11168****5.**J. Borwein, and P Borwein,*Pi and the AGM - A Study in Analytic Number Theory and Computational Complexity*, Wiley, New York, NY, 1987. MR**89a:11134****6.**J. Borwein and P. Borwein,*On the complexity of familiar functions and numbers*, SIAM Review**30**(1988), 589-601. MR**89k:68061****7.**J. Borwein, P. Borwein and D. H. Bailey,*Ramanujan, modular equations and approximations to pi*, Amer. Math. Monthly**96**(1989), 201-219. MR**90d:11143****8.**R. Brent,*The parallel evaluation of general arithmetic expressions*, J. Assoc. Comput. Mach.**21**(1974), 201-206. MR**58:31996****9.**S. Cook,*A taxonomy of problems with fast parallel algorithms*, Information and Control**64**(1985), 2-22. MR**87k:68043****10.**R. Crandall, K. Dilcher, and C. Pomerance,*A search for Wieferich and Wilson primes*, Math. Comp.**66**(1997), 433-449. CMP**96:07****11.**R. Crandall and J. Buhler,*On the evaluation of Euler sums*, Experimental Mathematics**3,**(1995), 275-285. MR**96e:11113****12.**H. R. P. Ferguson and D. H. Bailey,*Analysis of PSLQ, an integer relation algorithm (preprint)*.**13.**E. R. Hansen,*A Table of Series and Products*, Prentice-Hall, Englewood Cliffs, NJ, 1975.**14.**D. E. Knuth,*The Art of Computer Programming. Vol. 2: Seminumerical Algorithms*, Addison-Wesley, Reading, MA, 1981. MR**83i:68003****15.**L. Lewin,*Polylogarithms and Associated Functions*, North Holland, New York, 1981. MR**83b:33019****16.**L. Lewin,*Structural Properties of Polylogarithms*, Amer. Math. Soc., RI., 1991. MR**93b:11158****17.**N. Nielsen,*Der Eulersche Dilogarithmus*, Halle, Leipzig, 1909.**18.**S. D. Rabinowitz and S. Wagon,*A spigot algorithm for the digits of pi*, Amer. Math. Monthly**102**(1995), 195-203. MR**96a:11152****19.**A. Schönhage,*Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients*, in: EUROCAM (1982) Marseille, Springer Lecture Notes in Computer Science, vol. 144, 1982, pp. 3-15. MR**83m:68064****20.**J. Todd,*A problem on arc tangent relations*, Amer. Math. Monthly**56**(1949), 517-528. MR**11:159d****21.**H. S. Wilf,*Algorithms and Complexity*, Prentice Hall, Englewood Cliffs, NJ, 1986. MR**88j:68073**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
11A05,
11Y16,
68Q25

Retrieve articles in all journals with MSC (1991): 11A05, 11Y16, 68Q25

Additional Information

**David Bailey**

Affiliation:
NASA Ames Research Center, Mail Stop T27A-1, Moffett Field, California 94035-1000

Email:
dbailey@nas.nasa.gov

**Peter Borwein**

Affiliation:
Department of Mathematics and Statistics, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6

Email:
pborwein@cecm.sfu.ca

**Simon Plouffe**

Affiliation:
Department of Mathematics and Statistics, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6

Email:
plouffe@cecm.sfu.ca

DOI:
https://doi.org/10.1090/S0025-5718-97-00856-9

Keywords:
Computation,
digits,
log,
polylogarithms,
SC,
$\pi $,
algorithm

Received by editor(s):
October 11, 1995

Received by editor(s) in revised form:
February 16, 1996

Additional Notes:
Research of the second author was supported in part by NSERC of Canada.

Article copyright:
© Copyright 1997
American Mathematical Society