乗算アルゴリズム

乗算アルゴリズムとは、2つの数を乗算するためのアルゴリズム（または方法）のことです。数の大きさによって、効率的なアルゴリズムは異なります。数多くのアルゴリズムが知られており、この分野については多くの研究が行われています。

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

1960年、アナトリー・カラツバはカラツバ乗算を発見し、高速乗算アルゴリズムの研究が爆発的に増加した。この方法は、2桁の2つの数を乗算するのに、4回の乗算ではなく3回の乗算を使用する。（この方法の変種は、複素数を高速に乗算するためにも使用できる。）再帰的に実行した場合、この方法の時間計算量はとなる。 $O(n^{\log _{2}3})$ 数を2つ以上の部分に分割すると、トゥーム・クック乗算になります。例えば、3つの部分を用いると、トゥーム3アルゴリズムになります。多くの部分を用いると指数を1に限りなく近づけることができますが、定数係数も大きくなるため、実用的ではありません。

1968年、法に関するフーリエ変換を利用するシェーンハーゲ・シュトラッセンアルゴリズムが発見された。その時間計算量はである。 $O(n\log n\log \log n)$ 2007年、マルティン・フューラーは、複雑度を持つアルゴリズムを提案した。 $O(n\log n2^{\Theta (\log ^{*}n)})$ 。 2014 年に、Harvey、Joris van der Hoeven、Lecerf は複雑な提案をしました。 $O(n\log n2^{3\log ^{*}n})$ これにより、暗黙の定数が明示的になりました。これは次のように改善されました。 $O(n\log n2^{2\log ^{*}n})$ 2018年に。最後に、2019年にハーベイとファン・デル・ホーフェンは複雑性を持つ銀河アルゴリズムを考案した。 $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 のすべての桁についてキャリー= 0a_i = 1から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 ] mod基数積[ b_i + p ] =キャリー// 最後の桁は最終キャリーから来ます返品商品

コンピュータでの使用

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

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

コンピュータは当初、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 として計算されます

場合によっては、このような一連のシフトと加算または減算は、ハードウェア乗算器、特に除算器よりも優れた性能を発揮します。 $2n$ または $2^n±1$ 多くの場合、このような短いシーケンスに変換できます。

手計算による乗算アルゴリズム

標準的な筆算による掛け算に加えて、手計算で掛け算を行うための方法は他にもいくつかあります。こうした計算方法は、特にコンピュータや九九表が利用できない場合に、計算速度、計算の容易さ、あるいは教育的価値を高めるために考案されることがあります。

グリッド法

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

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

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

 300 40 90 + 12 ———— 442

続いて、合計442を得るために加算します。これは、単一の合計（右図参照）で計算するか、行ごとの合計を計算することによって行います。

(300 + 40) + (90 + 12) = 340 + 102 = 442。

この計算手法（必ずしも明示的なグリッド配置を用いるとは限らない）は、部分積アルゴリズムとも呼ばれる。その本質は、単純な乗算を個別に計算し、すべての加算は最終的な集計段階で行うという点にある。

グリッド法は原理的にはあらゆる桁数の因数に適用できますが、桁数が増えるにつれて部分積の数が煩雑になります。それでも、多桁の乗算の概念を導入する上で有用かつ明確な方法とみなされており、ほとんどの乗算計算が電卓や表計算ソフトで行われる現代においては、一部の生徒にとって実際に必要な乗算アルゴリズムはこれだけで済むかもしれません。

格子乗算

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

例に示すように、被乗数と乗数は格子、つまり篩の上右側に記されます。これは、レオナルド・ダ・ヴィンチの典拠の一つとして、2002年に『フィボナッチの算盤の書』を著したシグラーが言及しているムハンマド・イブン・ムーサー・アル＝フワーリズミーの『算術』に見られます。

乗算の段階では、格子は各行と各列に対応する数字の2桁の積で埋められていきます。10の位の数字は左上隅に配置されます。
加算段階では、格子は対角線上で合計されます。
最後に、繰り上がりが必要な場合は、格子の左側と下側に示されている答えは、長足し算や長掛け算と同様に、十の位の数字を繰り上げることによって通常の形式に変換されます。

例

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

ロシアの農民の増殖

