Algorithm of Karatsuba

The algorithm of Karatsuba (1960) is a method making it possible to quickly multiply two numbers with a complexity out of O ( $n^ {\ ln (3)/\ ln (2)}$ ). Note: $\ ln (3)/\ ln (2)$ is approximately equal to 1,58.

Statement

To multiply two numbers of N figures, the usual method requires to multiply each figure of the multiplier by each figure of the multiplicand. That thus requires produced N ² of two digits. It is said that the computing time is out of O ( N ²).

In 1960, Karatsuba, noticing that the calculation of ( has × 10^K + B ) ( C × 10^K + D ) which, in developed form ac × 10^{2 K} + ( AD + bc ) × 10^K + data base , seems to require the four products ac , AD , bc and data base , can in fact being only carried out with the three products ac , data base and ( has - B ) ( C - D ) by gathering calculations in the following form:

( has × 10^K + B ) ( C × 10^K + d) = ac × 10^{2 K} + (ac + data base - ( has - B ) ( C - D )) × 10^K + data base Thus, to calculate 26 × 34, one calculates

2 × 3 = 6

6 × 4 = 24

(2 - 6) × (3 - 4) = 4

The end result is then 6 × 100 + (6 + 24 - 4) × 10 + 24 = 600 + 260 + 24 = 884. Multiplication by the base of numeration (10 in the preceding example but into binary for the machines) which corresponds to a shift of figure, and the additions are inexpensive in time. For great numbers, the method can be reiterated for calculations of ac , data base and ( has - B ) ( C - D ) by dividing again has , B , C and D into two and so on.

Example

Thus, 12378456 × 25874215 will be calculated as follows:

1237 × 2587

8456 × 4215

(1237 - 8456) × (2587 - 4215) = 7219 × 1628

The product 1237 × 2587 itself will be calculated as follows:

12 × 25

37 × 87

(12 - 37) × (25 - 87) = 25 × 62

The product 12 × 25 will be calculated by means of:

1 × 2 = 2

2 × 5 = 10

(1 - 2) × (2 - 5) = 1 × 3 = 3

to obtain 12 × 25 = 2 × 100 + (2 + 10 - 3) × 10 + 10 = 300. One will obtain in the same way:

12 × 25 = 300

37 × 87 = 3219

25 × 62 = 1550

from where 1237 × 2587 = 300 × 100² + (300 + 3219 - 1550) × 100 + 3219 = 3000000 + 196900 + 3219 = 3200119. One will proceed in the same way for the products 8456 × 4215 and 7219 × 1628, obtaining finally:

1237 × 2587 = 3200119

8456 × 4215 = 35642040

7219 × 1628 = 11752532

From where, finally: 12378456 × 25874215 = 3200119 × 10000² + (3200119 + 35642040 - 11752532) × 10000 + 35652040

= 320011900000000 + 270896270000 + 35642040

= 320282831912040

Complete calculation asks for only 27 products of two digits instead of 64 by the usual method. Of course, this method, tiresome with the hand, reveals all its power for a machine having to carry out the product of great numbers. One then obtains an algorithm known as of fast multiplication of two numbers of N figures in $n^ {\ ln (3)/\ ln (2)}$ elementary operations (such as produces or summons of two digits) instead of N ². For N = 1000, $n^ {\ ln (3)/\ ln (2)}$ is about 50.000 whereas N ² = 1.000.000.

Toom and Cook improved this method by cutting out the numbers in R blocks (instead of 2). The computing time out of O ( N ²) by the usual method passes then out of O ( N ^1+ε) where ε is an arbitrary positive reality.

Refer

A. Karatsuba and Yu Ofman, Multiplication off Many-DIGITAL Numbers by Automatic Computers. Doklady Akad. Nauk SSSR vol. 145 (1962), pp. 293– 294. Translation in Physics-Doklady 7 (1963), pp. 595– 596.
Karacuba A.A. Berechnungen und die Kompliziertheit von Beziehungen (German) // Elektron. Inform. - verarb. Kybernetik, 11,603-606 (1975).
Karatsuba A.A. The complexity off computations // Proc. Steklov Inst. Maths., 211,169-183 (1995); translation from Trudy Chechmate. Inst. Steklova, 211,186-202 (1995).
Knuth D.E. The art off computer programming. v.2 . Addison-Wesley Publ.Co., 724 pp., Reading (1969).
Algorithm of Karatsuba for the Fast multiplication
Karatsuba Multiplication one Fast Algorithms and the FAIRY

See too

Technical of multiplication
Algorithm Toom-Cook
Anatolii Alexevich Karatsuba

Random links: