ブースの乗算アルゴリズム

ブースの乗算アルゴリズムは、 2 の補数表記の 2 つの符号付きバイナリ数を乗算する乗算アルゴリズムです。このアルゴリズムは、1950 年にアンドリュー ドナルド ブースがロンドンのブルームズベリーにあるバークベック カレッジで結晶学の研究をしていたときに考案されました。^{[ 1 ]}ブースのアルゴリズムは、コンピュータ アーキテクチャの研究において興味深いものです。

ブースのアルゴリズムは、符号付き2の補数表現のNビット乗数Yの隣接するビットペアを調べます。これには、最下位ビットの下にある暗黙のビット、y ₋₁ = 0が含まれます。iが0からN − 1までの各ビットy _iについて、ビットy _iとy _{i −1}が考慮されます。これら2つのビットが等しい場合、積アキュムレータPは変更されません。y i = 0かつy i −1 = 1の場合、被乗数 に_{2 i}を掛けたもの^が_Pに加算されます。また、y _i = 1かつy _i−1 = 0の場合、被乗数に2 ⁱを掛けたものがPから減算されます。Pの最終値は符号付き積です。

被乗数と積の表現は指定されていません。通常、これらは乗数と同様に2の補数表現ですが、加算と減算をサポートする任意の数体系でも同様に機能します。ここで述べたように、ステップの順序は決定されていません。通常、i = 0から始めて、LSBからMSBに進みます。次に、2 ⁱによる乗算は、ステップ間でPアキュムレータを右に増分シフトすることによって置き換えられます。下位ビットはシフトアウトでき、その後の加算と減算はPの最上位Nビットのみで実行できます。^{[ 2 ]}これらの詳細には多くのバリエーションと最適化があります。

このアルゴリズムは、乗数内の1の連続列を、列の両端で上位の+1と下位の-1に変換するものとして説明されることが多い。列が最上位ビット（MSB）を通過する場合、上位の+1は存在しないため、結果として適切な値の負の値として解釈される。

ブースのアルゴリズムは、あらかじめ決められた 2 つの値AとSのいずれかを積Pに(通常の符号なしバイナリ加算で) 繰り返し加算し、次にPに対して右方向の算術シフトを実行することによって実装できます。m と r をそれぞれ被乗数と乗数とし、 xとyをmとrのビット数とします。

1. AとSの値、およびPの初期値を決定してください。これらの数値はすべて( x  + y + 1)の長さを持つ必要があります。    
   1. A: 最上位（左端）ビットをmの値で埋めます。残りの（y  +  1）ビットをゼロで埋めます。
   2. S: 最上位ビットを2の補数表記で( −m )の値で埋めます。残りの( y  +  1)ビットをゼロで埋めます。
   3. P: 最上位のxビットをゼロで埋めます。その右側にrの値を付加します。最下位（最も右側）のビットをゼロで埋めます。
2. Pの最下位 2 ビット (右端のビット) を決定します。
   1. それらが01の場合は、 P  + Aの値を求めます。オーバーフローは無視してください。 
   2. それらが10の場合、 P  + Sの値を求めなさい。オーバーフローは無視してください。 
   3. 値が00の場合は、何もせず、次のステップでPを直接使用する。
   4. 値が11の場合は、何もせず、次のステップでPを直接使用してください。
3. 2番目の手順で得られた値を算術的に右に1桁シフトします。Pをこの新しい値とします。
4. 手順2と3をy回繰り返す。
5. Pから最下位ビット (右端のビット) を削除します。これはmとrの積です。

m = 3、r = − 4、x = 4、y = 4の場合、3 × ( − 4 )を求めなさい。

• m = 0011、-m = 1101、r = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• ループを4回実行します。
  1. P = 0000 110 0 0。最後の2ビットは00です。
     • P = 0000 0110 0。算術右シフト。
  2. P = 0000 011 0 0。最後の2ビットは00です。
     • P = 0000 0011 0。算術右シフト。
  3. P = 0000 001 1 0。最後の2ビットは10です。
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. 算術右シフト。
  4. P = 1110 100 1 1。最後の 2 ビットは 11 です。
     • P = 1111 0100 1. 算術右シフト。
• 積は1111 0100で、これは-12です。

