Binary splitting

In mathematics, Binary splitting(by A.A. Karatsuba) is another name of the fast Divide and Conquer method. This technique was unsuccessfully used in 80-th years for speeding up numerical evaluation of certain types of series. The proposed in that time technique was not enough to construct a fast algorithm for computation of an elementary transcendental function or a classical constant not speaking about general hypergeometric series. There was only one fast method for calculation of exponential or trigonometric funstions at that time --- the Gauss AGM method.

The method of fast calculation of sums of series of a special form was found in 1990 by Ekatherina Karatsuba and was later called the FEE (Fast E-functions Evaluation). The method FEE is at present the second known method (after the AGM) for fast evaluation of classical constants e and π, and elementary transcendental functions. But, unlike the AGM, the FEE is also the method for fast computation of higher transcendental functions. At present the FEE is the unique method, permitting to calculate fast such higher transcendental functions as the Euler Gamma function, hypergeometric, spherical, cylindrical etc. functions for algebraic values of the argument and parameters, the Riemann zeta function for integer values of the argument and the Hurwitz zeta function for integer values of the argument and algebraic values of the parameter.

It is very easy to make difference between the methods Binary Splitting and the FEE: if from step (of the process) to the next step the amount of the integers, participating in the process (of calculation), is increasing, but their length (the amount of their digits) is decreasing, then this is Binary Splitting (= Divide and Conquer): the name of the process corresponds to its essence; splitting means partition or decomposition. If, from step to step, the amount of the participating in the process integers is decreasing, but their length is increasing, then this is the FEE. At the last step of Divide and Conquer multiplication and addition of many low-digit integers are performed. At the last step of the FEE division of one great integer by another great integer is performed. So, the methods Binary Splitting and the FEE are absolutely different and, in some sense, inverse to each other processes.

The method FEE is implemented in some software packages, including Mathematica and Maple, according to the words of the developers who are not specialists in fast algorithms, under the name of Binary Splitting. However, the method of fast summation of the series of special form with the calculated values increasing from step to step, that is, the FEE, can not be called splitting. This is an erroneous name. This is a mistake.

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 process 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.

The FEE 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, FEE 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, FEE may render no speedup at all or be slower.

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

The FEE 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

• Karatsuba, E.A. Fast computation of exp(x). Problems of Information Transmission, v.26, N 3, p.109, Chronicle-17th All-Union School on Theory of Information and its Applications (1990).

• Karatsuba, E.A. On a new method for fast evaluation of transcendental functions. Uspechi Mat. Nauk, v.46, N 2 (278), pp.219-220 (1991).

• Karatsuba, E.A. On fast computation of transcendental functions. (English. Russian original) Sov. Math., Dokl. 43, No.3, 693-694 (1991); translation from Dokl. Akad. Nauk SSSR 318, No.2, 278-279 (1991).

Zbl 0773.65007 MSC2000: *65D20 65Y20 33C15, Reviewer: U.Stadtmüller (Ulm)

• 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).

Zbl 0782.65017 Zbl 0754.65021 MSC2000: *65D20 65Y05 65Y20 Reviewer: M.Tasche (Rostock)

• Karatsuba, E.A. Fast evaluation of $\zeta(3)$. (English. Russian original) Probl. Inf. Transm. 29, No.1, 58-62 (1993); translation from Probl. Peredachi Inf. 29, No.1, 68-73 (1993).

Zbl 0791.11073 MSC2000: *11Y35 11M06, Reviewer: K.Thanigasalam (Monaca)

• Karatsuba, Catherine A. Fast evaluation of Bessel functions. (English) Integral Transforms Spec. Funct. 1, No.4, 269-276 (1993).

Zbl 0827.65022 MSC2000: *65D20 33C10 65Y20, Reviewer: D.Kershaw (Lancaster)

• Karatsuba, E.A. Fast computation of the Riemann zeta-function $\zeta (s)$ for integer values of the argument $s$. (English. Russian original) Probl. Inf. Transm. 31, No.4, 353-362 (1995); translation from Probl. Peredachi Inf. 31, No.4, 69-80 (1995).

Zbl 0895.11032 Zbl 0859.11050 MSC2000: *11M06 11Y35 11Y60 Reviewer: A.Ivic (Beograd)

• Karatsuba, E.A. On fast computation of the Riemann zeta function for integer argument. (English. Russian original) Dokl. Math. 54, No.1, 626 (1996); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 349, No.4, 463 (1996).

Zbl 0923.11172 MSC2000: *11Y35 11M06 11Y60

• Karatsuba, E.A. Fast evaluation of the Hurwitz zeta function and Dirichlet $L$-series. (English. Russian original) [J] Probl. Inf. Transm. 34, No.4, 342-353 (1998); translation from Probl. Peredachi. Inf. 34, No.4, 62-75 (1998).

Zbl 0928.11056 ISSN 0032-9460; ISSN 1608-3253 Reviewer:E.Elizalde (Barcelona)

• Karatsuba, Ekatharine A. Fast evaluation of hypergeometric function by FEE. Computational Methods and Function Theory (CMFT'97), N.Papamichael, St.Ruscheweyh and E.B.Saff, eds., World Sc.Pub., pp.303-314 (1999).

• Karatsuba, E.A. On the computation of the Euler constant gamma. University of Helsinki preprint, 21 pp. (1999); J. of Numerical Algorithms, v.24, pp.83-97 (2000).

• Karatsuba, E.A Fast computation of ζ(3) and of some special integrals, using the polylogarithms, the Ramanujan formula and it's generalization. J. of Numerical Mathematics BIT, v. 41, N 4, pp.722-730 (2001).

• Karatsuba, E.A. Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W.Kramer,J.W.von Gudenberg,eds., pp.29-41 (2001).

• 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).

• Ekatherina Karatsuba. Fast Algorithms and the FEE method
• Ekatherina Karatsuba. Binary Spltting = Divide and Conquer
• Ekatherina Karatsuba. FAQ