×
Bailey, David; Borwein, Peter; Plouffe, Simon

On the rapid computation of various polylogarithmic constants. (English) Zbl 0879.11073

Math. Comput. 66, No. 218, 903-913 (1997).
Summary: We give algorithms for the computation of the \(d\)-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 \(\log {(2)}\) or \(\pi \) on a modest work station in a few hours run time. We demonstrate this technique by computing the ten billionth hexadecimal digit of \(\pi\), the billionth hexadecimal digits of \(\pi^{2}\), \(\log(2)\) and \(\log^{2}(2)\), and the ten billionth decimal digit of \(\log (9/10)\). These calculations rest on the observation that very special types of identities exist for certain numbers like \(\pi\), \(\pi^{2}\), \(\log(2)\) and \(\log^{2}(2)\). 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 \(\pi\): \[ \pi = \sum _{i=0}^{\infty}\frac {1}{16^{i}} \left(\frac {4}{8i+1} - \frac {2}{8i+4} - \frac {1}{8i+5} - \frac {1}{8i+6}\right). \]

Cited in 11 Reviews
Cited in 66 Documents

MSC:

11Y60 Evaluation of number-theoretic constants
68Q25 Analysis of algorithms and problem complexity

Keywords:

computation of digits; logarithm; polylogarithms; class SC; \(\pi\); algorithms; transcendental numbers
PDF BibTeX XML Cite
\textit{D. Bailey} et al., Math. Comput. 66, No. 218, 903--913 (1997; Zbl 0879.11073)
Full Text: DOI

References:

[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.
[2] V. Adamchik and S. Wagon, Pi: A 2000-year search changes direction (preprint). · Zbl 0886.11073
[3] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0326.68005
[4] David H. Bailey, Jonathan M. Borwein, and Roland Girgensohn, Experimental evaluation of Euler sums, Experiment. Math. 3 (1994), no. 1, 17 – 30. · Zbl 0810.11076
[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 Wiley-Interscience Publication. · Zbl 0611.10001
[6] J. M. Borwein and P. B. Borwein, On the complexity of familiar functions and numbers, SIAM Rev. 30 (1988), no. 4, 589 – 601. · Zbl 0686.68029
[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. · Zbl 0672.10017
[8] Richard P. Brent, The parallel evaluation of general arithmetic expressions, J. Assoc. Comput. Mach. 21 (1974), 201 – 206. · Zbl 0276.68010
[9] Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Inform. and Control 64 (1985), no. 1-3, 2 – 22. · Zbl 0575.68045
[10] R. Crandall, K. Dilcher, and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), 433-449. CMP 96:07 · Zbl 0854.11002
[11] Richard E. Crandall and Joe P. Buhler, On the evaluation of Euler sums, Experiment. Math. 3 (1994), no. 4, 275 – 285. · Zbl 0833.11045
[12] H. R. P. Ferguson and D. H. Bailey, Analysis of PSLQ, an integer relation algorithm (preprint). · Zbl 0927.11055
[13] E. R. Hansen, A Table of Series and Products, Prentice-Hall, Englewood Cliffs, NJ, 1975. · Zbl 0438.00001
[14] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0477.65002
[15] Leonard Lewin, Polylogarithms and associated functions, North-Holland Publishing Co., New York-Amsterdam, 1981. With a foreword by A. J. Van der Poorten. · Zbl 0465.33001
[16] Leonard Lewin , Structural properties of polylogarithms, Mathematical Surveys and Monographs, vol. 37, American Mathematical Society, Providence, RI, 1991. · Zbl 0745.33009
[17] N. Nielsen, Der Eulersche Dilogarithmus, Halle, Leipzig, 1909. · JFM 40.0478.01
[18] Stanley Rabinowitz and Stan Wagon, A spigot algorithm for the digits of \?, Amer. Math. Monthly 102 (1995), no. 3, 195 – 203. · Zbl 0853.11102
[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, Berlin-New York, 1982, pp. 3 – 15. · Zbl 0538.68035
[20] J. Todd, A problem on arc tangent relations, Amer. Math. Monthly 56 (1949), 517-528. · Zbl 0036.16101
[21] Herbert S. Wilf, Algorithms and complexity, Prentice Hall, Inc., Englewood Cliffs, NJ, 1986. · Zbl 0637.68006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.