カラツバアルゴリズム

カラツバアルゴリズムは、高速な乗算アルゴリズムです。 1960年にアナトリー・カラツバによって発見され、1962年に発表されました。 ^{[1] [2] [3]}これは、 2つのn桁の数の乗算をn /2桁の数の3回の乗算に減らし、この削減を繰り返すことで、最大で1桁の乗算に減らす分割統治アルゴリズムです。したがって、1桁の積を実行する従来のアルゴリズムよりも漸近的に高速です。 ${\displaystyle n^{\log _{2}3}\approx n^{1.58}}$${\displaystyle n^{2}}$

Karatsuba アルゴリズムは、2 次「小学校」アルゴリズムよりも漸近的に高速な最初の乗算アルゴリズムでした。Toom -Cook アルゴリズム(1963) は Karatsuba 法の高速な一般化であり、Schönhage-Strassen アルゴリズム(1971) は十分に大きいnに対してさらに高速です。

2 つのn桁の数字を乗算する標準的な手順では、 （ビッグ O 記法 ）に比例する数の基本演算が必要です。アンドレイ・コルモゴロフは、従来のアルゴリズムが漸近的に最適であると推測しました。つまり、そのタスクのアルゴリズムには基本演算が必要になるということです。 ${\displaystyle n^{2}\,\!}$${\displaystyle O(n^{2})\,\!}$${\displaystyle \オメガ (n^{2})\,\!}$

1960年、コルモゴロフはモスクワ国立大学でサイバネティクスにおける数学的問題に関するセミナーを開催し、この予想と計算の複雑さに関するその他の問題について述べた。1週間以内に、当時23歳の学生だったカラツバは、2つのn桁の数字を基本的なステップで乗算するアルゴリズムを発見し、この予想を反証した。コルモゴロフはこの発見に非常に興奮し、その後終了したセミナーの次の会合でそれを発表した。コルモゴロフは、世界中の会議でカラツバの結果に関する講演を行い（たとえば、「1962年国際数学者会議の議事録」の351～356ページ、および「1962年ストックホルム国際数学者会議での6つの講演」を参照）、1962年にこの手法をソ連科学アカデミーの議事録で発表した。この論文はコルモゴロフによって書かれ、乗算に関する2つの結果、カラツバのアルゴリズムとユーリ・オフマンによる別の結果が含まれていた。著者として「A. カラツバとユーリ・オフマン」と記載されていた。カラツバは出版社から論文の再版を受け取ったときに初めてこの論文を知った。^[2]${\displaystyle \オメガ (n^{2})\,\!}$${\displaystyle O(n^{\log _{2}3})}$

カラツバのアルゴリズムの基本原理は分割統治法であり、2 つの大きな数の積を計算できる公式を使用し、それぞれまたはの約半分の桁数を持つ 3 回の小さな数の乗算と、いくつかの加算および桁シフトを使用します。この基本ステップは、実際には、虚数単位i が底の累乗に置き換えられた、同様の複雑な乗算アルゴリズムの一般化です。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

とを の基数で - 桁の文字列として表す。未満の任意の正の整数に対して、与えられた 2 つの数は次のように表すことができる。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle n}$${\displaystyle B}$${\displaystyle m}$${\displaystyle n}$

${\displaystyle x=x_{1}B^{m}+x_{0},}$

${\displaystyle y=y_{1}B^{m}+y_{0},}$

ここで、およびは より小さい。積は ${\displaystyle x_{0}}$${\displaystyle y_{0}}$${\displaystyle B^{m}}$

${\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}$

どこ

${\displaystyle z_{2}=x_{1}y_{1},}$

${\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}$

${\displaystyle z_{0}=x_{0}y_{0}.}$

これらの公式は4回の掛け算を必要とし、チャールズ・バベッジにも知られていました。^[4]カラツバは、数回の加算を犠牲にして、3回の掛け算だけで計算できることを観察しました。 と を前と同様に使用する と、${\displaystyle xy}$${\displaystyle z_{0}}$${\displaystyle z_{2}}$${\displaystyle z_{3}=(x_{1}+x_{0})(y_{1}+y_{0}),}$

