On the rapid computation of various polylogarithmic constants
Authors:
David Bailey, Peter Borwein and Simon Plouffe
Journal:
Math. Comp. 66 (1997), 903913
MSC (1991):
Primary 11A05, 11Y16, 68Q25
MathSciNet review:
1415794
Fulltext PDF Free Access
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.
Handbook of mathematical functions, with formulas, graphs, and
mathematical tables, Edited by Milton Abramowitz and Irene A. Stegun,
Dover Publications, Inc., New York, 1966. MR 0208797
(34 #8606)
 2.
V. Adamchik and S. Wagon, Pi: A 2000year search changes direction (preprint).
 3.
Alfred
V. Aho, John
E. Hopcroft, and Jeffrey
D. Ullman, The design and analysis of computer algorithms,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Second printing; AddisonWesley Series in Computer Science and Information
Processing. MR
0413592 (54 #1706)
 4.
David
H. Bailey, Jonathan
M. Borwein, and Roland
Girgensohn, Experimental evaluation of Euler sums, Experiment.
Math. 3 (1994), no. 1, 17–30. MR 1302815
(96e:11168)
 5.
Jonathan
M. Borwein and Peter
B. Borwein, Pi and the AGM, Canadian Mathematical Society
Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New
York, 1987. A study in analytic number theory and computational complexity;
A WileyInterscience Publication. MR 877728
(89a:11134)
 6.
J.
M. Borwein and P.
B. Borwein, On the complexity of familiar functions and
numbers, SIAM Rev. 30 (1988), no. 4,
589–601. MR
967961 (89k:68061), http://dx.doi.org/10.1137/1030134
 7.
J.
M. Borwein, P.
B. Borwein, and D.
H. Bailey, Ramanujan, modular equations, and approximations to pi,
or How to compute one billion digits of pi, Amer. Math. Monthly
96 (1989), no. 3, 201–219. MR 991866
(90d:11143), http://dx.doi.org/10.2307/2325206
 8.
Richard
P. Brent, The parallel evaluation of general arithmetic
expressions, J. Assoc. Comput. Mach. 21 (1974),
201–206. MR 0660280
(58 #31996)
 9.
Stephen
A. Cook, A taxonomy of problems with fast parallel algorithms,
Inform. and Control 64 (1985), no. 13, 2–22.
MR 837088
(87k:68043), http://dx.doi.org/10.1016/S00199958(85)800413
 10.
R. Crandall, K. Dilcher, and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), 433449. CMP 96:07
 11.
Richard
E. Crandall and Joe
P. Buhler, On the evaluation of Euler sums, Experiment. Math.
3 (1994), no. 4, 275–285. MR 1341720
(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, PrenticeHall, Englewood Cliffs, NJ, 1975.
 14.
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 15.
Leonard
Lewin, Polylogarithms and associated functions, NorthHolland
Publishing Co., New YorkAmsterdam, 1981. With a foreword by A. J. Van der
Poorten. MR
618278 (83b:33019)
 16.
Leonard
Lewin (ed.), Structural properties of polylogarithms,
Mathematical Surveys and Monographs, vol. 37, American Mathematical
Society, Providence, RI, 1991. MR 1148371
(93b:11158)
 17.
N. Nielsen, Der Eulersche Dilogarithmus, Halle, Leipzig, 1909.
 18.
Stanley
Rabinowitz and Stan
Wagon, A spigot algorithm for the digits of 𝜋, Amer.
Math. Monthly 102 (1995), no. 3, 195–203. MR 1317842
(96a:11152), http://dx.doi.org/10.2307/2975006
 19.
Arnold
Schönhage, Asymptotically fast algorithms for the numerical
multiplication and division of polynomials with complex coefficients,
Computer algebra (Marseille, 1982) Lecture Notes in Comput. Sci.,
vol. 144, Springer, BerlinNew York, 1982, pp. 3–15. MR 680048
(83m:68064)
 20.
John
Todd, A problem on arc tangent relations, Amer. Math. Monthly
56 (1949), 517–528. MR 0031496
(11,159d)
 21.
Herbert
S. Wilf, Algorithms and complexity, Prentice Hall, Inc.,
Englewood Cliffs, NJ, 1986. MR 897317
(88j:68073)
 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 2000year search changes direction (preprint).
 3.
 A. V. Aho, J.E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, AddisonWesley, Reading, MA, 1975. MR 54:1706
 4.
 D. H. Bailey, J. Borwein and R. Girgensohn, Experimental evaluation of Euler sums, Experimental Mathematics 3 (1994), 1730. 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), 589601. MR 89k:68061
 7.
 J. Borwein, P. Borwein and D. H. Bailey, Ramanujan, modular equations and approximations to pi, Amer. Math. Monthly 96 (1989), 201219. MR 90d:11143
 8.
 R. Brent, The parallel evaluation of general arithmetic expressions, J. Assoc. Comput. Mach. 21 (1974), 201206. MR 58:31996
 9.
 S. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control 64 (1985), 222. MR 87k:68043
 10.
 R. Crandall, K. Dilcher, and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), 433449. CMP 96:07
 11.
 R. Crandall and J. Buhler, On the evaluation of Euler sums, Experimental Mathematics 3, (1995), 275285. 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, PrenticeHall, Englewood Cliffs, NJ, 1975.
 14.
 D. E. Knuth, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, AddisonWesley, 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), 195203. 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. 315. MR 83m:68064
 20.
 J. Todd, A problem on arc tangent relations, Amer. Math. Monthly 56 (1949), 517528. MR 11:159d
 21.
 H. S. Wilf, Algorithms and Complexity, Prentice Hall, Englewood Cliffs, NJ, 1986. MR 88j:68073
Similar Articles
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 T27A1, Moffett Field, California 940351000
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:
http://dx.doi.org/10.1090/S0025571897008569
PII:
S 00255718(97)008569
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
