乗算アルゴリズム

乗算アルゴリズムは、2 つの数値を乗算するアルゴリズム(または方法)です。数値のサイズに応じて、他のアルゴリズムよりも効率的なアルゴリズムが異なります。多数のアルゴリズムが知られており、このトピックについては多くの研究が行われてきました。

最も古くて単純な方法は、古代から長乗算または小学校の乗算として知られており、最初の数のすべての桁を 2 番目の数のすべての桁で乗算し、その結果を加算するというものです。これにはの時間計算量があります。ここで、nは桁数です。手作業で行う場合、これはグリッド法乗算または格子乗算と言い換えることもできます。ソフトウェアでは、ビットシフトと加算の 2 つの操作のみが必要である ため、これは「シフトと加算」と呼ばれることがあります。${\displaystyle O(n^{2})}$

1960 年、アナトリー カラツバがカラツバ乗算を発見し、高速乗算アルゴリズムの研究が一気に進みました。この方法では、2 つの 2 桁の数字を乗算するのに、4 回ではなく 3 回の乗算を使用します (このバリエーションを使用して、複素数を高速に乗算することもできます) 。再帰的に実行すると、時間の計算量は になります。数を 3 つ以上の部分に分割すると、トゥーム クック乗算になります。たとえば、3 つの部分を使用すると、トゥーム 3アルゴリズムになります。多くの部分を使用すると、指数を 1 に任意に近づけることができますが、定数係数も大きくなるため、実用的ではありません。 ${\displaystyle O(n^{\log _{2}3})}$

1968年、係数上のフーリエ変換を利用するシェーンハーゲ・シュトラッセンアルゴリズムが発見されました。このアルゴリズムの時間計算量は です。2007年、Martin Fürer は複雑度 のアルゴリズムを提案しました。2014年、Harvey、Joris van der Hoeven、Lecerf は複雑度 のアルゴリズムを提案し、暗黙の定数を明示的にしました。これは 2018年に に改良されました。最後に、2019年、Harvey と van der Hoeven は複雑度 の銀河アルゴリズムを考案しました。これは、今日でも推測の域を出ませんが、これが最適な境界であろうというシェーンハーゲとシュトラッセンによる推測と一致しています。 ${\displaystyle O(n\log n\log \log n)}$${\displaystyle O(n\log n2^{\Theta (\log ^{*}n)})}$${\displaystyle O(n\log n2^{3\log ^{*}n})}$${\displaystyle O(n\log n2^{2\log ^{*}n})}$${\displaystyle O(n\log n)}$

整数乗算アルゴリズムは、クロネッカー置換法によって多項式を乗算するためにも使用できます。

位取り記数法が使用される場合、学校では、自然な掛け算の方法が長掛け算（小学校の掛け算とも呼ばれる）として教えられます。これは、被乗数を乗数の各桁で掛け算し、適切にシフトされた結果をすべて合計します。1桁の 掛け算表を暗記する必要があります。

これは、10 進法で大きな数を手作業で掛け算する場合の通常のアルゴリズムです。長い掛け算を紙の上で行う人は、すべての積を書き留めてからそれらを足し合わせます。そろばんを使用する人は、各積が計算されるとすぐに積を合計します。

この例では、長乗算を使用して23,958,233 (被乗数) を 5,830 (乗数) で乗算し、結果 (積) は 139,676,498,390 になります。

      23958233
× 5830
———————————————
      00000000 （ = 23,958,233 × 0）
     71874699 ( = 23,958,233 × 30)
   191665864 ( = 23,958,233 × 800)
+ 119791165 ( = 23,958,233 × 5,000)
———————————————
  139676498390 ( = 139,676,498,390)

ドイツなどの一部の国では、上記の乗算は同様に表されますが、元の積は水平に保たれ、乗数の最初の桁から計算が始まります。^[1]

23958233 · 5830
———————————————
   119791165
    191665864
      71874699
       00000000
———————————————
   139676498390

以下の擬似コードは、上記の乗算のプロセスを示しています。最終的に結果となる合計を維持するために 1 行だけを保持します。'+=' 演算子は、既存の値の合計を示し、コンパクトさのために操作を格納するために使用されることに注意してください (Java や C などの言語に似ています)。

