Space-efficient evaluation of hypergeometric series

ABSTRACT

Many important constants, such as e and Apéry's constant ζ(3), can be approximated by a truncated hypergeometric series. The evaluation of such series to high precision has traditionally been done by binary splitting followed by fixed-point division. However, the numerator and the denominator computed by binary splitting usually contain a very large common factor. In this paper, we apply standard computer algebra techniques including modular computation and rational reconstruction to overcome the shortcomings of the binary splitting method. The space complexity of our algorithm is the same as a bound on the size of the reduced numerator and denominator of the series approximation. Moreover, if the predicted bound is small, the time complexity is better than the standard binary splitting approach. Our approach allows a series to be evaluated to a higher precision without additional memory. We show that when our algorithm is applied to compute ζ(3), the memory requirement is significantly reduced compared to the binary splitting approach.

REFERENCES

• 1: T. Amdeberhan. Faster and faster convergent series for ζ(3). Electronic Journal of Combinatorics, 3, 1996.
• 2: T. Amdeberhan and D. Zeilberger. Hypergeometric series acceleration via the WZ method. Electronic Journal of Combinatorics, 4, 1997.
• 3: D. J. Bernstein. Fast multiplication and its applications. To appear in Buhler-Stevenhagen Algorithmic number theory book.
• 4: J. Borwein and P. Borwein. Pi and the AGM. John Wiley and Sons, 1987.
• 5: 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]
• 6: 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]
• 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: George E. Collins , Mark J. Encarnación, Efficient rational number reconstruction, Journal of Symbolic Computation, v.20 n.3, p.287-297, Sept. 1995 [doi>10.1006/jsco.1995.1051]
• 9: R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert W function. Advances in Computational Mathematics, 5:329--359, 1996.
• 10: R. W. Gosper. Strip mining in the abandoned orefields of nineteenth century mathematics. In Computers in Mathematics, pages 261--284. Dekker, New York, 1990.
• 11: X. Gourdon and P. Sebah. Numbers, constants and computation. http://numbers.computation.free.fr/Constants/constants.html.
• 12: 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
• 13: G. Hanrot, E. Thomé, and P. Zimmermann. A new algorithm for hypergeometric constants. Private Communication, 2005.
• 14: E. A. Karatsuba. Fast evaluation of ζ(3). Problemy Peredachi Informatsii, 27:68--73, 1993.
• 15: Michael Monagan, Maximal quotient rational reconstruction: an almost optimal algorithm for rational reconstruction, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.243-249, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005321]
• 16: Peter Lawrence Montgomery, An FFT extension of the elliptic curve method of factorization, University of California at Los Angeles, Los Angeles, CA, 1992
• 17: K. H. Rosen. Elementary Number Theory and Its Applications. Addison-Wesley, 1992.
• 18: J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6:64--94, 1962.
• 19: A. Schönhage. Schnelle berechnung von kettenbruchentwicklungen. Acta Informatica, 1:139--144, 1971.
• 20: A. Schönhage and V. Strassen. Schnelle multiplikation großer zahlen. Computing, 7:281--292, 1971.
• 21: Paul S. Wang , M. J. T. Guy , J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin, v.16 n.2, p.2-3, May 1982 [doi>10.1145/1089292.1089293]
• 22: 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]
• 23: Eugene V. Zima, Simplification and optimization transformations of chains of recurrences, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.42-50, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220352]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Special function approximations

General Terms:
Algorithms, Performance