next up previous
: [問題] 符号付き数の乗算 : 乗算と除算 : 乗算と除算

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

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

図 7: 筆算による乗算の実行。
\begin{figure}\begin{center}
\epsfbox{mul1.eps}\end{center}\end{figure}

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

図 8: 乗算の第一のアルゴリズムの流れ図。
\begin{figure}\begin{center}\epsfxsize =7cm \epsfbox{mul_chart.eps}\end{center}\end{figure}

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

図 9: 第一の乗算アルゴリズムを 4 ビットの乗算に適用した様子。
\begin{figure}\begin{tabular}{c\vert l\vert c\vert c\vert c}
サイクル & ステップ...
...x{3.2ex}[0pt]{4} & (c) & 0000 & 0010 0000 & 0000 0110
\end{tabular}
\end{figure}
MIPS CPU にこのアルゴリズムを実装するには が必要になる。 実際にはアルゴリズムに工夫が加えられ、 のように、乗算ハードウェアはより簡単に実現されている (教科書、授業における「最終バージョン」)。 そのアルゴリズムの詳細は教科書や授業を参照して欲しいが、 基本は上で見た筆算によるアルゴリズムである。

[問題]

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


平成16年12月13日