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

(a + bx)2 = a2 + ((a + b)2 – a2 – b2)x + b2x2,

the second one — on the formula

(a + bx)(c + dx) = ac + ((a + b)(c + d) – ac – bd)x + bdx2.

I.      Since  4ab = (a + b)2 – (a – b)2 the multiplication of two numbers  a  and  b  is equivalent in the complexity of realization to the squaring. Assume that  X  is a  n -digit integer, that is

X = ε0 + 2ε1 + ... + 2n–1εn–1,

where  εj = 0  or  1,   j = 0, 1, ..., n-1.  Assume for simplicity that  n = 2m,   m ≥ 1;   2k = n.  Representing  X  in the form

X = X1 + 2kX2,

where

X1 = ε0 + 2ε1 + ... + 2k–1εk–1 ,
X2 = εk + 2εk+1 + ... + 2k–1εn–1 ,

we find

 X2 = (X1 + 2kX2)2 = X12+ ((X1 + X2)2 – (X12 + X22))2k + X222n. (1)

The integers  X1  and  X2  are  k -digit ones. The integer  X1 + X2  can have  k+1 digits. In that case we represent it in the form  2X3 + X4,  where  X3  is a  k -digit integer,  X4  is a one-digit integer. Then

 (X1 + X2)2 = 4X32 + 4X3X4 + X42 . (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  3φ(k) = 3φ(n2–1)  operations. The number of operations, required by the remaining calculations in the right-hand side of (1), namely, the multiplication by  4, 2k, 2n,  five additions and one subtraction of no more than  2n -digit integers, is of order at most  :n.  This implies (3). Applying (3) successively to  φ(n2–1),  φ(n2–2) , ... , φ(n2–m+1)  and taking into account that  φ(n2–m) = φ(1) =1,  we obtain

φ (n) ≤ 3(φ(n2–1) + cn2–1) + cn = 32φ(n2–2) + 3cn2–1 + cn ≤ ... ≤
≤   3mφ(n2–m) + 3m–1c(n2–m+1) + 3m–2c(n2–m+2) + ... + 3 c(n2–1) + cn =
= 3m + cn((3/2)m–1 + (3/2)m–2 + … + (3/2) + 1) =
= 3m + 2cn((3/2)m – 1) < 3m (2c + 1) = (2c+1) nlog 23

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) nlog 23 ,   log 2 3 = 1,5849... . (4)

If  n  is not a power of two, then determining an integer  m  by the inequalities  2m–1 < n ≤ 2m,  we represent  X  as a  2m -digit integer, that is we set the last  2m–n  digits to be equal to zero:  εn = ... = ε2m–1 = 0.  All the rest of the arguments work as they are and the resulting upper bound for  φ(n)  is the same, by order of  n.

II.      The second version is the direct multiplication of two  n -digit integers. Assume, as before, that  n = 2m,   2k = n;   A  and  B  are two  n -digit integers. Representing  A  and  B  in the form

A = A1 + 2kA2 ,   B = B1 + 2kB2,

where  A1, A2, B1, B2 are k -digit integers, we find:

 AB = A1B1 + 2k((A1 + A2)(B1 + B2) – (A1B1 + A2B2)) + 2nA2B2 . (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 = x2  at the point  x = x1   with the accuracy up to  n  digits. If one splits  X  into more than two summands, then it is possible to obtain asymptotically better bounds for the complexity of calculating the product (respectively, squaring). The method ‘Divide and Conquer’ (its other names are ‘The Dichotomy Principle’, ‘Binary Splitting’, etc.) is the fundamental and most general fast method. Hundreds of different algorithms are constructed on its basis.

J

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

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