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.

Method

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.

Comparison with other methods

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(n²) multiplication, binary splitting may render no speedup at all or be slower.

Since all subdivisions of the series can be computed independently of each other, binary splitting lends well to parallelization and checkpointing.

In a less specific sense, binary splitting may also refer to any divide and conquer algorithm that always divides the problem in two halves.

gollark: > If any provision of this policy is found by a court (or other entity) to be unenforceable, it nevertheless remains in force.

gollark: > By using potatOS, agreeing to be bound by these terms, misusing potatOS, installing potatOS, reading about potatOS, knowing about these terms, knowing anyone who is bound by these terms, reading these terms, or thinking of anything related to these terms, you agree to be bound by these terms both until the last stars in the universe burn out and the last black holes evaporate and retroactively, arbitrarily far into the past.

gollark: I declare your dibs transferred to me.

gollark: > By using it, you agree that these frogs may throw cookies, and that any "dibs" you make may be transferred to the authors of potatOS at their discretion.PotatOS privacy policy, line 18.

gollark: I call dibs on your deletion and declare it nonexistent.

References

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.