ブースの乗算アルゴリズム
ブースのアルゴリズムは、2つの事前に決定された値 A および S のうちの1つを積 P に繰り返し加算(通常の符号なし2進数の加算)し、P を右方向に算術シフトするという形で実装できる。ここで、m を被乗数、r を乗数とし、m のビット数を x、rのビット数を y とする。
A と S の値を決定し、P を初期状態にする。いずれも長さは (x + y + 1) ビットとする。 A: 最上位(左端)側のビット列に m の値を格納する。残る (y + 1) ビットは全て0にする。 S: 最上位側のビット列に (−m) の2の補数表現を格納する。残る (y + 1) ビットは全て0にする。 P: 最上位側の x ビットを全て0にする。その右のビット列に r の値を格納する。最下位(右端)ビットは0とする。
P の最下位(右端)2ビットを調べる。 その中身が 01 の場合、P + A を計算し、オーバーフローは無視する。 その中身が 10 の場合、P + S を計算し、オーバーフローは無視する。 その中身が 00 の場合、何もしない。現在の P をそのまま次ステップで使用する。 その中身が 11 の場合、何もしない。現在の P をそのまま次ステップで使用する。
上のステップで得られた値を右に1ビット算術シフトする。その値を P の新たな値とする。
ステップ2と3を y 回反復する。
Pの最下位(右端)ビットを除去する。これが m と r の積である。