multiply ( a [ 1 .. p ] , b [ 1 .. q ] , base ) // インデックス 1 の右端の数字を含むオペランド                              
  product = [ 1 .. p + q ] // 結果のためのスペースを割り当てる                                          
  b_i = 1 ～q // b のすべての数字に対して                                               
    キャリー= 0  
    for a_i = 1 to p // a内のすべての数字に対して                                             
      積[ a_i + b_i - 1 ] +=繰り上がり+ a [ a_i ] * b [ b_i ]          
      繰り上がり=積[ a_i + b_i - 1 ] /底        
      積[ a_i + b_i - 1 ] =積[ a_i + b_i - 1 ]を底とする法            
    積[ b_i + p ] =繰り上がり// 最後の桁は最後の繰り上がりから得られる                                   
  返品商品 

一部のチップでは、さまざまな整数および浮動小数点ワード サイズに対して、ハードウェアまたはマイクロコードで長乗算を実装しています。任意精度演算では、比較的小さな数を乗算するために、基数を 2 ^w（wはワード内のビット数）に設定した長乗算を使用するのが一般的です。この方法を使用してn桁の 2 つの数を乗算するには、約n ^{2 回の}演算が必要です。より正式には、長乗算を使用して 2 つのn桁の数を乗算するには、 Θ ( n ² ) 回の 1 桁の演算（加算と乗算） が必要です。

ソフトウェアで実装する場合、長い乗算アルゴリズムは加算中にオーバーフローを処理する必要があり、コストがかかる可能性があります。一般的な解決策は、数値を小さな基数bで表すことです。たとえば、8 b は表現可能なマシン整数です。これにより、オーバーフローが発生する前に複数の加算を実行できます。数値が大きくなりすぎた場合は、結果にその一部を加算するか、残りの部分を繰り上げてb未満の数値にマッピングします。このプロセスは正規化と呼ばれます。リチャード・ブレントは、このアプローチを Fortran パッケージ MP で使用しました。^[2]

コンピュータは当初、基数 2 の長倍算に非常によく似たアルゴリズムを使用していましたが、現代のプロセッサは、より効率的なアルゴリズムを使用して高速乗算用に回路を最適化しましたが、その代償としてハードウェアの実現がより複雑になりました。^{[引用が必要]}基数 2 の長倍算は、アルゴリズムが単純化され、左シフト (2 の累乗による乗算) と加算のみで構成されるため、 「シフト アンド アッド」と呼ばれることがあります。現在利用可能なほとんどのマイクロプロセッサは、ハードウェア乗算器またはマイクロコードで、さまざまな整数および浮動小数点サイズに対して、このアルゴリズムまたは他の同様のアルゴリズム (ブース エンコーディングなど) を実装しています。^{[引用が必要]}

現在利用可能なプロセッサでは、ビット単位のシフト命令は通常 (常にというわけではありませんが) 乗算命令よりも高速であり、2 の累乗による乗算 (左シフト) と除算 (右シフト) に使用できます。定数による乗算と定数による除算は、シフトと加算または減算のシーケンスを使用して実装できます。たとえば、ビット シフトと加算のみを使用して 10 を乗算する方法はいくつかあります。

 (( x  <<  2 )  +  x )  <<  1  # ここで 10*x は (x*2^2 + x)*2 として計算されます
 ( x  <<  3 )  +  ( x  <<  1 )  # ここで 10*x は x*2^3 + x*2 として計算されます

場合によっては、このようなシフトと加算または減算のシーケンスは、ハードウェア乗算器、特に除算器よりもパフォーマンスが優れています。またはの形式の数値による除算は、多くの場合、このような短いシーケンスに変換できます。 ${\displaystyle 2^{n}}$${\displaystyle 2^{n}\pm 1}$

標準的な長掛け算のほかに、手作業で掛け算を実行するために使用される他の方法がいくつかあります。このようなアルゴリズムは、特にコンピュータや掛け算表が利用できない場合に、速度、計算のしやすさ、または教育的価値のために考案される場合があります。

グリッド法（またはボックス法）は、小学校や初等学校の生徒によく教えられる多桁の掛け算の入門法である。1990年代後半からイングランドとウェールズの全国小学校数学カリキュラムの標準的な一部となっている。^[3]

