乗算と除算 - 組み込みC/C++

前回のエントリで乗算器と除算器の話題に触れました、今回はコーヒーブレークとして実践的ではないですが乗算と除算をハードウェアではなくてソフトウェアで実現する場合どうするかを見ていきたいと思います。

乗算(掛け算)

　筆算の手順をそのまま再現しますので例として0b1001 × 0b0110 (9×6)を見ていきましょう。

\begin{align*}\begin{array}{rr} & 1001 \\ × & 0110 \\ \hline & 0000 \\ & 1001~~ \\ & 1001~~~~ \\ & 0000~~~~~~\\ \hline & 0110110 \end{array}\end{align*}

答えは0b0110110 = 54 になりました。よくよく筆算の中身を見てみると0b0110を下位ビットから走査して、ビットが立っていたら0b1001をずらして足すという構造に気付くかと思います。さっそくコードにプロットしてみましょう。(固定小数点の時に作成した積の関数とリプレースできる形で書きます。)

	UnFix16 operator*(  CFix16 &cF )
	{			
		UnFix16 uF;

		__int64 i_a = 0;
		for(int i=0 ; i<32; i++){
			if( ((__int64)cF.get().iNum >> i) & 0x01 ){
				i_a += ( (__int64)m_uF.iNum << i);
			}
		}
		uF.iNum = i_a >> 16;

		return( uF );
	}

32bitの計算ですが、計算過程は64bitに拡張しています。これは筆算を見ればわかるように、例えば4ケタ同志の積は8ケタになっており計算過程、結果においてはbitを拡張しています。とはいえ32bitしか表現できませんので、一端64bitまで拡張して最後に16bitづらして小数点の位置を調整しています。

除算(割り算)

　割り算も幾つか方法はあるものの乗算同様、筆算をプログラムで再現することになります。例として0b1101 ÷ 0b0010 (13÷2)を見てみましょう。(mathjaxというサービスでTEXを表示していますがcline命令を実装していないみたいで筆算らしからぬ見た目になってしまいました。)

\begin{align*} \begin{array}{r|rr} & 0110.1 & \\ \hline 0010 & 1101.0 \\ & 10~~~~~~~ & \\ \hline & 10~~~~~ & \\ & 10~~~~~ & \\ \hline & 01~~~ &\\ & 0~~~ & \\ \hline & 10~ & \\ & 10~ & \\\hline & 0~ & \end{array}\end{align*}

答えは6.5になっていますね。掛け算と同様、構造をよく見てビットを走査していきたいのですが、割り算は最上位ビットから検算していく仕組みです。最上位ビットから一つづつ位を増やしていき、順次0b0010を引いていきます。引ける時にビットを立てて、引けない時には0を置きます。それではプログラムを見てみましょう。

	UnFix16 operator/(  CFix16 &cF )	
	{			
		UnFix16 uF;

		__int64 i_a = 0;
		__int64 i_b = 0;
		__int64 i_op1 = (__int64)m_uF.iNum;
		__int64 i_op2 = (__int64)cF.get().iNum << 32;
		for(int i=1; i<=64; i++){
			i_a <<= 1;
			i_op1 <<= 1;			
			i_b = i_op1 - i_op2;
			if( i_b >= 0 ){
				i_a |= 0x01;
				i_op1 = i_b;
			}
		}
		uF.iNum = i_a >> 16;

		return( uF );
	}

m_uF.iNumが割られる数で、cF.get().iNumが割る数です。最初に32bit左シフトしていますが、本来なら割られる数は最上位ビットから走査していくため、m_uF.iNum >> 32-i みたいな項が現れます。しかし残念ながらシフト演算はX >> -1と言うようにマイナス値のオペランドを設定しても、X << 1 と解釈してくれない為、桁以上の計算に制限が出てきます。そこで左シフトだけ使えば良いようにと最初に割る数の方の位を拡張しました。掛け算同様、最後に小数点の位置を調整しています。

まとめ

　ソフトだけで乗算、除算を実現しようとすると、見てきたように計算量が大きくなってしまいます。ハードウェアで実装されている乗算器、除算器はこれら手間をとってかわってくれています。他にもハードウェアが肩代わりしてくれる処理が多くあるのでアーキテクチャの資料をよく見ましょう。