Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1101884.1101886 | ACM SIGSAM Bulletin |
Keywords | Field | DocType |
n log,standard binary splitting approach,binary splitting method,numerator anddenominator,higher precision,ofthe size,space-efficient evaluation,high precision,binary splitting approach,series approximation,additional memory,truncated hypergeometric series,size o,computed numerator anddenominator,reduced numerator,hypergeometric series,memory requirement,binary splitting,computed numerator,prediction ofthe size,reduced numerator anddenominator,elementary functions,computer algebra,space complexity,time complexity,fixed point,exponential function,rational number | Hypergeometric function,Integer,Discrete mathematics,Binary logarithm,Rational number,Combinatorics,Polynomial,Binary splitting,Time complexity,Mathematics,Fraction (mathematics) | Journal |
Volume | Issue | Citations |
39 | 2 | 2 |
PageRank | References | Authors |
0.42 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Howard Cheng | 1 | 137 | 18.85 |
| Barry Gergel | 2 | 25 | 2.84 |
| Ethan Kimy | 3 | 2 | 0.42 |
| eugene v zima | 4 | 9 | 2.65 |