両方の因数は、百の位、十の位、一の位に分割（「分割」）され、各位の積は比較的単純な乗算のみの段階で明示的に計算され、その後、別の加算段階でこれらの寄与が合計されて最終的な答えが得られます。

たとえば、34 × 13 の計算は、グリッドを使用して計算できます。

  300
   40
   90
 + 12
 ————
  442

続いて加算して 442 を得ます。これは、単一の合計 (右を参照) または行ごとの合計 (300 + 40) + (90 + 12) = 340 + 102 = 442 を作成することによって得られます。

この計算方法 (必ずしも明示的なグリッド配置を使用する必要はありませんが) は、部分積アルゴリズムとも呼ばれます。その本質は、単純な乗算を個別に計算し、すべての加算を最後の集約段階に残すことです。

グリッド法は、原理的にはどんな大きさの因数にも適用できますが、桁数が増えると部分積の数が扱いにくくなります。それでも、これは複数桁の乗算の概念を導入するのに便利な明示的な方法と見なされています。また、ほとんどの乗算計算が計算機やスプレッドシートを使用して行われる時代では、実際には一部の学生が必要とする唯一の乗算アルゴリズムになるかもしれません。

格子乗算、またはふるい乗算は、アルゴリズム的には長乗算と同等である。計算をガイドし、すべての乗算を加算から分離する格子（紙に描かれたグリッド）の準備が必要である。これは、1202年にフィボナッチの算盤でヨーロッパに紹介された。フィボナッチは、右手と左手を使って中間計算を行うという、精神的な操作であると説明した。マトラクチ・ナスフは、 16世紀の本「Umdet-ul Hisab」で、この方法の6つの異なるバリエーションを紹介した。これは、オスマン帝国中のエンデルン学校で広く使用された。 ^[4] ネイピアの骨、またはネイピアの棒も、ネイピアが亡くなった年である1617年に出版されたように、この方法を使用していた。

例に示されているように、被乗数と乗数は格子またはふるいの上と右側に書かれています。これは、2002 年に「フィボナッチの算盤の書」の著者であるシグラーが言及したレオナルドの資料の 1 つであるムハンマド イブン ムサ アル フワーリズミーの「算術」に見られます。 ^{[引用が必要]}

• 乗算フェーズでは、各行と列にラベルを付ける対応する数字の 2 桁の積で格子が埋められます。10 の位の数字は左上隅に配置されます。
• 加算フェーズでは、格子の対角線が合計されます。
• 最後に、繰り上がりフェーズが必要な場合は、格子の左側と下側に沿って示される答えは、長い加算または乗算のように 10 の位を繰り上げることによって通常の形式に変換されます。

右の図は、格子乗算を使用して 345 × 12 を計算する方法を示しています。より複雑な例として、23,958,233 に 5,830 (乗数) を掛けた計算を示す下の図を考えてみましょう。結果は 139,676,498,390 です。23,958,233 は格子の上部にあり、5,830 は右側にあることに注意してください。積は格子を埋め尽くし、それらの積の合計 (対角線上) は左側と下側にあります。次に、それらの合計を図のように合計します。

バイナリ方式は、農民に分類され、長い掛け算に必要な九九を暗記していない人々によって広く使用されてきたため、農民の掛け算としても知られています。 ^{[5] [検証失敗]}このアルゴリズムは古代エジプトで使用されていました。^[6]主な利点は、すぐに教えることができ、暗記する必要がなく、紙と鉛筆がない場合はポーカーチップなどのトークンを使用して実行できることです。欠点は、長い掛け算よりも手順が多いため、大きな数では扱いにくいことです。

紙に、余りを無視して乗数を繰り返し半分にしたときに得られる数字を 1 つの列に書き、その隣の列に被乗数を繰り返し 2 倍にしたときに得られる数字を書きます。最初の数字の最後の桁が偶数である各行を消し、2 番目の列の残りの数字を加算して積を求めます。

この例では、農民乗算を使用して 11 に 3 を掛けて、結果 33 を算出します。

10進数: 2進数:
11 3 1011 11
5 6 101 110
2    12        10   1100
1 24 1 11000
    —— ——————
    33 100001

手順を明示的に説明します。

