Space-efficient evaluation of hypergeometric series

We consider the evaluation of the truncated hypergeometric series [EQUATION] to high precision, where <i>a, b, p</i>, and <i>q</i> are polynomials with integer coefficients, and <i>a</i>(<i>n</i>), <i>b</i>(<i>n</i>), <i>p</i>(<i>n</i>), <i>q</i>(<i>n</i>) have bit length <i>O</i>(log <i>n</i>). We also assume that the series is linearly convergent, so that the <i>n</i>th term of (1) is <i>O</i>(<i>c<sup>-n</sup></i>) with <i>c</i> > 1. These series are commonly used in the high precision evaluation of elementary functions and other constants, including the exponential function, logarithms, trigonometric functions, and constants such as the Apéry's constant ζ(3) [9, 10]. "Binary splitting" is an approach that has been independently discovered and used by many authors in the computation of (1) [2, 3, 4, 5, 8, 10, 12]. Binary splitting computes the numerator and denominator of the rational number <i>S</i>(<i>N</i>). The decimal representation of <i>S</i>(<i>N</i>) is then computed by fixed-point division of the numerator by the denominator. The binary splitting approach takes advantage of the special form of the series (1) to obtain a denominator that is relatively small (of size <i>O</i>(<i>N</i> log <i>N</i>)). It also takes advantage of fast integer multiplication to obtain a time complexity of <i>O</i>((log <i>N</i>)<sup>2</sup>M(<i>N</i>)), where M(<i>N</i>) = <i>O</i>(<i>N</i> log <i>N</i> log log <i>N</i>) is the complexity of integer multiplication of two <i>N</i>-bit integers [16]. The space complexity of the algorithm is <i>O</i>(<i>N</i> log <i>N</i>), the size of the computed numerator and denominator. Typically, the numerator and denominator computed by binary splitting have large common factors. For example, in the computation of 640000 digits of ζ(3), as much as 86% of the size of the computed numerator and denominator can be attributed to their common factor [7]. Empirically, we have observed that the size of the reduced numerator and denominator is <i>O</i>(<i>N</i>) instead of <i>O</i>(<i>N</i> log <i>N</i>) as computed by binary splitting. The additional digits computed not only slow down the final division but also require more memory to be used during the computation. For computing a large number of decimal digits, either the computation cannot be done at all or some data would have to be swapped out of memory, increasing the computation time dramatically. In this poster, we study the application of well-known techniques in computer algebra to the evaluation of (1). If a bound on the size of the <i>reduced</i> numerator and denominator is known, we can compute the image of <i>S</i>(<i>N</i>) in (1) under an appropriately chosen modulus. Fast rational number reconstruction can then be applied to recover the reduced numerator and denominator [13, 14, 15, 17]. We show how to apply our techniques to the computation of ζ(3), including the prediction of the size of the reduced numerator and denominator. In particular, we obtain the desired <i>O</i>(<i>N</i>) bound on the size of reduced numerator and denominator, which is an interesting result by itself. The techniques used in the analysis can be applied to similar hypergeometric series.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.