🌐English

Karatsuba 法による乗算

2012-11-29
Takayuki HOSODA

概要

筆算の方法で n 桁の乗算を行うには Ο(n2) の計算量が必要であるが、 Karatsuba 法では Ο(n log23) の計算量で計算できる。

※但し、数千桁を越える乗算の場合には FFT や 中国人剰余定理 による乗算が望ましい。
※発見者 Anatolii Alexeevitch Karatsuba (ロシア語: Карацуба, Анатолий Алексеевич) の名前をとって Karatsuba 法と呼ぶ。

2n 桁の数 X と Y の積を求める

まず、X, Y を上位 n 桁と下位 n 桁に分割し
X = a R + b Y = c R + d
と表現すると
X Y = (a R + b) (c R + d) = a c + (a d + b c) R + b d … (1)
ここで、交差項 (a d + b c) を直接計算せず、既に計算した a c と b d を再利用することで n 桁同士の乗算回数を 1 回削減できる：
(a - b) (c - d) = a c - (a d + b c) + b d
であるから、
(a d + b c) = a c + b d - (a - b)(c - d) … (2)
(1) に (2) を代入して
X Y = a c R2 + (a c - (a - b)(c - d) + b d ) R + b d … (3)
となって、2n 桁の数の掛け算が n 桁の数の３つの乗算と６つの加算に分解できた。

つまり、桁数が 2 倍になったときに乗算の計算量が 3 倍で済む ということである。

10進 6 桁の数の掛け算の例

具体例として、次の２つの 10進 6 桁の数の掛け算を考えてみる： 
X = 123456
Y = 789012
R = 103 = 1000 として、 X を上位 3 桁と、下位 3 桁に分けて： 
a = 123
b = 456
同様に、Y を上位 3 桁と、下位 3 桁に分けて： 
c = 789
d =  12
(3) 式における各々の項を計算すると： 
a c = 97047
b d =  5472
(a - b)(c - d) = -258741
一つの式で書くと： 
X Y 
= 97047 R2 + (97047 - (-258741) + 5472 ) R + 5472
    = 97408265472
これを筆算的に書くと： 
   97 047          ← R2
 +     97 047      ← R
 -   -258 741      ← R
 +      5 472      ← R
 +          5 472
------------------        
 = 97 408 265 472

このようにして、大きな２つの数の乗算が小さな数の３つの乗算と６つの加算に分解して計算できることが示された。

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.