[問題] 符号なし数の乗算

簡単のために符号なし数の乗算を考えよう。 $0010 \times 0011$ の 計算を行なうには、10 進数のときと同様に筆算で行なうことができる (図 7)。

図 7: 筆算による乗算の実行。

一般に $n$ ビットの 2 進数と $m$ ビットの 2 進数を掛け合わせると、 $n + m$ ビットになる (図 7 では 4 ビット $\times$ 4 ビットが 7 ビットに なっているが、最上位ビットから桁上がりが生ずることも考えられ、 その場合は 8 ビットになるのである)。

図 8: 乗算の第一のアルゴリズムの流れ図。

以上の筆算をアルゴリズムとしてまとめると図 8 のようになる (教科書、授業での「第一のバージョン」に相当)。 これはもっとも単純な乗算の実装の例である。 また、このアルゴリズムを $0010 \times 0011$ に適用したのが図 9 である。

図 9: 第一の乗算アルゴリズムを 4 ビットの乗算に適用した様子。

MIPS CPU にこのアルゴリズムを実装するには

• 64 ビット ALU
• 乗数用 32 ビットレジスタ
• 被乗数用 64 ビットレジスタ
• 積用 64 ビットレジスタ

が必要になる。 実際にはアルゴリズムに工夫が加えられ、

• 32 ビット ALU
• 被乗数用 32 ビットレジスタ
• 積用 64 ビットレジスタ (乗数と共用)

のように、乗算ハードウェアはより簡単に実現されている (教科書、授業における「最終バージョン」)。 そのアルゴリズムの詳細は教科書や授業を参照して欲しいが、 基本は上で見た筆算によるアルゴリズムである。

[問題]

1. 図 9 の空欄 (a), (b), (c) は、流れ図 8 において何に対応しているか。