🌐Japanese

Karatsuba Multiplication

2012-11-29
Takayuki HOSODA

Overview

To multiply two n-digit numbers using the ordinary long-multiplication method requires a computational complexity of Ο(n2) .
In contrast, the Karatsuba method reduces the complexity to Ο(n log23) .

Note: For multiplications involving numbers with several thousand digits or more, algorithms based on the FFT or the Chinese Remainder Theorem are generally more suitable.
The method is named after its discoverer, Anatolii Alexeevitch Karatsuba (Russian: „K„p„‚„p„ˆ„…„q„p, „@„~„p„„„€„|„y„z „@„|„u„{„ƒ„u„u„r„y„‰).

Computing the Product of Two 2n-Digit Numbers X and Y

First, split X and Y into their upper n digits and lower n digits:
X = a R + b Y = c R + d
Then their product can be written as:
X Y = (a R + b) (c R + d) = a c + (a d + b c) R + b d … (1)
Here, instead of directly computing the cross term (ad + bc), we reuse the already computed products ac and bd, thereby reducing the number of n-digit multiplications by one:
(a - b) (c - d) = a c - (a d + b c) + b d
Therefore,
(a d + b c) = a c + b d - (a - b)(c - d) c (2)
Substituting (2) into (1) yields:
X Y = a c R2 + (a c - (a - b)(c - d) + b d ) R + b d c (3)
Thus, the multiplication of two 2n-digit numbers has been reduced to three multiplications of n-digit numbers and six additions.

In other words, when the number of digits doubles, the multiplication cost increases by only a factor of three.

Example: Multiplying Two 6-Digit Decimal Numbers

As a concrete example, consider the multiplication of the following two 6-digit decimal numbers: 
X = 123456
Y = 789012
Let R = 103 = 1000. Split X into its upper and lower three digits: 
a = 123
b = 456
Split Y similarly: 
c = 789
d =  12
Compute each term in equation (3): 
a c = 97047
b d =  5472
(a - b)(c - d) = -258741
Written as a single expression: 
X Y 
= 97047 R2 + (97047 - (-258741) + 5472 ) R + 5472
    = 97408265472
Displayed in a long-multiplication?like form: 
   97 047          ← R2
 +     97 047      ← R
 -   -258 741      ← R
 +      5 472      ← R
 +          5 472
------------------        
 = 97 408 265 472

This example demonstrates how the multiplication of two large numbers can be decomposed into three smaller multiplications and six additions.

REFERENCE

  1. Karatsuba, A. A.; Ofman, Y. P. (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences (in Russian). 145: 293–294. "Translation in the academic journal Physics-Doklady, 7 (1963), pp. 595–596"
  2. Knuth, Donald E. (1969). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (1st ed.). Addison-Wesley. See Section 4.3.3 for discussion of Karatsuba–Ofman multiplication.

SEE ALSO

www.finetune.co.jp [Mail] © 2000 Takayuki HOSODA.