|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 乗算 ： [じょうざん] (n) multiplication
ブースの乗算アルゴリズム（ブースのじょうざんアルゴリズム）は、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''i'' をかけたものを ''P'' に加算する。''y''i = 1 かつ ''y''i-1 = 0 の場合、被乗数に 2''i'' をかけたものを ''P'' から減算する。このようにして得られた ''P'' の最終的な値が符号付きの積となっている。 被乗数と積の表現は特に指定されていない。一般にそれらも乗数と同様に2の補数表現とするが、加減算が可能な任意の数値表現が可能である。また、乗数をどちらから調べるかも規定されていない。通常はLSBからMSBへと進め、''i'' = 0 からスタートする。この場合 2''i'' をかける演算は ''P'' をステップごとに1ビットずつシフトする操作に置き換え可能となる。シフトではみ出たビットは捨てられ、その後の加減算は''P''の上位''N''ビットについてのみ行う。実際には様々な派生や最適化が存在する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ブースの乗算アルゴリズム」の詳細全文を読む スポンサード リンク
|