二進法は、農民乗算とも呼ばれています。これは、農民に分類される人々が広く使用しており、そのため長乗算に必要な九九を暗記していないためです。^{[ 5 ]}このアルゴリズムは古代エジプトで使用されていました。^[⁶^]主な利点は、すぐに教えることができ、暗記する必要がなく、紙と鉛筆がない場合はポーカーチップなどのトークンを使用して実行できることです。欠点は、長乗算よりも手順が多いため、大きな数では扱いにくいことです。

説明

一方の列には、乗数を繰り返し半分にし、余りを無視した結果の数値が入っています。その隣の列には、被乗数を繰り返し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。

この方法は、乗算が分配法則を満たすため有効です。

{\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

四分の一平方乗算

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

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

の場合 $x$ そして $y$ は整数なので、

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

なぜなら $x+y$ そして $xy$ 両方とも偶数か両方とも奇数です。これはつまり、

{\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までの数字について、余りを捨てた四分位数のルックアップテーブルです。これにより、 $9\times9$ までの数の乗算が可能になります。

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

四分の一平方乗算の歴史

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

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

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

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

1/4 平方乗算器技術は、ハードウェア乗算器をサポートしていない 8 ビットシステムにとって有益である。Charles Putney はこれを6502に実装した。^{[ 12 ]}

乗算の計算複雑性

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

2つの数値の乗算を行う最速のアルゴリズムは何ですか？

n

桁数？

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

理論計算機科学における研究分野の一つに、2つの数値を乗算するために必要な1ビット演算の回数に関するものがある。 $n$ ビット整数。これは乗算の計算複雑度として知られています。手作業で行われる通常のアルゴリズムの漸近的な複雑度は $O(n^{2})$ しかし、1960年にアナトリー・カラツバは、より複雑なアルゴリズムが可能であることを発見した（カラツバアルゴリズムを使用）。^{[ 13 ]}

現在、最も計算複雑度が低いアルゴリズムは、2019年にDavid HarveyとJoris van der Hoevenによって開発されたアルゴリズムで、 Schönhage–Strassenアルゴリズムで導入された数論的変換を利用して整数を乗算する戦略を採用している。 $O(n\log n)$ 操作。^{[ 14 ]}これは可能な限り最良のアルゴリズムであると推測されていますが、下限は $\Omega (n\log n)$ 不明である。

唐つば乗算

カラツバ乗算は、O( n ^{log ₂ 3} ) ≈ O( n ^1.585 ) の分割統治アルゴリズムであり、再帰を使用して部分計算をマージします。

数式を書き換えることで、部分計算や再帰処理が可能になります。再帰処理を用いることで、この問題を高速に解決できます。

させて $x$ そして $y$ として表現される $n$ 何らかの基数における数字列 $B$ 任意の正の整数に対して $m$ 未満 $n$ 与えられた2つの数値は次のように書くことができる。

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

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

どこ $x_{0}$ そして $\displaystyle y_0}}$ より小さい $B^{m}$ 製品はその後

${\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}}$

どこ

z_{2}=x_{1}y_{1},

z_{1}=x_{1}y_{0}+x_{0}y_{1},

z_{0}=x_{0}y_{0}.

これらの公式は4回の乗算を必要とし、チャールズ・バベッジに知られていた。^{[ 15 ]}カラツバは、 $xy$ わずか3回の乗算で計算できますが、いくつかの追加加算が必要になります。 $z_{0}$ そして $\displaystyle z_2}}$ 以前と同様に、

{\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}}

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

N個の数を掛け合わせる一般的なケース

拡張後のパターンを分析すると、以下のことがわかる。

${\begin{alignedat}{5}(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})(z_{1}B^{m}+z_{0})(a_{1}B^{m}+a_{0})&=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}\\&+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_{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_{0}B^{m{\phantom {1}}}\\&+a_{0}x_{1}y_{0}z_{0}B^{m{\phantom {1}}}&+a_{0}x_{0}y_{1}z_{0}B^{m{\phantom {1}}}&+a_{0}x_{0}y_{0}z_{1}B^{m{\phantom {1}}}&+a_{0}x_{0}y_{0}z_{0}{\phantom {B^{1m}}}\end{alignedat}}$

