典型的実装

ウィキペディア小見出し辞書

典型的実装

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/24 18:50 UTC 版)

「ブースの乗算アルゴリズム」の記事における「典型的実装」の解説

ブースのアルゴリズムは、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 の積である。