15.2.5 完全除算

いわゆる「完全除算」とは，割られる数が割る数の完全な倍数になっていることが既知の時の除算です。 Jebeleanの完全除算アルゴリズムは，この前提を利用して，いくつかの効果的な最適化を行います(see References)。

考え方はこうです。例えば10進数の368154を543で割ることを考えましょう。 割られる数の最後の桁は4ですので，商の最後の桁は8でなければなりません。 これは4*7 mod 10から来ており，7は3 (割る数の最後の桁)の10を法とする逆数，即ち 3*7 ≡ 1 mod 10となります。従って，8*543=4344は 割られる数より差し引くことができ，363810となります。結果として低い方の桁はゼロになります。

このやり方を2番目の桁にも適用すると，商の次の桁は7 (7 ≡ 1*7 mod 10)となり， 7*543=3801を引いて325800となります。 最終的には商の3番目の桁である6 (8*7 mod 10)が得られ， 6*543=3258を引いてゼロになります。 従って，商は678となります。

しかしながら，乗法と減法は，割られる数の小さい3桁分に関しては必要ないことに気が付きます。 3桁の商を得るにはこれで十分だからです。 ということで，商の最後の桁については減算も必要ありません。2NxNの除算についてもこれと同様にして 実行でき，通常の筆算除算アルゴリズムの半分の労力で済みます。

NxM の完全除算はQ=N-Mリムの商を生成するので，通常の筆算除算アルゴリズムを 節約するために計算を2つのパートに分けます。まず最初に，商Qの各リムは乗算1回で求められ，2x1の除算や乗算は必要ありません。2番目に，交差積はQ>M～ Q*M-M*(M+1)/2であるか，Q<=M ～Q*(Q-1)/2であれば，減らすことができます。この節約は補足的なものです。 Qが大きい時には多くの除算を減らすことができ，Qが小さければ，交差積の回数を減らすことができます。

使用するモジュラ逆数はgmp-impl.hのbinvert_limbマクロで効率的に計算することができます。 32bitリムでは4つ，64bitリムでは6つの積で得られます。 tune/modlinv.cには，CPUにふさわしい，乗算の代わりのビット操作で行う別ルーチンを実装してあります。

準2次完全除算法はJebeleanが“Exact Division with Karatsuba Complexity”で提唱していますが まだ実装されていません。これは通常の除算に対して分割統治法的アプローチを取るものですが (see Divide and Conquer Division)，低い桁から高い桁の方に計算を行っていきます。 未実装ですが有望株としては“Bidirectional Exact Integer Division” （ Krandick & Jebelean）があり，商リムを割られる数の両端の桁から求めていくもので，2NxN 除算に必要な交差積の回数を半減させることができます。

3で割る時の完全除法の特別な場合はmpn_divexact_by3に実装してあります。 これはToom-3 乗法と mpq の標準化をサポートしています。3のモジュラ逆数を乗じて商の桁を出していくものです (つまり0xAA..AAB)。次のリムに対して桁借り上げが必要になるかどうかを決める2回の比較も行います。 桁借り上げの効用で乗算が不要になるので，パイプライン化した乗算機構が入っているCPUには有用でしょう。