各項は、0から10までの一意のバイナリ数に関連付けられています。 $2N+1-1$ 、例えば $a_{1}x_{1}y_{1}z_{1}\longleftrightarrow 1111,\ a_{1}x_{0}y_{1}z_{0}\longleftrightarrow 1010$ など。さらに、このバイナリ文字列では、B は 1 のべき乗であり、m を乗算します。

これをより少ない言葉で表現すると、次のようになります。

$\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}$ 、どこ $c(i,j)$ は、数字 i の j 番目の位置にある数字を意味します。 $c(i,j)\in \{0,1\}$

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

歴史

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

トゥーム・クック

乗算のもう一つの方法は、トゥーム・クック法またはトゥーム3法と呼ばれます。トゥーム・クック法では、乗算する各数を複数の部分に分割します。トゥーム・クック法は、カラツバ法の一般化の一つです。3ウェイのトゥーム・クック法では、 5回のN倍の乗算のコストで3N倍の乗算を実行できます。これにより、演算速度が9/5倍になりますが、カラツバ法では4/3倍にしかならないのです。

使用する部品数を増やすことで再帰的な乗算にかかる時間をさらに短縮できますが、加算や桁管理に伴うオーバーヘッドも増加します。そのため、フーリエ変換法は数千桁の数に対しては一般的に高速であり、さらに大きな数に対しても漸近的に高速になります。

シェーンハーゲ通り

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

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

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

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

の係数は $B^{k}$ 製品には $z_{k}=\sum _{(i,j):i+j=k}{x_{i}y_{j}}=\sum _{i=0}^{k}{x_{i}y_{k-i}},$ 畳み込み演算があり、高速フーリエ変換（FFT）を使用できます。 ${\hat {f}}(XY)={\hat {f}}(\sum _{i=0}^{k}{x_{i}y_{k-i}})={\hat {f}}(X)\cdot {\hat {f}}(Y).$

したがって、乗算はFFTに還元される。 $N$ 乗算と逆FFT。結果として、時間計算量は $O (n log(n) log(log n))$ となり。

歴史

このアルゴリズムは、 1968 年にStrassenによって考案されました。1971 年に Schönhageと Strassenによって実用化され、理論的な保証が提供され、Schönhage–Strassen アルゴリズムが誕生しました。^{[ 17 ]}

さらなる改善

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

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

2019 年 3 月、David HarveyとJoris van der Hoeven はO ( n log n )乗算アルゴリズムの発見を発表しました。 ^{[ 23 ]}これは2021 年にAnnals of Mathematicsに掲載されました。^{[ 14 ]} Schönhage と Strassen はn log( n ) が「最良の」結果であると予測していたため、Harvey は「... 私たちの研究はこの問題の終着点となることが期待されますが、これを厳密に証明する方法はまだわかりません」と述べています。^{[ 24 ]しかし、この新しいアルゴリズムは非常に非実用的です。桁数が}^[¹⁴^]を超える場合にのみ Schönhage–Strassen アルゴリズムよりも高速になります。

{\begin{aligned}2^{{1729}^{12}}&=2^{713\,739\,807\,325\,663\,489\,766\,475\,852\,620\,783\,120\,641}\\&\approx 4.145331\times 10^{214\,857\,091\,104\,455\,254\,035\,802\,532\,723\,729\,912\,717}\\&\approx 10^{2.148571\times 10^{38}}.\end{aligned}}

下限値

単一プロセッサ上で 2 つのnビット数を乗算する場合、 Ω ( n )には自明な下限値が存在する。従来のマシン、つまりチューリング等価マシン上では、対応するアルゴリズムも、より厳密な下限値も知られていない。ハートマニス・スターンズ予想によれば、 $O(n)$ 達成できません。乗算は任意の素数pに対してAC ⁰ [ p ]の範囲外にあるため、AND、OR、NOT、MOD _pゲートを使用して積を計算できる定数深さ、多項式 (または準指数) サイズ回路のファミリーは存在しません。これは、MOD _qの定数深さの乗算への還元から導かれます。^[²⁵^]分岐プログラムのいくつかのクラスについては、乗算の下限も知られています。^[²⁶^]

複素数の乗算

複雑な乗算は通常、4回の乗算と2回の加算から成ります。