上記の手法は、被乗数が表現可能な最大の負の数である場合（例えば、被乗数が 4 ビットの場合、この値は− 8 になります）には不十分です。これは、S を設定するために必要な被乗数の否定である -m を計算する際にオーバーフローが発生するためです。この問題を解決する 1 つの方法は、A、S、P をそれぞれ 1 ビットずつ拡張することです。ただし、これらの数値は依然として同じです。つまり、以前は− 8 が 1000 の 4 ビットで表現されていましたが、現在は 1000 の 5 ビットで表現されます。これは、上記の実装に従いますが、A と S のビットの決定方法が変更されます。例えば、元々 A の最初のxビットに割り当てられていたmの値は、 x + 1 ビットに拡張され、A の最初のx + 1 ビットに割り当てられます。以下では、被乗数と乗数に 4 ビットを使用して− 8 に 2を乗算することで、改良された手法を示します。

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0
• ループを4回実行します。
  1. P = 0 0000 001 0 0。最後の 2 ビットは 00 です。
     • P = 0 0000 0001 0。右シフト。
  2. P = 0 0000 000 1 0。最後の 2 ビットは 10 です。
     • P = 0 1000 0001 0。P = P + S。
     • P = 0 0100 0000 1. 右シフト。
  3. P = 0 0100 000 0 1。最後の 2 ビットは 01 です。
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0。右シフト。
  4. P = 1 1110 000 0 0。最後の 2 ビットは 00 です。
     • P = 1 1111 0000 0。右シフト。
• 積は11110000（最初と最後のビットを破棄した後）で、これは-16です。

0に囲まれた1のブロックからなる正の乗数を考えてみましょう。例えば、00111110です。その積は次のようになります。 $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&1&1&0\\\hline \end{array}}=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}$$ ここで、Mは被乗数である。同じ式を書き換えることで、演算回数を2回に減らすことができる。 $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&0&0&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{1})=M\times 62.}$$

実際、バイナリ数における任意の1の並びは、2つのバイナリ数の差に分解できることが示されています。

$${\displaystyle (\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}.}$$

したがって、乗算は、より単純な演算、すなわち乗数を加算し、その結果得られた部分積を適切な位置にシフトし、最後に乗数を減算することによって、元の数値の1の列に置き換えることができます。これは、2進乗数で0を扱う際にはシフト以外の操作は不要であるという事実を利用しており、99を乗算する際に99  =  100 − 1という数学的性質を利用するのと似ています。  

この方式は、乗数内の任意の数の 1 のブロック (ブロック内に 1 つの 1 がある場合を含む) に拡張できます。したがって、

$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&0&1&0\\\hline \end{array}}\ =M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58}$$$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&-1&1&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58.}$$

ブースのアルゴリズムは、1のブロックの最初の桁（0 1）に遭遇したときに加算を行い、ブロックの終わり（1 0）に遭遇したときに減算を行うという、この従来の方式を踏襲しています。これは負の乗数にも適用できます。乗数の1が長いブロックにグループ化されている場合、ブースのアルゴリズムは通常の乗算​​アルゴリズムよりも少ない加算と減算で済みます。

IntelのPentiumマイクロプロセッサは、 64ビットハードウェア乗算器でBoothアルゴリズムの基数8版を使用しています。基数8乗算の実装方法のため、キャリー先読み、キャリー選択、Kogge–Stone加算を組み合わせてレイテンシを最小限に抑える方法で3倍乗算の特殊なケースを実行するための複雑な補助回路が必要です。^{[ 3 ]}

• バイナリ乗算器
• 非隣接形式
• 冗長なバイナリ表現
• ウォレスの木
• ダッダ乗数

• コリン、アンドリュー（1993年春）。「バークベック・カレッジのアンドリュー・ブースのコンピュータ」。Resurrection （ 5）。ロンドン：コンピュータ保存協会。
• パターソン、デイビッド・アンドリュー；ヘネシー、ジョン・リロイ（ 1998）。コンピュータ構成と設計：ハードウェア／ソフトウェアインターフェース（第2 版）。米国カリフォルニア州サンフランシスコ：モーガン・カウフマン出版。ISBN 1-55860-428-6。
• スタリングス、ウィリアム（2000）。コンピュータ構成とアーキテクチャ：パフォーマンスのための設計（第5 版）。ニュージャージー：プレンティス・ホール社。ISBN 0-13-081294-3。
• Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques" . quadibloc . 2018年7月3日のオリジナルからアーカイブ済み。 2018年7月16日取得。

• 基数4ブース符号化
• RTLとコンピュータ算術の形式理論における基数8ブース符号化
• ブースのアルゴリズムJavaScriptシミュレーター
• Pythonでの実装
• C++での実装
• Javaでの実装
• ブースのアルゴリズムを使用する利点