Binary splitting
Encyclopedia
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.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, binary splitting is a technique for speeding up numerical evaluation of many types of series
Series (mathematics)
A series is the sum of the terms of a sequence. Finite sequences and series have defined first and last terms, whereas infinite sequences and series continue indefinitely....
with rational terms. In particular, it can be used to evaluate hypergeometric series
Hypergeometric series
In mathematics, a generalized hypergeometric series is a series in which the ratio of successive coefficients indexed by n is a rational function of n. The series, if convergent, defines a generalized hypergeometric function, which may then be defined over a wider domain of the argument by...
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.
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
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
that always divides the problem in two halves.