(a+bi)(c+di)=(ac-bd)+(bc+ad)i.

または

{\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 ではツイドル係数と呼ばれる) で行われ、この場合、加算 ( d − cとc + d ) のうち 2 つを事前に計算できます。したがって、必要な乗算は 3 回、加算は 3 回だけです。^[²⁸^] ただし、このように乗算を加算と交換することは、現代の浮動小数点演算ユニットではもはや有益ではない可能性があります。^[²⁹^]

多項式の乗算

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

長乗算法は、代数式の乗算を可能にするように一般化することができる。

14ac - 3ab + 2 に ac - ab + 1 を掛けたもの

14ac -3ab 2 ac -ab 1 ———————————————————— 14a ² c ² -3a ² bc 2ac -14a ² bc 3 a ² b ² -2ab 14ac -3ab 2 ——————————————————————————————————————— 14a ² c ² -17a ² bc 16ac 3a ² b ² -5ab +2 ======================================== ^{[ 31 ]}

縦書き乗算のさらなる例として、23ロングトン（t）、12ハンドレッドウェイト（cwt）、2クォーター（qtr）に47を掛けることを考えてみましょう。この例では、アボワールデュポワ単位を使用しています。1 t = 20 cwt、1 cwt = 4 qtr。

 t cwt qtr 23 12 2 47 × ———————————————— 1. 全てに47を掛ける 1081 564 94 ———————————————— 2a. 4分の1を繰り上げて、100ポンドに加算します（94 = 23 × 4 + 2） (564) 94 23 2 ————— 587 2 2b. cwt を繰り上げて t に加える (587 = 29 × 20 + 7) (1081) 587 2 29 7 ———————————————— 3. 最終追加 1110 7 2 ================= 回答: 1110 トン 7 cwt 2 qtr

同じレイアウトと方法は、従来のあらゆる測定単位や、旧英国ポンド・ドル制度のような非十進法通貨にも適用できます。

参考文献

