Binary splitting

In mathematics, binary splitting is a technique for speeding up numerical evaluation of many types of series with rational terms. In particular, it can be used to evaluate hypergeometric series at rational points. Given a series

$S(a,b)=\sum _{n=a}^{b}{\frac {p_{n}}{q_{n}}}$

where p_n and q_n are integers, the goal of binary splitting is to compute integers P(a, b) and Q(a, b) such that

$S(a,b)={\frac {P(a,b)}{Q(a,b)}}.$

The splitting consists of setting m = [(a+b)/2] and recursively computing P(a, b) and Q(a, b) from P(a, m), P(m, b), Q(a, m), and Q(m, b). When a and b are sufficiently close, P(a, b) and Q(a, b) can be computed directly from p_a...p_b and q_a...q_b.

Binary splitting requires more memory than direct term-by-term summation, but is asymptotically faster since the sizes of all occurring subproducts are reduced. Whereas the most naive evaluation scheme of a rational series uses a full-precision division for each term in the series, binary splitting also requires only one final division at the target precision; this is not only faster, but conveniently eliminates rounding errors. To take full advantage of the scheme, fast multiplication algorithms such as Toom-Cook and Schönhage-Strassen must be used; with ordinary O(n²) multiplication, binary splitting may render no speedup at all or be slower.

Binary splitting is used by the fastest existing software for computing mathematical constants such as π and e to high accuracy. It can be used more generally to evaluate many common special functions of arbitrary arguments; however, it is mainly useful when the argument is a small rational number.

References

• Xavier Gourdon & Pascal Sebah. Binary splitting method
• Bruno Haible & Thomas Papanikolaou. Fast multiprecision evaluation of series of rational numbers. Technical Report No. TI-7/97, Darmstadt University of Technology, 1997