Here two equivalent versions of the Karatsuba
method **‘Divide and Conquer’ (‘Binary Splitting’)** are presented. The first version is based on the formula.

the second one — on the formula

**I.**
Since **4ab = (a + b) ^{2} – (a – b)^{2}, ** the multiplication of two numbers

where **ε _{j} = 0** or

where

we find

X^{2} = (X_{1} + 2^{k}X_{2})^{2} = X_{1}^{2}+ ((X_{1} + X_{2})^{2} – (X_{1}^{2} + X_{2}^{2}))2^{k} + X_{2}^{2}2^{n}. | (1) |

The integers **X _{1}** and

(X_{1} + X_{2})^{2} = 4X_{3}^{2} + 4X_{3}X_{4} + X_{4}^{2} .
| (2) |

We denote by **φ(n)** the number of operations sufficient for the squaring of a **n** -digit integer by means of the formula (1). It follows from (1) that **φ(n)** satisfies the inequality

φ(n) ≤ 3φ(n2^{–1}) + cn ,
| (3) |

where **c > 0** is an absolute constant. Indeed, taking into account (2), the right-hand side of (1) contains the sum of three squares of **k** -digit integers, **k = n2 ^{–1},**
to calculate which we need

Hence, the total number **φ(n)** of operations sufficient for the squaring of a **n** -digit integer by means of the formula (1), satisfies the bound

φ(n) < (2c+1) n^{log 23} , log _{2} 3 = 1,5849... .
| (4) |

If **n** is not a power of two, then determining an integer **m** by the inequalities
**2 ^{m–1} < n ≤ 2^{m},** we represent

**II.**
The second version is the direct multiplication of two **n** -digit integers. Assume, as before, that **n = 2 ^{m}, 2k = n; A** and

where **A _{1}, A_{2}, B_{1}, B_{2} are k** -digit integers, we find:

AB = A_{1}B_{1} + 2^{k}((A_{1} + A_{2})(B_{1} + B_{2}) – (A_{1}B_{1} + A_{2}B_{2})) + 2^{n}A_{2}B_{2} .
| (5) |

Thus, in this case the formula (1) is replaced by the formula (5). If we denote by the symbol **φ(n)** the number of operations sufficient for the multiplication of two **n**-digit integers by means of the formula (5), then for **φ(n)** the inequality (3) holds, and therefore, the inequality (4) is true. Note that, the foregoing first way of multiplication can be treated as an algorithm of computation of the function **y = x ^{2}** at the point

For the history of creating the method, see: A. A. Karatsuba “The complexity of computations” Proc. Steklov Inst. Math., Vol. 211, pp. 169-183 (1995).

On the method **‘Divide and Conquer’** and how it is used one can read at the numerous web-pages, for example

- http://212.cmc-msu.ru/files/kniga.html
- http://educeth.ethz.ch/informatik/werkstatt/multiplik/smult/
- http://gersoo.free.fr/docs/karat/kar.html
- http://numbers.computation.free.fr/Constants/Algorithms/representation.html
- http://www-math.uni-paderborn.de/mca/mult.html
- http://www.cs.pitt.edu/~kirk/cs1501/animations/
- http://www.cs.princeton.edu/introcs/79crypto/Karatsuba.java.html
- http://www-2.cs.cmu.edu/~cburch/251/karat/

Fast Algorithms and the FEE Method

*) If any mathematical symbols or formulas are not visible correctly than you can see them in the same file in MS-Word format (73,216 bites).

© Ekatherina Karatsuba

The allocation date is May 11, 2005.

Last correction: September 14, 2005.