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
where pn and qn are integers, the goal of binary splitting is to compute integers P(a, b) and Q(a, b) such that
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 pa...pb and qa...qb.
Binary splitting requires more memory than direct term-by-term summation, but is asymptotically faster since the sizes of all occurring subproducts are reduced. Additionally, whereas the most naive evaluation scheme for a rational series uses a full-precision division for each term in the series, binary splitting 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(n2) multiplication, binary splitting may render no speedup at all or be slower.
In a less specific sense, binary splitting may also refer to any divide and conquer algorithm that always divides the problem in two halves.
- Xavier Gourdon & Pascal Sebah. Binary splitting method
- David V. Chudnovsky & Gregory V. Chudnovsky. Computer algebra in the service of mathematical physics and number theory. In Computers and Mathematics (Stanford, CA, 1986), pp. 09–232, Dekker, New York, 1990.
- Bruno Haible, Thomas Papanikolaou. Fast multiprecision evaluation of series of rational numbers. Paper distributed with the CLN library source code.
- Lozier, D.W. and Olver, F.W.J. Numerical Evaluation of Special Functions. Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics, W.Gautschi, eds., Proc. Sympos. Applied Mathematics, AMS, v.48, pp. 79–125 (1994).
- Bach, E. The complexity of number-theoretic constants. Info. Proc. Letters, N 62, pp. 145–152 (1997).
- Borwein, J.M., Bradley, D.M. and Crandall, R.E. Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math., v.121, N 1-2, pp. 247–296 (2000).
- Karatsuba, E.A. Fast evaluation of transcendental functions. (English. Russian original) Probl. Inf. Transm. 27, No.4, 339-360 (1991); translation from Probl. Peredachi Inf. 27, No.4, 76–99 (1991).
- Ekatherina Karatsuba. Fast Algorithms and the FEE method