15.2.2 筆算除算アルゴリズム

筆算 NxM 除算は手計算と同じ方法ですが，基数は 2^mp_bits_per_limbとなります。詳細はKnuth section 4.3.1 algorithm Dと，mpn/generic/sb_divrem_mn.cをご覧下さい。

簡単に解説すると，割られる数が割る数より大きい間は，商の高いリムが求められ， Nx1 積である q*dが割られる数から引かれていきます。正規化した割る数(最大有効ビットが１）を使うと，商を構成する各リムは2x1除算と1x1 乗算に減算を何回か行って得ることができます。2x1 除算は割る数の大きいリムで行われ，ハードウェアの除算命令か，逆数の乗算の高速な方を使います(Single Limb Divisionと同じ)。 商は大きくなり過ぎることもありますが，割る数を加減すれば防げますので，滅多に起こりません。

商のリムの個数である Q=N-Mを用いると，これはO(Q*M) のアルゴリズムになり， QxM 筆算乗算アルゴリズムと同程度のスピードで実行できます。実際には，余計な乗算と除算がQ個の商リムそれぞれに入りますので，多少違ってきます。