• 11と3が上部に書かれています
• 11 は半分 (5.5) になり、3 は 2 倍 (6) になります。小数部分は切り捨てられます (5.5 は 5 になります)。
• 5 は半分 (2.5)、6 は 2 倍 (12) になります。小数部分は切り捨てられます (2.5 は 2 になります)。左の列の数字 (2) は偶数なので、右の列の数字 (12) は切り捨てられます。
• 2は半分（1）になり、12は2倍（24）になります。
• 削られていない値をすべて合計すると、3 + 6 + 24 = 33 になります。

この方法は、乗算が分配的であるため機能します。

${\displaystyle {\begin{aligned}3\times 11&=3\times (1\times 2^{0}+1\times 2^{1}+0\times 2^{2}+1\times 2^{3})\\&=3\times (1+2+8)\\&=3+6+24\\&=33.\end{aligned}}}$

先ほどの例の数字 (23,958,233 と 5,830) を使用した、より複雑な例:

10進数: 2進数:
5830   23958233        1011011000110   1011011011001001011011001
2915 47916466 101101100011 10110110110010010110110010
1457 95832932 10110110001 101101101100100101101100100
728   191665864        1011011000   1011011011001001011011001000 
364   383331728        101101100   10110110110010010110110010000 
182   766663456        10110110   101101101100100101101100100000
91 1533326912 1011011 1011011011001001011011001000000
45 3066653824 101101 10110110110010010110110010000000
22   6133307648        10110   101101101100100101101100100000000
11 12266615296 1011 1011011011001001011011001000000000
5 24533230592 101 10110110110010010110110010000000000
2   49066461184        10   101101101100100101101100100000000000 
1 98132922368 1   1011011011001001011011001000000000000
  ———————————— 1022143253354344244353353243222210110 （繰り上がり前）
  139676498390 10000010000101010111100011100111010110

この式は、場合によっては、掛け算の計算をより簡単にするために使用できます。

${\displaystyle {\frac {\left(x+y\right)^{2}}{4}}-{\frac {\left(xy\right)^{2}}{4}}={\frac {1}{4}}\left(\left(x^{2}+2xy+y^{2}\right)-\left(x^{2}-2xy+y^{2}\right)\right)={\frac {1}{4}}\left(4xy\right)=xy.}$

とが整数の 場合、${\displaystyle x}$${\displaystyle y}$

${\displaystyle (x+y)^{2}\equiv (xy)^{2}{\bmod {4}}}$

と は両方とも偶数か両方とも奇数である。 つまり${\displaystyle x+y}$${\displaystyle xy}$

${\displaystyle {\begin{aligned}xy&={\frac {1}{4}}(x+y)^{2}-{\frac {1}{4}}(xy)^{2}\\&=\left((x+y)^{2}{\text{ div }}4\right)-\left((xy)^{2}{\text{ div }}4\right)\end{aligned}}}$

次の例のように、平方数を 4 で割った整数部分を (事前に) 計算するだけで十分です。

以下は、 0 から 18 までの数字の余りを除いた 4 分の 1 平方の参照テーブルです。これにより、9×9までの数字の乗算が可能になります。

たとえば、9 に 3 を掛けると、合計と差はそれぞれ 12 と 6 になります。表で両方の値を調べると、36 と 9 となり、その差は 27 で、これは 9 と 3 の積です。

先史時代、四分の一平方の乗算には床関数が使われており、いくつかの資料^{[7] [8]ではこれを}バビロニア数学（紀元前2000-1600年） に起因するものとしている。

アントワーヌ・ヴォワザンは1817年に掛け算の補助として1から1000までの四分の一平方数表を出版した。1から100000までのより大きな四分の一平方数表は1856年にサミュエル・ローンディによって出版され、^[9] 1から200000までの四分の一平方数表は1888年にジョセフ・ブラターによって出版された。 ^[10]

1/4 乗算器は、アナログ コンピューターで2 つのアナログ入力信号の積であるアナログ信号を形成するために使用されました。このアプリケーションでは、オペアンプを使用して 2 つの入力電圧の和と差が形成されます。これらのそれぞれの 2 乗は、区分線形回路を使用して近似されます。最後に、2 つの 2 乗の差が形成され、さらに別のオペアンプを使用して 1/4 にスケーリングされます。

