Time-and space-efficient evaluation of some hypergeometric constants

ABSTRACT

The currently best known algorithms for the numerical evaluation of hypergeometric constants such as Ç(3) to d decimal digits have time complexity O(M(d) log²d) and space complexity of O(d log d) or O(d). Following work from Cheng, Gergel, Kim and Zima, we present a new algorithm with the same asymptotic complexity, but more efficient in practice. Our implementation of this algorithm improves over existing programs for the computation of Π, and we announce a new record of 2 billion digits for Ç(3).

REFERENCES

• 1: Bernstein, D. J. Fast multiplication and its applications. http://cr.yp.to/papers.html, 2004.
• 2: Borwein, J. and Borwein, P. Pi and the AGM. John Wiley and Sons, 1987.
• 3: Jonathan M. Borwein , David M. Bradley , Richard E. Crandall, Computational strategies for the Riemann zeta function, Journal of Computational and Applied Mathematics, v.121 n.1-2, p.247-296, Sept. 1, 2000 [doi>10.1016/S0377-0427(00)00336-8]
• 4: Richard P. Brent, Fast Multiple-Precision Evaluation of Elementary Functions, Journal of the ACM (JACM), v.23 n.2, p.242-251, April 1976 [doi>10.1145/321941.321944]
• 5: Chudnovsky, D., Chudnovsky G. Computer algebra in the service of mathematical physics and number theory. Computers in mathematics (Stanford, CA, 1986), 109--232, Lecture Notes in Pure and Appl. Math., 125, Dekker, New York, 1990.
• 6: Howard Cheng , Barry Gergel , Ethan Kim , Eugene Zima, Space-efficient evaluation of hypergeometric series, ACM SIGSAM Bulletin, v.39 n.2, June 2005 [doi>10.1145/1101884.1101886]
• 7: Howard Cheng , Eugene Zima, On accelerated methods to evaluate sums of products of rational numbers, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.54-61, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345581]
• 8: Laurent Fousse , Guillaume Hanrot , Vincent Lefèvre , Patrick Pélissier , Paul Zimmermann, MPFR: A multiple-precision binary floating-point library with correct rounding, ACM Transactions on Mathematical Software (TOMS), v.33 n.2, p.13-es, June 2007 [doi>10.1145/1236463.1236468]
• 9: Pierrick Gaudry , Alexander Kruppa , Paul Zimmermann, A gmp-based implementation of schönhage-strassen's large integer multiplication algorithm, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277572]
• 10: Gosper, R. Strip mining in the abandoned orefields of nineteenth century mathematics. Computers in Mathematics (1990), pp. 261--284.
• 11: Gourdon, X., and Sebah, P. Binary splitting method. http://numbers.computation.free.fr/Constants/Algorithms/splitting.html, 2001.
• 12: GMP: The GNU Multiple Precision Arithmetic Library, 4.2.1 ed., 2006. http://gmplib.org/.
• 13: Bruno Haible , Thomas Papanikolaou, Fast Multiprecision Evaluation of Series of Rational Numbers, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.338-350, June 21-25, 1998
• 14: Karatsuba, E. A. Fast evaluation of transcendental functions. In Problems of Information Transmission, 27: 339--360, 1991.
• 15: Lang, S. Algebraic Number Theory. Springer-Verlag, 1994.
• 16: Schönhage, A., Grotefeld, A. F. W., and Vetter, E. Fast Algorithms, A Multitape Turing Machine Implementation. BI-Wissenschaftsverlag, 1994.
• 17: Schönhage, A. and Strassen, V. Schnelle Multiplikation groβer Zahlen. Computing 7 (1971), 281--292.
• 18: Tenenbaum, G. Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press, 1995.
• 19: Xinmao Wang , Victor Y. Pan, Acceleration of Euclidean Algorithm and Rational Number Reconstruction, SIAM Journal on Computing, v.32 n.2, p.548-556, 2003 [doi>10.1137/S0097539702408636]
• 20: Joris van der Hoeven, Fast evaluation of holonomic functions, Theoretical Computer Science, v.210 n.1, p.199-215, Jan. 6, 1999 [doi>10.1016/S0304-3975(98)00102-9]
• 21: Joris van der Hoeven, Fast evaluation of holonomic functions near and in regular singularities, Journal of Symbolic Computation, v.31 n.6, p.717-743, June 2001 [doi>10.1006/jsco.2000.0474]
• 22: Joris van der Hoeven, Efficient accelero-summation of holonomic functions, Journal of Symbolic Computation, v.42 n.4, p.389-428, April, 2007 [doi>10.1016/j.jsc.2006.12.005]
• 23: Xue, H. gmp-chudnovsky.c code for computing digits of Π using the GNU MP library. Available at http://gmplib.org/pi-with-gmp.html, 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms, Performance

Keywords:
high-precision evaluation, hypergeometric constants