引き過ぎを戻す必要があるのか?

筆算では、引き過ぎて部分剰余がマイナスになってしまった場合は、商を一つ減らして、やり直すという手順を踏むが、本当に、戻す必要があるのだろうか?

ある桁で除数Dを引いて、部分剰余がマイナスになっても、次の桁で除数D(一つ桁がずれているので、値としてはD/2)を足せば、結果としてD/2を引いたことになる。これは最初の桁では商を1から0に減らし、次の桁で商を1にするのと同じである。

ということで、引き算の結果、部分剰余がマイナスになっても元に戻さず、次のステップで除数を足し込むという割り算法が考案された。この方法は、部分剰余を元に戻さないので、Non Restoring Division(引き放し法。筆者は、引きっ放し法と書くべきと思うのであるが、学術用語としては重みに欠けるためか、引き放し法という用語が用いられている)と呼ばれる。引き放し法では、部分剰余がプラスの場合は除数Dを引き、部分剰余がマイナスの場合は、除数Dを加える。

図3の例は、"101000"=40を"1100"=12で割るという例であるが、最初は被除数の下位2ビットはレジスタの下半分に残っている状態を図示している。最初は2ビットのずれがあるので、除数Dを引くことは12の4倍を引くことになる。そうすると、部分剰余は-8となる。結果がマイナスであるので、次の桁では除数を加える。桁の移動に伴い、被除数を1ビット左シフトするので、ここでは除数の2倍を加えることになる。そうすると、-8＋24となり、部分剰余は16となる。更に、最後の桁では、部分剰余がプラスであるので、除数12を引き、余りは4となる。

この場合の各桁の商であるが、最初が+1、次が-1、そして最後が+1である。従って、次の図4のようにプラスの部分商からマイナスの部分商を引いて、最終結果を求める。

このように引き放し法では、プラスとマイナスの商の合計を求める必要がある。しかし、プラスの商Qpとマイナスの商Qnは否定の関係にあるので、Qp-Qn = Qp + (*Qn+1) = Qp + Qp +1となる。つまり、プラスの商Qpを2倍(1ビット左シフト)して、最下位のビットに"1"を入れれば良い。そして、最上位からの桁溢れ(キャリー)は無視する。

更に良く考えると、プラスの商のビットが"1"になるのは、前回の加算の結果がプラスになった場合であるので、前回の加算結果のキャリーを反転して部分商として使えば1ビット左シフトもできてしまう。また、最下位の引き算の結果がプラスの場合は、符号ビットを反転して書き込めば+1もできてしまう。

ということで、最終の商を求めるのに加算は必要なく、引き放し法の割り算器の回路は、実は、図2と同じ回路で良い。但し、引き放し法では、最後の余りがプラスになるとは限らず、例えば、この方法で50÷12を計算すると、商が5で、剰余が-10になってしまう。このように剰余がマイナスになる場合は、剰余に除数の1倍を加算して、商を1減らすという処理が必要となる。

しかし、図2の回路では、マイナスの剰余の符号ビットを反転して商レジスタに書き込んでおり、最終の剰余がマイナスの場合は、"0"が書かれる。つまり、商の最後の+1が行われないので、都合の良いことには、自動的に商の値は-1された正しい値となる。

但し、剰余の値はマイナスのままなので、プラスの剰余の値が必要になる場合は、最後に除数を足し込むという補正サイクルが必要になる。ということで、引き放し法では、補正サイクルを必要とする場合でもN+1サイクルで商と剰余を求めることができる。