↑ 「乗算」。www.mathematische -basteleien.de 。 2022年3月15日取得。
↑ Brent, Richard P (1978 年 3 月). "A Fortran Multiple-Precision Arithmetic Package". ACM Transactions on Mathematical Software . 4 : 57–70 . CiteSeerX 10.1.1.117.8425 . doi : 10.1145/355769.355775 . S2CID 8875817 .
↑イーソン、ゲイリー (2000-02-13). 「親たちの学校再開」 . BBCニュース.イーストアウェイ、ロブ（2010年9月10日）。「なぜ現代の親は数学ができないのか」。BBCニュース。
↑ Corlu, MS; Burlbaw, LM; Capraro, RM; Corlu, MA; Han, S. (2010). "オスマン帝国宮廷学校エンデルンと多才な男、マトラクチ・ナスフ" .韓国数学教育学会誌シリーズD：数学教育研究. 14 (1): 19– 31.
↑ボゴモルニー、アレクサンダー。「農民の増殖」。www.cut - the-knot.org。 2017年11月4日取得。
↑ウェルズ、D.（1987）。『ペンギン版奇妙な数字辞典』ペンギンブックス。44ページ。ISBN 978-0-14-008029-2。
↑マクファーランド、デイビッド（2007）、『クォーターテーブル再考：初期のテーブル、テーブル構築における分業、およびアナログコンピュータにおける後期の実装』、p. 1
↑ロブソン、エレノア（2008）。『古代イラクの数学：社会史』プリンストン大学出版局、227ページ。ISBN 978-0691201405。
↑ 「書評」、土木技師および建築家ジャーナル：54-55、1857年。
↑ Holmes, Neville (2003), "四分の一平方数による乗算", The Mathematical Gazette , 87 (509): 296– 299, doi : 10.1017/S0025557200172778 , JSTOR 3621048 , S2CID 125040256 .
↑ Everett L., Johnson (1980年3月)、「デジタル四分の一平方乗算器」、IEEE Transactions on Computers、vol. C-29、no. 3、ワシントンDC、米国：IEEE Computer Society、pp. 258–261、doi：10.1109/TC.1980.1675558、ISSN 0018-9340、S2CID 24813486
↑ Putney, Charles (1986年3月) 「史上最速の6502乗算」 Apple Assembly Line 6 ( 6).
↑ 「コンピューターが大きな数を掛け合わせる天才的な方法」。YouTube 。 2025年1月2日。
1 2 3ハーベイ、デイビッド。ファン・デル・ホーフェン、ジョリス（2021）。「時間内の整数乗算」 $O(n\log n)$ " (PDF) . Annals of Mathematics . Second Series. 193 (2): 563– 617. doi : 10.4007/annals.2021.193.2.4 . MR 4224716 . S2CID 109934776 .
↑チャールズ・バベッジ、『第 VIII 章 – 解析機関について、より大きな数の扱い、哲学者の生涯からの抜粋』、ロングマン・グリーン、ロンドン、1864 年、125 ページ。
↑ D. クヌース著『コンピュータプログラミングの技法』第2巻、第4.3.3節（1998年）
↑シェーンハーゲ、A.;ストラッセン、V. (1971)。「シュネル・マルチプリケーション・グローサー・ザーレン」。コンピューティング。7 ( 3–4 ): 281–292 .土井: 10.1007/BF02242355。S2CID 9738629。
↑ Fürer, M. (2007). "Faster Integer Multiplication" (PDF) . Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA . pp. 57–66 . doi : 10.1145/1250790.1250800 . ISBN 978-1-59593-631-8. S2CID 8437794 .
↑ De, A.; Saha, C.; Kurur, P.; Saptharishi, R. (2008). "モジュラー算術を用いた高速整数乗算".第40回ACM理論計算機科学シンポジウム（STOC）論文集. pp. 499–506 . arXiv : 0801.1416 . doi : 10.1145/1374376.1374447 . ISBN 978-1-60558-047-0. S2CID 3264828 .
↑ハーヴェイ、デヴィッド;ファン・デル・ホーフェン、ジョリス。ルセルフ、グレゴワール (2016)。「整数乗算がさらに高速化」。複雑さのジャーナル。36 : 1–30.arXiv : 1407.3360 。土井：10.1016/j.jco.2016.03.001。MR 3530637。
↑ Covanov, Svyatoslav; Thomé, Emmanuel (2019). "一般化フェルマー素数を用いた高速整数乗算". Math. Comp. 88 (317): 1449– 1477. arXiv : 1502.02800 . doi : 10.1090/mcom/3367 . S2CID 67790860 .
↑ Harvey, D.; van der Hoeven, J. (2019). "短い格子ベクトルを使用した高速整数乗算". The Open Book Series . 2 : 293– 310. arXiv : 1802.07932 . doi : 10.2140/obs.2019.2.293 . S2CID 3464567 .
↑ハートネット、ケビン (2019-04-11). 「数学者たちが完璧な掛け算の方法を発見」 .クアンタマガジン. 2019-05-03閲覧.
↑ギルバート、ラクラン (2019-04-04). 「数学の天才が48年前の掛け算の問題を解決」 . UNSW . 2019-04-18に取得。
↑ Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach . Cambridge University Press. ISBN 978-0-521-42426-4。
↑ Ablayev, F.; Karpinski, M. (2003). "ランダム化された順序付き読み取り1回分岐プログラムにおける整数乗算の下限" (PDF) . Information and Computation . 186 (1): 78– 89. doi : 10.1016/S0890-5401(03)00118-4 .
↑クヌース、ドナルド・E. (1988)、『コンピュータプログラミングの技法第2巻：半数値アルゴリズム』、アディソン・ウェスリー、 519、706ページ
↑ Duhamel, P.; Vetterli, M. (1990). "高速フーリエ変換: チュートリアルレビューと現状" (PDF) . Signal Processing . 19 (4): 259–299 セクション 4.1 を参照。Bibcode : 1990SigPr..19..259D . doi : 10.1016/0165-1684(90)90158-U .
↑ Johnson, SG; Frigo, M. (2007). "算術演算が少ない修正スプリット基数FFT" (PDF) . IEEE Trans. Signal Process . 55 (1): 111–9 セクション IV を参照。Bibcode : 2007ITSP...55..111J . doi : 10.1109/TSP.2006.882087 . S2CID 14772428 .
↑フォン・ツア・ガテン、ヨアヒム;ゲルハルト、ユルゲン (1999)、『Modern Computer Algebra』、ケンブリッジ大学出版局、243 ～ 244 ページ、ISBN 978-0-521-64176-0。
↑キャッスル、フランク (1900)。ワークショップ数学。ロンドン：マクミラン社、74ページ。