1980 年、エベレット L. ジョンソンはデジタル乗算器で 1/4 平方法を使用することを提案しました。^[11]たとえば、2 つの 8 ビット整数の積を求めるには、デジタル デバイスで和と差を求め、両方の量を平方表で検索し、結果の差を求め、2 ビット右にシフトして 4 で割ります。8 ビット整数の場合、1/4 平方表には 2 ⁹ −1=511 個のエントリ (可能な和の全範囲 0..510 に対して 1 つのエントリ、差には範囲 0..255 の最初の 256 個のエントリのみを使用)、または 2 ⁹ −1=511 個のエントリ (負の差には 2 の補数と 9 ビット マスキングの手法を使用し、差の符号のテストを回避) があり、各エントリは 16 ビット幅です (エントリの値は (0²/4)=0 から (510²/4)=65025 までです)。

1/4乗算器技術は、ハードウェア乗算器をサポートしていない8ビットシステムにメリットをもたらしました。チャールズ・パトニーはこ​​れを6502に実装しました。^[12]

コンピュータサイエンスにおける未解決の問題:

2 桁の数字の乗算を行う最も高速なアルゴリズムは何ですか?${\displaystyle n}$

(コンピュータサイエンスにおける未解決の問題)

理論計算機科学における研究分野は、2 つの ビット整数を乗算するために必要な 1 ビット算術演算の数に関するものです。これは、乗算の計算複雑度として知られています。手作業で行われる通常のアルゴリズムの漸近複雑度は ですが、1960 年にAnatoly Karatsuba は、より低い複雑度が可能であることを発見しました ( Karatsuba アルゴリズムを使用)。 ${\displaystyle n}$${\displaystyle O(n^{2})}$

現在、計算複雑度が最も低いアルゴリズムは、2019年のデイビッド・ハーヴェイとヨリス・ファン・デル・ホーヴェンによるアルゴリズムであり、シェーンハーゲ・シュトラッセンアルゴリズムで導入された数論的変換を使用して、演算のみを使用して整数を乗算する戦略を採用しています。^[13]これは可能な限り最高のアルゴリズムであると推測されていますが、の下限はわかっていません。 ${\displaystyle O(n\log n)}$${\displaystyle \Omega (n\log n)}$

Karatsuba 乗算は、再帰を使用してサブ計算を結合する O( n ^{log ₂ 3} ) ≈ O( n ^1.585 ) の分割統治アルゴリズムです。

式を書き直すことで、サブ計算/再帰が可能になります。再帰を実行することで、これを高速に解決できます。

とを の基数で - 桁の文字列として表す。未満の任意の正の整数に対して、与えられた 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回の掛け算を必要とし、チャールズ・バベッジにも知られていました。^[14]カラツバは、いくつかの追加の加算を犠牲にして、3回の掛け算だけで計算できることを観察しました。 と を前と同じように使用すると、 ${\displaystyle xy}$${\displaystyle z_{0}}$${\displaystyle z_{2}}$

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

再帰のオーバーヘッドのため、Karatsuba の乗算はnの値が小さい場合の長い乗算よりも遅くなります。そのため、一般的な実装では、 nの値が小さい場合、長い乗算に切り替えます。

拡張後のパターンを調べると、次のことがわかります。

${\displaystyle (x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})(z_{1}B^{m}+z_{0})(a_{1}B^{m}+a_{0})=}$
${\displaystyle a_{1}x_{1}y_{1}z_{1}B^{4m}+a_{1}x_{1}y_{1}z_{0}B^{3m}+a_{1 }x_{1}y_{0}z_{1}B^{3m}+a_{1}x_{0}y_{1}z_{1}B^{3m}}$
${\displaystyle +a_{0}x_{1}y_{1}z_{1}B^{3m}+a_{1}x_{1}y_{0}z_{0}B^{2m}+a_{1}x_{0}y_{1}z_{0}B^{2m}+a_{0}x_{1}y_{1}z_{0}B^{2m}+a_{0}x_{1}y_{1}z_{0}B^{2m}}$
${\displaystyle +a_{1}x_{0}y_{0}z_{1}B^{2m}+a_{0}x_{1}y_{0}z_{1}B^{2m}+a_{0}x_{0}y_{1}z_{1}B^{2m}+a_{1}x_{0}y_{0}z_{1}B^{2m}+a_{1}x_{0}y_{0}z_{0}B^{m}}$
${\displaystyle +a_{0}x_{1}y_{0}z_{0}B^{m}+a_{0}x_{0}y_{1}z_{0}B^{m}+a_{0}x_{0}y_{0}z_{1}B^{m}+a_{0}x_{0}y_{0}z_{1}B^{m}+a_{0}x_{0}y_{0}z_{0}}$

