Binary splitting

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 pn and qn 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 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.

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.

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

[edit] References

Retrieved from "http://en.wikipedia.org../../../b/i/n/Binary_splitting.html"