さらに読む

ウォーレン・ジュニア、ヘンリー・S. (2013).ハッカーズ・ディライト（第2 版）.アディソン・ウェスリー-ピアソン・エデュケーション社. ISBN 978-0-321-84268-8。
Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques" . quadibloc . 2018-07-03 のオリジナルからアーカイブ済み. 2018-07-16に取得.
ヨハンソン、ケニー（2008）。低消費電力・低複雑度シフト加算ベース計算（PDF）（博士論文）。リンシェーピング科学技術研究（第1版）。スウェーデン、リンシェーピング：リンシェーピング大学電気工学科。ISBN 978-91-7393-836-5ISSN 0345-7524。No . 1201。 2017年8月13日のオリジナルからアーカイブ（PDF）。 2021年8月23日取得。（x+268ページ）

外部リンク

基本的な算術

UCSMPの「日常数学」における算数の多様な方法
古代数学に関するパワーポイントプレゼンテーション
格子乗算のフラッシュビデオ

高度なアルゴリズム

GMPで使用される乗算アルゴリズム

[1] 「乗算」。www.mathematische -basteleien.de 。 2022年3月15日取得。

[2] Brent, Richard P (1978 年 3 月). "A Fortran Multiple-Precision Arithmetic Package". ACM Transactions on Mathematical Software . 4 : 57–70 . CiteSeerX 10.1.1.117.8425 . doi : 10.1145/355769.355775 . S2CID 8875817 .

[3] イーソン、ゲイリー (2000-02-13). 「親たちの学校再開」 . BBCニュース.イーストアウェイ、ロブ（2010年9月10日）。「なぜ現代の親は数学ができないのか」。BBCニュース。

[4] Corlu, MS; Burlbaw, LM; Capraro, RM; Corlu, MA; Han, S. (2010). "オスマン帝国宮廷学校エンデルンと多才な男、マトラクチ・ナスフ" .韓国数学教育学会誌シリーズD：数学教育研究. 14 (1): 19– 31.

[5] ボゴモルニー、アレクサンダー。「農民の増殖」。www.cut - the-knot.org。 2017年11月4日取得。

[6] ウェルズ、D.（1987）。『ペンギン版奇妙な数字辞典』ペンギンブックス。44ページ。ISBN 978-0-14-008029-2。

[7] マクファーランド、デイビッド（2007）、『クォーターテーブル再考：初期のテーブル、テーブル構築における分業、およびアナログコンピュータにおける後期の実装』、p. 1

[8] ロブソン、エレノア（2008）。『古代イラクの数学：社会史』プリンストン大学出版局、227ページ。ISBN 978-0691201405。

[9] 「書評」、土木技師および建築家ジャーナル：54-55、1857年。

[10] Holmes, Neville (2003), "四分の一平方数による乗算", The Mathematical Gazette , 87 (509): 296– 299, doi : 10.1017/S0025557200172778 , JSTOR 3621048 , S2CID 125040256 .

[eljohnson-11] Everett L., Johnson (1980年3月)、「デジタル四分の一平方乗算器」、IEEE Transactions on Computers、vol. C-29、no. 3、ワシントンDC、米国：IEEE Computer Society、pp. 258–261、doi：10.1109/TC.1980.1675558、ISSN 0018-9340、S2CID 24813486

[cputney-12] Putney, Charles (1986年3月) 「史上最速の6502乗算」 Apple Assembly Line 6 ( 6).

[13] 「コンピューターが大きな数を掛け合わせる天才的な方法」。YouTube 。 2025年1月2日。

[Harvey-vdHoeven-14] 1 2 3ハーベイ、デイビッド。ファン・デル・ホーフェン、ジョリス（2021）。「時間内の整数乗算」 $O(n\log n)$ " (PDF) . Annals of Mathematics . Second Series. 193 (2): 563– 617. doi : 10.4007/annals.2021.193.2.4 . MR 4224716 . S2CID 109934776 .