各加数は、0 から などの一意の 2 進数に関連付けられます。 さらに、この 2 進文字列では、B は 1 の数に累乗され、m で乗算されます。 ${\displaystyle 2^{N+1}-1}$${\displaystyle a_{1}x_{1}y_{1}z_{1}\longleftrightarrow 1111,\ a_{1}x_{0}y_{1}z_{0}\longleftrightarrow 1010}$

これをもっと簡潔に表現すると次のようになります。

${\displaystyle \prod _{j=1}^{N}(x_{j,1}B^{m}+x_{j,0})=\sum _{i=1}^{2^{N+1}-1}\prod _{j=1}^{N}x_{j,c(i,j)}B^{m\sum _{j=1}^{N}c(i,j)}=\sum _{j=0}^{N}z_{j}B^{jm}}$ここで、は数字iのj番目の位置の数字を意味します。${\displaystyle c(i,j)}$${\displaystyle c(i,j)\in \{0,1\}}$

${\displaystyle z_{0}=\prod _{j=1}^{N}x_{j,0}}$
${\displaystyle z_{N}=\prod _{j=1}^{N}x_{j,1}}$
${\displaystyle z_{N-1}=\prod _{j=1}^{N}(x_{j,0}+x_{j,1})-\sum _{i\neq N-1}^{N}z_{i}}$

カラツバのアルゴリズムは、長い乗算よりも漸近的に高速な乗算アルゴリズムとして初めて知られており、^[15]高速乗算の理論の出発点と見なすことができます。

乗算の別の方法は、トゥーム・クックまたはトゥーム 3 と呼ばれます。トゥーム・クック法では、乗算する各数値を複数の部分に分割します。トゥーム・クック法は、カラツバ法の一般化の 1 つです。3 方向トゥーム・クックは、サイズNの乗算 5 回分のコストでサイズ3N の乗算を実行できます。これにより、演算が 9/5 倍に高速化されますが、カラツバ法では 4/3 倍に高速化されます。

より多くの部分を使用すると、再帰乗算にかかる時間をさらに短縮できますが、加算と桁管理によるオーバーヘッドも大きくなります。このため、フーリエ変換法は、数千桁の数値の場合は通常より高速であり、さらに大きな数値の場合は漸近的に高速になります。

基数 B のすべての数は、多項式として表すことができます。

${\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}}$

さらに、2 つの数値の乗算は、2 つの多項式の積として考えることができます。

${\displaystyle XY=(\sum _{i=0}^{N}{x_{i}B^{i}})(\sum _{j=0}^{N}{y_{i}B^{j}})}$

なぜなら、:の場合、畳み込みが起こります。 ${\displaystyle B^{k}}$${\displaystyle c_{k}=\sum _{(i,j):i+j=k}{a_{i}b_{j}}=\sum _{i=0}^{k}{a_{i}b_{k-i}}}$

畳み込みルールを用いたFFT（高速フーリエ変換）を使用すると、

${\displaystyle {\hat {f}}(a*b)={\hat {f}}(\sum _{i=0}^{k}{a_{i}b_{k-i}})={\hat {f}}(a)}$●つまり、 ● 、ここで は フーリエ空間における対応する係数です。これは、fft(a * b) = fft(a) ● fft(b) と書くこともできます。 ${\displaystyle {\hat {f}}(b)}$${\displaystyle C_{k}=a_{k}}$${\displaystyle b_{k}}$${\displaystyle C_{k}}$

フーリエ変換による線形性により、同じ係数が得られ、これらの多項式は係数ごとに 1 つの固有の項のみで構成されるためです。

