多倍長整数の割り算2

前ページでは仮商と真の商は2以上の誤差がないことが分かったが、さらに精度を上げ誤差を1以下とする方法を探る
前ページの仮商を計算後、非除数上位3桁目および除数の上位2桁目を使用して誤差が2のケースを削除する。さらに誤差が1のケースを少なくする。

手法

またはであるかチェックする
上記式が成立する場合q'から1を引くr'にb_{t}を加える
ならチェックを繰り返す

チェック2

非除数3桁÷除数2桁がq



(1)式に左式の左辺を代入



非除数3桁÷除数2桁がq≦q'+1の証明

なら




となることから矛盾であるq=q'+2のケースはない

実行ファイルとソースファイルのダウンロード