Answers to the frequently asked

questions




Who is the author of the method ‘Binary Splitting’?

The author of the method is A. A. Karatsuba.    ‘Binary Splitting’ is another name of the method ‘Divide and Conquer’.

Who has been developing the method ‘Binary Splitting’ (= ‘Divide and Conquer’) further on?

If by ‘developing’ one one means constructing algorithms based on the ‘Divide and Conquer’, then it was developed and applied in practice by hundreds of people. Among these algorithms the most well known are the algorithms of Fast Fourier Transform (FFT) and Fast Matrix Multiplication.

Who is the author of the method of fast summation of series (of special form) and when this method appeared?

This method (called later the FEE) was discovered by me in 1990. A special feature of the method FEE is that this method makes possible fast evaluation not only of every elementary transcendental function, but also of a lot of higher transcendental functions (such as, for example, the Euler gamma function, Bessel's functions, hypergeometric series), methods of fast calculation of which didn't exist before.

Did any method of fast evaluation of the constant  e  and the constant  π  exist earlier?

Only the method of Arithmetic-Geometric Mean (AGM) of Gauss. By ‘fast evaluation’ we mean the evaluation, the bit complexity of which is asymptotically close to the optimal (the best possible) one.

Why are you claiming that the method of fast computation of sums with the help of the pairwise addition arised in 1990? People added numbers pairwise to calculate their sum since ancient times.

This is not a problem, to put together a few numbers pairwise (or not pairwise). The problem is fast calculation of the sums of the form (1), (2) (see the text ‘Fast algorithms and the FEE method’). Pairwise additions are not sufficient for fast evaluation of such sums.

Is the method ‘Divide and Conquer’ (= ‘Binary Splitting’) used in the calculations performed by means of the FEE?

Yes, of course. It is implied that the products of the numbers are calculated using ‘Binary Splitting’.

Were the algorithms of evaluation of the exponential function with the help of ‘Binary Splitting’ developed before 1990?

Such algorithms were developed indeed. The method ‘Binary Splitting’ is applied for fast computation of a product and it seems natural to apply it for computation of a multiplicative function. However, no fast algorithm for evaluation of the exponential function was constructed, because to represent this function in the form of a ‘well organized’ product is not enough to create a fast algorithm. It is necessary also to calculate fast every factor of this product, and such factor is in it's turn a ‘complicated’ function. That is where the method FEE is needed, to compute fast such function factors.

How is it possible to make difference between the methods ‘Binary Splitting’ and the FEE?

Very easily. 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.

The methods ‘Binary Splitting’ and the FEE are similar: in the first method the multiplied integers are represented in the form on the sum of two integers, in the second one the numbers are summed in pairs. Is it possible to consider the FEE as a ‘parallel Binary Splitting’?

No. These are absolutely different and, in some sense, inverse to each other processes. Besides. The step by step splitting of multiplied integers is insufficient to construct the method of fast multiplication like ‘Binary Splitting’. It is insufficient just to put numbers together in pairs to obtain a fast process of calculation of sums (of the form (1), (2) and similar to them), like the FEE. On the peculiarities of these methods see the text ‘Fast algorithms and the FEE method’.

The method FEE is implemented in some West software packages, including Mathematica and Maple, according to the words of the developers, under the name of ‘Binary Splitting’. May be, it would be worthwhile to agree with this name, if many computer scientists in the West countries call this method by that name?

No. Even in the case if, both the West, and the East, computer scientists say ‘integration’ for ‘differentiation’, integration will not become differentiation for that reason. 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.




J




© Ekatherina Karatsuba
The allocation date is May 15, 2005.
Last correction: October 28, 2005.