${\displaystyle {\hat {f}}(x^{n})=\left({\frac {i}{2\pi }}\right)^{n}\delta ^{(n)}}$ そして ${\displaystyle {\hat {f}}(a\,X(\xi )+b\,Y(\xi ))=a\,{\hat {X}}(\xi )+b\,{\hat {Y}}(\xi )}$

畳み込みルール: ●${\displaystyle {\hat {f}}(X*Y)=\ {\hat {f}}(X)}$${\displaystyle {\hat {f}}(Y)}$

FFT を通じて畳み込みの問題を積の問題に減らしました。

各 に対して、ifft (多項式補間) を求めることで、目的の係数が得られます。 ${\displaystyle c_{k}}$

アルゴリズムは分割統治戦略を使用して、問題をサブ問題に分割します。

時間計算量は O( n  log( n ) log(log( n ))) です。

このアルゴリズムは、1968年にシュトラッセンによって発明されました。1971年にシェーンハーゲとシュトラッセンによって実用化され、理論的な保証が提供され、シェーンハーゲ・シュトラッセンアルゴリズムが誕生しました。^[16]

2007 年、ペンシルベニア州立大学のスイス人数学者Martin Fürerは、複素数のフーリエ変換を使用して、整数乗算の漸近複雑度をn  log( n ) 2 ^{Θ( log * ( n ))に改善しました[17]} 。ここで、log ^{* は}反復対数を表します。Anindya De、Chandan Saha、Piyush Kurur、および Ramprasad Saptharishi は、 2008 年にモジュラー演算を使用した同様のアルゴリズムを提示し、同じ実行時間を達成しました^[18] 。 上記の資料の文脈で、これら後者の著者が達成したのは、Z / NZ が(2 m ) 乗根を持つように、N が2 ^{3 k} + 1よりはるかに小さいことです。これにより計算が高速化され、時間計算量が削減されます。ただし、これら後者のアルゴリズムは、非現実的なほど大きな入力に対してのみ Schönhage–Strassen より高速です。

