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

ブースの乗算アルゴリズム（ブースのじょうざんアルゴリズム）は、2の補数表現のふたつの符号付整数の乗算の手法である。

このアルゴリズムは1950年ごろアンドリュー・ドナルド・ブースがロンドン大学バークベック・カレッジで結晶学を研究しているときに発明したものである。ブースは卓上計算機を使って研究していて、計算速度を向上させるために乗算を高速化する方法を探していてこれを発明した。彼の時代のマシンではシフトは加算よりも高速であり、ある種の数値では彼のアルゴリズムは高速であった。しかも負数についてもこのアルゴリズムは機能した。ブースのアルゴリズムはコンピュータ・アーキテクチャの研究において興味深い。

アルゴリズム

ブースのアルゴリズムは、符号付きの2の補数表現のNビットの乗数 Y において、最下位ビットよりさらに下に y_-1 = 0 というビットを暗黙のうちに補って隣接する2つのビットを調べる。Yの各ビット y_i（i は 0 から N-1）について、y_i と y_i-1 を調べる。それら2ビットが同じ場合、積（アキュムレータ） P は変化しない。y_i = 0 かつ y_i-1 = 1 の場合、被乗数に 2ⁱ をかけたものを P に加算する。y_i = 1 かつ y_i-1 = 0 の場合、被乗数に 2ⁱ をかけたものを P から減算する。このようにして得られた P の最終的な値が符号付きの積となっている。

被乗数と積の表現は特に指定されていない。一般にそれらも乗数と同様に2の補数表現とするが、加減算が可能な任意の数値表現が可能である。また、乗数をどちらから調べるかも規定されていない。通常はLSBからMSBへと進め、i = 0 からスタートする。この場合 2ⁱ をかける演算は P をステップごとに1ビットずつシフトする操作に置き換え可能となる。シフトではみ出たビットは捨てられ、その後の加減算はPの上位Nビットについてのみ行う。実際には様々な派生や最適化が存在する。

典型的実装

ブースのアルゴリズムは、2つの事前に決定された値 A および S のうちの1つを積 P に繰り返し加算（通常の符号なし2進数の加算）し、P を右方向に算術シフトするという形で実装できる。ここで、m を被乗数、r を乗数とし、m のビット数を x、rのビット数を y とする。

1. A と S の値を決定し、P を初期状態にする。いずれも長さは (x + y + 1) ビットとする。
   1. A: 最上位（左端）側のビット列に m の値を格納する。残る (y + 1) ビットは全て0にする。
   2. S: 最上位側のビット列に (−m) の2の補数表現を格納する。残る (y + 1) ビットは全て0にする。
   3. P: 最上位側の x ビットを全て0にする。その右のビット列に r の値を格納する。最下位（右端）ビットは0とする。
2. P の最下位（右端）2ビットを調べる。
   1. その中身が 01 の場合、P + A を計算し、オーバーフローは無視する。
   2. その中身が 10 の場合、P + S を計算し、オーバーフローは無視する。
   3. その中身が 00 の場合、何もしない。現在の P をそのまま次ステップで使用する。
   4. その中身が 11 の場合、何もしない。現在の P をそのまま次ステップで使用する。
3. 上のステップで得られた値を右に1ビット算術シフトする。その値を P の新たな値とする。
4. ステップ2と3を y 回反復する。
5. Pの最下位（右端）ビットを除去する。これが m と r の積である。

実施例

3 × -4 を実行する。m = 3、r = −4、x = 4、y = 4 である。

• m = 0011, -m = 1101, r = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• ループを 4回実行する。
  1. P = 0000 1100 0. 最後の 2ビットは 00.
     • P = 0000 0110 0. 右シフト.
  2. P = 0000 0110 0. 最後の 2ビットは 00.
     • P = 0000 0011 0. 右シフト.
  3. P = 0000 0011 0. 最後の 2ビットは 10.
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. 右シフト.
  4. P = 1110 1001 1. 最後の 2ビットは 11.
     • P = 1111 0100 1. 右シフト.
• 積は 1111 0100 となり、 -12 である。

2の補数表現では、表現可能な最小の負数の2の補数を計算すると本来のビット数では表現できない。例えば、被乗数が4ビットなら -8 (1000) という値の2の補数は 8 (01000) となる。つまり A と S で必要とするビット数が異なることになり、上述の実装ではうまく計算できない。1つの解決策として、A、S、P のビット数を1ビット増やせばよい。以下は被乗数も乗数も4ビットのとき −8 × 2 を計算する例である。

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0
• ループを 4回実行する。
  1. P = 0 0000 0010 0. 最後の 2ビットは 00.
     • P = 0 0000 0001 0. 右シフト.
  2. P = 0 0000 0001 0. 最後の 2ビットは 10.
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. 右シフト.
  3. P = 0 0100 0000 1. 最後の 2ビットは 01.
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. 右シフト.
  4. P = 1 1110 0000 0. 最後の 2ビットは 00.
     • P = 1 1111 0000 0. 右シフト.
• 積は 11110000 となり（最上位ビットと最下位ビットを除いた値）、−16 である。

動作原理

1の前後を 0で囲んだ正の乗数を考える。例えば、00111110 である。積は以下のようになる。

$M\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62$

ここで M は被乗数である。演算回数は以下のように書き換えることで 2回にまで減らすことができる。

$M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62$

積は被乗数の 1回の加算と 1回の減算で生成される。この手法を 1 のかたまり毎に実施することでいかなる乗数にも適用できる（1が 1ビットしかなくてもである）。したがって以下のようになる。

$M\times \,^{\prime \prime }0\;0\;1\;1\;1\;0\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58$

$M\times \,^{\prime \prime }0\;1\;0\;0{\mbox{-1}}\;1{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58$

ブースのアルゴリズムはこの手法に従って、1のかたまりの最初に当たったら（0 1）加算を実行し、1のかたまりの最後に当たったら（1 0）減算を実行するものである。この手法は負数の乗算でもうまく機能する。乗数の中の 1 が連続していれば、ブースのアルゴリズムでは一般的な乗算アルゴリズムよりも加算や減算が少なくて済む。逆に 1 が2つ以上連続していない場合、一般的なアルゴリズムよりも加算や減算の回数が多くなってしまう。

参考文献

1. Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2
2. Collin, Andrew. Andrew Booth's Computers at Birkbeck College. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
3. Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
4. Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.

関連項目

• 乗算器

外部リンク

• Radix-4 Booth Encoding
• Radix-8 Booth Encoding in A Formal Theory of RTL and Computer Arithmetic
• Booth's Algorithm
• Booth's Algorithm JavaScript Simulator
• Implementation in Verilog
• Implementation in Python
• Boothのアルゴリズム