Space-efficient evaluation of hypergeometric series
Authors: Cheng Howard , Gergel Barry , Kim Ethan , Zima Eugene 
Published: January 2007

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> &gt; 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&eacute;ry's constant &zeta;(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 &zeta;(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 &zeta;(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.