被加数の削減

加数の縮約は、符号なし2進整数の高速な2進乗算アルゴリズムです。加数の生成、加数の縮約、そして加算という3つのステップで実行されます。

手順

被加数の生成

二進数の乗算では、加数の各行は0か、乗算される数のいずれかになります。次の例を考えてみましょう。

 1001 1010倍 ----- 0000 1001 0000 1001

加数列の2行目と4行目は、最初の項と等価です。加数列を生成するには、各加数列ごとに単純なANDゲートが必要です。十分な数のANDゲートがあれば、加数列を生成するのにかかる時間は算術論理演算ユニットの1サイクルになります。

被加数の削減

加数は、2つの1ビット項と1つのキャリーインビットを受け入れる一般的な1ビット全加算器を用いて減算されます。これにより、合計とキャリーアウトが生成されます。全加算器は、合計が同じ列の加数に保持され、キャリーアウトが左にシフトされるように配置されます。各減算ラウンドでは、1つの列の3ビットが全加算器の2つの項とキャリーインとして使用され、その列の1つの合計ビットが生成されます。これにより、列のビットは3分の1に減算されます。ただし、右側の列はキャリーアウトビットをシフトするため、列のビットは加数の行数の3分の1に増加します。最悪の場合、減算ラウンドごとに行数が2/3に減算されます。

以下に、最初の縮約ラウンドの実行方法を示します。加数の「空」の位置はすべてゼロとみなされることに注意してください（ここでは「仮定されたゼロ値」を示すために「.」が使用されています）。各行の上位3ビットは、全加算器への3つの入力（2つの項とキャリー入力）です。合計は列の最上位ビットに配置されます。キャリー出力は列の左隣の2行目に配置されます。最下位ビットは加算器への単一の入力です。この加算器の合計は列の3行目に配置されます。キャリー出力は常にゼロであるため無視されますが、設計上は列の左隣の4行目に配置されます。設計上、1、3、5、…行目（上から数えて）には、その列自体の合計が入ります。2、4、6、…行目は、右隣の列からのキャリー出力値が入ります。

 1011 x0110 ----- ...0000 ..1011. .1011.. 0000... ------- 0111010 000100。 00000..

全く同じ方法で再度減算を行います。今回は、他のすべての被加数はゼロである必要があるため、上位3行の被加数のみが対象となります。

0111010 000100。 00000.. ------- 0110010 001000。

加数の有効行が2行だけになった時点で、縮約サイクルは終了します。基本的な全加算器は通常、算術論理ユニットの3サイクルを必要とします。したがって、縮約の各サイクルは通常3サイクル長くなります。

合計

残りの加数が2行だけになった場合、高速加算器を用いて加算します。高速加算器には様々な設計があり、そのどれを使ってもこのアルゴリズムを完了できます。

計算時間

加数削減アルゴリズムの計算時間は次のとおりです: T = 1Δt + r3Δt + FA (ここで、r は削減サイクル数、FA はアルゴリズムの最後の高速加算器の時間です)。