多倍長整数の割り算

1.定義

非除数(割られる数)


123454322の場合となる

除数


11111の場合となる


余り


基数(進数)

D=1桁の最大値+1 10進数の場合は10

関係式


2.計算を効率化するために非除数・除数にkを掛ける

全桁の割り算を実行するのは困難であるため、上位桁同士の割り算を実行し商を推測する
除数にkを掛けた結果、除数の最上位の値が になるようにkを決める
この結果btが非常に小さい場合、商の計算の効率が悪いのでkを掛けることにより商の候補が絞りこみやすくなる


a,bにkを掛ける

3.商の最上位桁位置及びu及び商の桁値quを求める

3.1.as≧bt 非除数の最上位桁の値≧除数の最上位桁の値 である場合

a≧bD^(s-t)の時 非除数≧除数の最上位をs-t桁
kを掛けていることにより

であることから、Dを消去すると



となるので最上位の商は1となる。
商の最上位桁の位置は


最上位桁の商の値は

3.2.as≧bt 非除数の最上位桁の値≧除数の最上位桁位の値である場合

a < bD^(s-t)の時 非除数の最上位桁<除数の最上位桁の場合(非除数2桁/除数1桁で計算)





分子 , 分母


(1)(2)式より不等式を作成すると









ならば
(3)式の右辺の数値の範囲は

したがっての上位2桁 / bの上位1桁 とすると qはq'と等しいか(q'+1)または(q'+2)のいずれかである。

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