${\displaystyle {\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=(x_{1}+x_{0})(y_{0} +y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=z_{3}-z_{2}-z_{0}.\\\end{aligned} }}$

したがって、計算には3回の乗算のみが必要であり、${\displaystyle z_{0},z_{1}}$${\displaystyle z_{2}.}$

12345 と 6789 の積を計算するには( B = 10)、m = 3 を選択します。結果の基数 ( B ^m = 1000 ) を使用して入力オペランドを分解するには、次のようにm回の右シフトを使用します。

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

3 つの部分的な結果を計算するために、小さい整数に対して実行される 3 つの乗算のみが使用されます。

2 = 12 × 6 ₌ 72

0 = 345 × 789 ₌ 272205

z ₁ = ( 12 + 345 ) × ( 6 + 789 ) − z ₂ − z ₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

これら 3 つの部分的な結果を加算し、それに応じてシフトするだけで結果が得られます (次に、入力オペランドと同様に、これら 3 つの入力を1000進数で分解して繰り上がりを考慮します)。

結果 = z ₂ · ( B ^m ) ² + z ₁ · ( B ^m ) ¹ + z ₀ · ( B ^m ) ⁰、すなわち

結果 = 72 · 1000 ² + 11538 · 1000 + 272205 = 83810205。

中間の 3 番目の乗算は、最初の 2 つの乗算の 2 倍未満の大きさの入力ドメインで実行され、その出力ドメインは 4 倍未満の大きさであり、最初の 2 つの乗算から計算された1000進数の繰り上がりは、これらの 2 つの減算を計算するときに考慮する必要があることに注意してください。

nが 4 以上の場合、Karatsuba の基本ステップの 3 つの乗算には、 n桁未満のオペランドが含まれます。したがって、これらの積は、Karatsuba アルゴリズムの再帰呼び出しによって計算できます。数値が直接計算できる (または計算しなければならない) ほど小さくなるまで、再帰を適用できます。

たとえば、完全な 32 ビット x 32 ビットの乗算器を備えたコンピュータでは、 B = 2 ³¹を選択して、各桁を別々の 32 ビットのバイナリ ワードとして保存できます。すると、合計x ₁ + x ₀とy ₁ + y _{0では、繰り上がり桁を保存するための追加のバイナリ ワードは必要なくなり (}繰り上がり保存加算器の場合のように)、乗算する数字が 1 桁になるまで Karatsuba 再帰を適用できます。

Karatsuba の基本ステップは、任意の基数Bと任意のmに対して機能しますが、再帰アルゴリズムは、m がn /2に等しい場合に最も効率的です(切り上げ)。特に、nが 2 ^kで、ある整数kに対して再帰がnが 1 のときにのみ停止する場合、1 桁の乗算の回数は 3 ^kで、これはc = log ₂ 3のn ^cです。

任意の入力をゼロ桁で拡張して長さを 2 の累乗にすることができるため、任意のnに対して、基本的な乗算の回数は最大 になります。 ${\displaystyle 3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!}$

カラツバの基本ステップにおける加算、減算、桁シフト（Bの累乗による乗算）はnに比例した時間がかかるため、 nが増加するにつれてそのコストは無視できるようになります。より正確には、T（n ）が2つのn桁の数字を乗算するときにアルゴリズムが実行する基本演算の総数を表す場合、

${\displaystyle T(n)=3T(\lceil n/2\rceil )+cn+d}$

定数cとdに対して、この再帰関係に対して、分割統治再帰のマスター定理により漸近境界が得られます。 ${\displaystyle T(n)=\Theta (n^{\log _{2}3})\,\!}$

したがって、nが十分に大きい場合、Karatsuba のアルゴリズムでは、その基本ステップで単純な式よりも多くの加算とシフトが使用されるにもかかわらず、長手による乗算よりもシフトと 1 桁の加算が少なくなります。ただし、 nの値が小さい場合は、余分なシフト操作と加算操作により、長手による方法よりも実行速度が遅くなる可能性があります。

以下は、10進数で表された数値を使用したこのアルゴリズムの擬似コードです。整数の2進数表現では、すべての10を2に置き換えるだけで十分です。^[5]

split_at 関数の 2 番目の引数は、右側から抽出する桁数を指定します。たとえば、split_at("12345", 3) は最後の 3 桁を抽出し、high="12", low="345" になります。

function karatsuba ( num1 , num2 ) if ( num1 < 10 or num2 < 10 ) return num1 × num2 /* 従来の乗算に戻ります */ /* 数値のサイズを計算します。 */ m = max ( size_base10 ( num1 ), size_base10 ( num2 )) m2 = floor ( m / 2 ) /* m2 = ceil (m / 2) も機能します */ /* 数字のシーケンスを途中で分割します。 */ high1 、low1 = split_at ( num1 、m2 ) high2 、low2 = split_at ( num2 、m2 ) /* 約半分のサイズの数値に対して 3 回の再帰呼び出しが行われます。 */ z0 =カラツバ( low1 , low2 ) z1 =カラツバ( low1 + high1 , low2 + high2 ) z2 =カラツバ( high1 , high2 ) return ( z2 × 10 ^ ( m2 × 2 )) + (( z1 - z2 - z0 ) × 10 ^ m2 ) + z0  
           
            
    
    
       
         
    
    
    
        
        
    
    
       
           
       
    
                       

実装時に発生する問題は、との上記の計算がオーバーフロー（範囲 の結果を生成する）を引き起こす可能性があることです。オーバーフローが発生すると、乗算器に1ビットの余分なビットが必要になります。これは、次のことに注意することで回避できます。 ${\displaystyle (x_{1}+x_{0})}$${\displaystyle (y_{1}+y_{0})}$${\displaystyle z_{1}}$${\displaystyle B^{m}\leq {\text{result}}}2B^{m}}$

${\displaystyle z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.}$

とのこの計算により、の範囲の結果が生成されます。この方法では負の数が生成される可能性があり、その場合、符号をエンコードするために 1 ビット余分に必要となり、乗数にも 1 ビット余分に必要となります。ただし、これを回避する 1 つの方法は、符号を記録してから と の絶対値を使用して符号なしの乗算を実行することです。その後、両方の符号が元々異なっていた場合は結果が否定される可能性があります。もう 1 つの利点は、 が負であっても、 の最終的な計算には加算のみが含まれることです。 ${\displaystyle (x_{0}-x_{1})}$${\displaystyle (y_{1}-y_{0})}$${\displaystyle -B^{m}$${\displaystyle (x_{0}-x_{1})}$${\displaystyle (y_{1}-y_{0})}$${\displaystyle (x_{0}-x_{1})(y_{1}-y_{0})}$${\displaystyle z_{1}}$

• 多項式乗算のためのカラツバアルゴリズム
• Weisstein、Eric W.「Karatsuba 乗算」。MathWorld。
• Bernstein, DJ、「数学者のための多桁乗算」。Karatsuba およびその他の多くの乗算アルゴリズムについて説明します。