[15] チャールズ・バベッジ、『第 VIII 章 – 解析機関について、より大きな数の扱い、哲学者の生涯からの抜粋』、ロングマン・グリーン、ロンドン、1864 年、125 ページ。

[16] D. クヌース著『コンピュータプログラミングの技法』第2巻、第4.3.3節（1998年）

[schönhage-17] シェーンハーゲ、A.;ストラッセン、V. (1971)。「シュネル・マルチプリケーション・グローサー・ザーレン」。コンピューティング。7 ( 3–4 ): 281–292 .土井: 10.1007/BF02242355。S2CID 9738629。

[fürer_1-18] Fürer, M. (2007). "Faster Integer Multiplication" (PDF) . Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA . pp. 57–66 . doi : 10.1145/1250790.1250800 . ISBN 978-1-59593-631-8. S2CID 8437794 .

[19] De, A.; Saha, C.; Kurur, P.; Saptharishi, R. (2008). "モジュラー算術を用いた高速整数乗算".第40回ACM理論計算機科学シンポジウム（STOC）論文集. pp. 499–506 . arXiv : 0801.1416 . doi : 10.1145/1374376.1374447 . ISBN 978-1-60558-047-0. S2CID 3264828 .

[20] ハーヴェイ、デヴィッド;ファン・デル・ホーフェン、ジョリス。ルセルフ、グレゴワール (2016)。「整数乗算がさらに高速化」。複雑さのジャーナル。36 : 1–30.arXiv : 1407.3360 。土井：10.1016/j.jco.2016.03.001。MR 3530637。

[21] Covanov, Svyatoslav; Thomé, Emmanuel (2019). "一般化フェルマー素数を用いた高速整数乗算". Math. Comp. 88 (317): 1449– 1477. arXiv : 1502.02800 . doi : 10.1090/mcom/3367 . S2CID 67790860 .

[22] Harvey, D.; van der Hoeven, J. (2019). "短い格子ベクトルを使用した高速整数乗算". The Open Book Series . 2 : 293– 310. arXiv : 1802.07932 . doi : 10.2140/obs.2019.2.293 . S2CID 3464567 .

[23] ハートネット、ケビン (2019-04-11). 「数学者たちが完璧な掛け算の方法を発見」 .クアンタマガジン. 2019-05-03閲覧.

[24] ギルバート、ラクラン (2019-04-04). 「数学の天才が48年前の掛け算の問題を解決」 . UNSW . 2019-04-18に取得。

[25] Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach . Cambridge University Press. ISBN 978-0-521-42426-4。

[26] Ablayev, F.; Karpinski, M. (2003). "ランダム化された順序付き読み取り1回分岐プログラムにおける整数乗算の下限" (PDF) . Information and Computation . 186 (1): 78– 89. doi : 10.1016/S0890-5401(03)00118-4 .

[taocp-vol2-sec464-ex41-27] クヌース、ドナルド・E. (1988)、『コンピュータプログラミングの技法第2巻：半数値アルゴリズム』、アディソン・ウェスリー、 519、706ページ

[28] Duhamel, P.; Vetterli, M. (1990). "高速フーリエ変換: チュートリアルレビューと現状" (PDF) . Signal Processing . 19 (4): 259–299 セクション 4.1 を参照。Bibcode : 1990SigPr..19..259D . doi : 10.1016/0165-1684(90)90158-U .

[29] Johnson, SG; Frigo, M. (2007). "算術演算が少ない修正スプリット基数FFT" (PDF) . IEEE Trans. Signal Process . 55 (1): 111–9 セクション IV を参照。Bibcode : 2007ITSP...55..111J . doi : 10.1109/TSP.2006.882087 . S2CID 14772428 .

[30] フォン・ツア・ガテン、ヨアヒム;ゲルハルト、ユルゲン (1999)、『Modern Computer Algebra』、ケンブリッジ大学出版局、243 ～ 244 ページ、ISBN 978-0-521-64176-0。

[31] キャッスル、フランク (1900)。ワークショップ数学。ロンドン：マクミラン社、74ページ。

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]。

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]。

[ 19 ]

[ 20 ]

[ 21 ]

22

[ 23 ]

[ 24 ]しかし、この新しいアルゴリズムは非常に非実用的です。桁数が

[

[

[ 27 ]

[

[

[ 30 ]

[ 31 ]