15.2.1 単一リムの除算

Nx1の除算は，2x1の除算を，高い桁から低い桁へ繰り返し実行して行います。これはハードウェアの 除算命令と逆数の乗算のうち，実行しているCPUに適したものを選んで行います。

逆数の乗算はMöller と Granlund (see References)の論文“Improved division by invariant integers”に基づいて実装されたgmp-impl.hにあるudiv_qrnnd_preinvマクロで行っています。 考え方としては，1/d (invert_limb参照)の固定小数点近似値を作り，割られる数の高い方のリムから(プラス1bit分)乗算して商qを求めるものです。 dは正規化(高いビットが1になる)されているものとすると，qは1より大きくなることはありません。この割られる数からq*dを引くと余りが得られるので，qもしくはq-1が商となります。

この結果，除算が2回の乗算と４，５回の演算操作で実行できます。低いレイテンシの乗算機構を持つCPUでは，逆数の計算が必要にはなりますが，４，５リム以上であればコスト的に引き合い，ハードウェアの除算命令より高速に実行できます。

割る数が確実に正規化されている時は，汎用Cルーチンの __udiv_qrnnd_c，もしくは逆数の乗算を使って，a*2^k÷d*2^kとして行います。ここでaは割られる数で，kはd*2^kセットの高いビットを持つのに必要となる数です。 割られる数に対するビットシフトは通常“on the fly”で実行されます。つまり，各ステップで適当なビットを抽出していくということです。こうすることで，商のリムが段々と計算されていきます。余りが欲しい時のみ， 割られる数のシフトを戻して r = a mod d*2^kを計算し，最後のステップでr*2^k mod d*2^kを行います。こうすることで，ビットシフトに時間がかかったり，レジスタの少ないCPUでは高速化できます。

逆数の乗算は，一度に二つのリムをまとめて行うことができます。同じ計算を2回行うことになりますが，逆数は2つのリムで表現し，割る数の低いリムはゼロを詰め込んで扱います。余計な仕事が必要になり，逆数は2x2乗算が必要になりますが，4つの 1x1は独立に実行できますので，並列化可能です。 同様に q*dを求める2x1の計算も可能です。 実質的には，2リムを2回の乗算で実行した方が，1回に1リムだけ扱うよりはレイテンシに対する効果が出てきます。これは一度に3～4リムまで拡張します。逆数を適用する手間はかかりますが，乗算のスループットの限界まで高速化することができるようになります。

逆数については同様のアプローチを，割る数が半リムの場合は半リム計算にも適用することができます。 この場合は，逆数に対する1x1 乗算を2つの(1/2)x1乗算に直すことができ，高速な半リム乗算を使うことで，パイプライン化されていなくても，CPU資源の節約ができます。