2014 年、Harvey、Joris van der Hoeven、Lecerf ^[19]は、指数に含まれる暗黙の定数を明示的にすることで、実行時間 を達成する新しいアルゴリズムを提示しました。彼らはまた、 を達成するアルゴリズムの変種も提案しましたが、その妥当性はメルセンヌ素数の分布に関する標準的な予想に依存しています。2016 年、Covanov と Thomé は、フェルマー素数の一般化に基づく整数乗算アルゴリズムを提案しました。これは、推測的に の計算量上限を達成するものです。これは、2015 年の Harvey、van der Hoeven、Lecerf の条件付き結果と一致していますが、異なるアルゴリズムを使用し、異なる予想に依存しています。^{[20] 2018 年、Harvey と van der Hoeven は}、ミンコフスキーの定理によって保証された短い格子ベクトルの存在に基づくアプローチを使用して、の無条件計算量上限を証明しました。^[21]${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$${\displaystyle O(\log ^{*}n)}$${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$

2019年3月、デイヴィッド・ハーヴェイとヨリス・ファン・デル・ホーヴェンはO ( nlogn )乗算アルゴリズムの発見を発表しました。 ^[22]これは2021年にAnnals of Mathematicsに掲載されました。^[23]シェーンハーゲとシュトラッセンがnlog(n)が「可能な限り最良の」結果であると予測したため、ハーヴェイ は次のように述べています。「...私 たちの研究は、この問題の解決への道の終わりになると期待されていますが、これを厳密に証明する方法はまだわかっていません。」^[24]

単一プロセッサ上で2 つのnビット数を乗算する場合、 Ω ( n )という自明な下限値が存在する。対応するアルゴリズム (従来のマシン、つまりチューリング等価マシン上) や、より明確な下限値は知られていない。乗算は任意の素数pに対してAC ⁰ [ p ]の範囲外にあるため、積を計算できる AND、OR、NOT、MOD _pゲートを使用した定数深度、多項式 (または指数関数以下) サイズの回路族は存在しない。これは、MOD _qを定数深度で乗算に縮約することから導かれる。^{[25]乗算の下限値は、}分岐プログラムのいくつかのクラスでも知られている。^[26]

複雑な乗算には通常、4 つの乗算と 2 つの加算が含まれます。

${\displaystyle (a+bi)(c+di)=(ac-bd)+(bc+ad)i.}$

または

${\displaystyle {\begin{array}{c|c|c}\times &a&bi\\\hline c&ac&bci\\\hline di&adi&-bd\end{array}}}$

1963年にピーター・ウンガーが観察したように、本質的にはカラツバのアルゴリズムと同じ計算法を使って、乗算の回数を3回に減らすことができます。^[27]積( a  +  bi ) · ( c  +  di )は次のように計算できます。

k ₁ = c · ( a + b )

k ₂ = a · ( d − c )

k ₃ = b · ( c + d )

実部 = k ₁ − k ₃

虚数部 = k ₁ + k ₂。

このアルゴリズムでは、4 回ではなく 3 回の乗算と、2 回ではなく 5 回の加算または減算のみを使用します。手動で計算する場合のように、乗算が 3 回の加算または減算よりもコストがかかる場合は、速度が向上します。最新のコンピューターでは、乗算と加算にほぼ同じ時間がかかることがあるため、速度が向上しない可能性があります。浮動小数点を使用すると精度が多少低下する可能性があるというトレードオフがあります。

高速フーリエ変換（FFT）（または任意の線形変換）では、複素乗算は定数係数c  +  di（ FFTでは回転因子と呼ばれる）によって行われ、その場合、2つの加算（d − cとc + d）は事前に計算できます。したがって、必要な乗算は3つと加算は3つだけです。^{[28]しかし、このように乗算と加算をトレードオフすることは、現代の}浮動小数点ユニット ではもはや有利ではないかもしれません。^[29]

上記の乗算アルゴリズムはすべて多項式の乗算に拡張することもできます。あるいはクロネッカー置換法を使用して、多項式の乗算の問題を単一の2進乗算に変換することもできます。^[30]

長い乗算法を一般化して、代数式の乗算も可能にすることができます。

14ac - 3ab + 2 に ac - ab + 1 を掛ける

14ac -3ab 2
   ac-ab 1 アク-アブ 1
 ———————————————————
 14a 2 c 2   -3a 2 bc 2ac
        -14a 2 bc 3 a 2 b 2   -2ab
                 14ac -3ab 2
 ———————————————————————————————————————
 14a 2 c 2 -17a 2 bc 16ac 3a 2 b 2     -5ab +2
 ======================================= [31]

列ベースの乗算のさらなる例として、23 ロングトン (t)、12 ハンドレッドウェイト (cwt)、および 2 クォーター (qtr) を 47 で乗算する場合を考えます。この例では常用単位が使用されています。1 t = 20 cwt、1 cwt = 4 qtr です。

    t cwt 四半期
   23 12 2
               47倍
 ———————————————
  141 94 94
  940 470
   29 23
 ———————————————
 1110 587 94
 ———————————————
 1110 7 2
 ================= 答え: 1110 トン 7 cwt 2 qtr

まずクォーターに 47 を掛けます。結果の 94 が最初のワークスペースに書き込まれます。次に、cwt 12*47 = (2 + 10)*47 を掛けますが、部分的な結果 (94, 470) はまだ合計しません。同様に、23 に 47 を掛けると (141, 940) になります。クォーターの列を合計し、結果を 2 番目のワークスペースに配置します (この場合は簡単な操作です)。94 クォーターは 23 cwt と 2 qtr なので、2 を答えに入れて、23 を次の左の列に入れます。次に、cwt 列の 3 つのエントリを合計して 587 になります。これは 29 t 7 cwt なので、7 を答えに、29 を左の列に書き込みます。次に、トンの列を合計します。調整する必要はないので、結果はそのままコピーされます。

同じレイアウトと方法は、従来の計測単位や、古い英国の£sdシステムなどの非 10 進通貨にも使用できます。

• バイナリ乗算器
• ダダ乗数
• 除算アルゴリズム
• 多項式を評価するためのホーナースキーム
• 対数
• 行列乗算アルゴリズム
• 暗算
• 数論的変換
• プロスタファエレシス
• 計算尺
• トラクテンバーグシステム
• 剰余数システム § 乗算は別の高速乗算アルゴリズムであり、線形代数のように多くの演算が連続して実行される場合に特に効率的です。
• ウォレスツリー