SRT除算法

はじめに

2023年6月現在、ディジタル回路による高速な除算法であるSRT除算法についてググってみても、複雑であるか曖昧な説明しか見つけることはできなかった。本noteは基本的なディジタル回路に明るい人を対象に、SRT除算を理解してもらうことを目的にしている。

準備

除数の用語

$$
(z-r) / d = q, 0 ≤ r < d
$$

z: 被除数
d: 除数
q: 商
r: 余り

前提
被除数、除数ともにプラスであるとする。

基本回路

基本アルゴリズム

SRT除算のような近似値でない商を求めるディジタル除算のアルゴリズムは筆算をイメージすれば分かりやすい。

10進数の除算(筆算)

図1

図1のように、筆算では被除数を最上位桁から1桁ずつ見ていって、商を部分的に決定していく。このnoteでは繰り返しの各サイクルの初めに見えてる余りの大きさを部分剰余という。サイクルiの部分剰余をpr[i]と定義する。図の例ではpr[1]=16, pr[2]=52, pr[3]=8である。また、各サイクルの部分剰余を除数の適当な倍数で引いた後の値のことを除後部分剰余と呼び、サイクルiの除後部分剰余をres[i]と定義する。図の例ではres[1]=5, res[2]=8である(サイクル1の引き算の結果はサイクル2の部分剰余と重ねて書いてある)。また、各サイクルで決めた商の桁の値のことを部分商と呼び、サイクルiの部分商をpq[i]と定義する。図の例ではpq[1]=1,pq[2]=4である。

部分剰余条件

当然だが、除算では最終的に部分剰余がdより小さくなる。

$$
pr[最後のサイクル] < d
$$

このアルゴリズムの除算では引ける数は最大9dなので、これは以下と同値である

$$
pr[1つ前のサイクル] < 10d
$$

このためには、すべてのサイクルで部分剰余が10dより小さい必要がある。
なぜならば、仮にあるサイクルiでpr[i] >= 10dとなった場合、dは最大9倍で引けるのでres[i] >= pr[i] - 9d >= d。次のサイクルの部分剰余は、res[i]が10倍されて次の桁の数が足された数なので、pr[i+1] >= 10res[i] >= 10d。したがってpr[最後のサイクル]もまた10d以上になってしまうからである。

本noteではこの除算を成立させるための部分剰余の条件を部分剰余条件と呼ぶ。筆算でも必ず除数の方が大きい状態から演算処理を開始するが、こうすると部分剰余条件が満たされた状態からスタートできる。

回路

2進数の除算の筆算を図2に示す。

図2

10進数との違いは、部分剰余条件がpr[i] < 2dであり、部分商は0か1であることである。基本はこのアルゴリズム通りの回路を作る。

1. 除後部分剰余から1桁増やして部分剰余を作ることは、回路上では1ビットのシフト演算。

2. 部分商は、部分剰余を除数で引いてみて、結果が正ならば1、負ならば0とすればよい。

3. 除後部分剰余は、2で引いた結果が正の時のみレジスタを書き換えれば良い。

こうして次の図で示す回路が得られる。

図3

除数、被除数ともにNビットとすると、除数レジスタと商レジスタはNビット、被除数レジスタは2Nビットの長さを持つようにする。被除数レジスタの上半分を部分剰余として使うためである。商と被除数レジスタは1ビットの左シフト機能を備えている。

動作として、まず、除数レジスタに除数を入れる。そして、被除数レジスタの下半分に被除数を入れ、被除数レジスタの上位の半分はゼロクリアしておく。
次のステップをN回繰り返す。

1. 被除数レジスタと商レジスタを1ビット左シフトする

2. 被除数レジスタの上半分から除数を引く

3. 商レジスタの最下位ビットに引き算の結果が正ならば1、負ならば0を格納

4. 被除数レジスタの上半分に引き算の結果が正ならば引き算の結果を格納

この基本的な除算法ではビット数だけのサイクルが必要であり、32ビットデータ型のプロセッサでは32サイクルもかかってしまうことになる。

ゼロスキップ

割り算の最初は、被除数レジスタの上半分は0が詰まっており、明らかにサイクルを無駄にしている。整数の割り算の場合は、普通のプログラムでは、被除数の値も32ビットとか64ビットの語長を一杯に使うような値が出現するのは稀なので、0が連続していれば複数ビットの左シフトをまとめて1サイクルに行い、被除数の上位の0をスキップしてしまえば処理時間を短縮できる。
除数の最上位の1と並ぶ位置まで被除数の左シフトを繰り返すのがベストである。しかし、

1. 長い語のどこに最上位の1があるかを探す回路は、1サイクルで見つけるのには多くの論理ゲートが必要

2. 両者の最上位ビット位置の差に応じて任意のビット数の左シフトを行う回路も、多くの論理ゲートが必要

そのため、実用的には、被除数レジスタの下半分の最上位側の数ビットを検査し、それが全て0の場合はその部分が被除数レジスタの上半分に入ってきても除数を超えることは無いので、検査したビット数分の左シフトを行うという方法が一般的である。
例えば、32ビットの被除数の上位16ビットが0であるとすると、1サイクルに2ビットづつゼロスキップを行う場合では24サイクル（8+16=24）に短縮できる。