C++で、b[bit]の非負整数（例えば、unsigned long）

質問

C++で、b[bit]の非負整数（例えば、unsigned long）２つa0,a1を用いて、2b[bit]の非負整数を表現した場合の除算に関する質問です。

非負整数 a=a0*2^b+a0 を b[bit]の非負整数 D(≠0) で割った、商と余りを求めたいのですが、例えば次のように求めようとします、
d0 = a0/D.
m0 = a0%D.
d1 = (m0*2^b+a1)/D = (m0*2^b)/D + a1/D
m1 = (m0*2^b+a1)%D = (m0*2^b)%D + a1%D
ですが、ここで (m0*2^b)/D と (m0*2^b)%D をb[bit]の非負整数に対する演算のみ(ループ処理も含めたくない)を用いて計算する方法が思いつかないのですが、何か良い方法はありませんでしょうか？
上記が計算できれば、
商 d = d0*2^b + d1.
余り m = m1
と構成できます。

回答No.1

mtaka2 · ベストアンサー

まず、質問者さんの立てた式には、計算過程に誤りがあります。
d1 = (m0*2^b)/D + a1/D
m1 = (m0*2^b)%D + a1%D
この「/」が整数除算だとすると、この/・%では、正しい計算はできません。
(例えば、b=4bitで考えましょう。50=4*2^4+2ですが、これを7で割った場合、
(4*2^4)/7+2/7=48/7+2/7=6+0=6
(4*2^4)%7+2%7=48%7+2%7=6+2=8
つまり、50を7で割った商が6で余り8になってしまいます。
つまり、個別に出した商や余りを単純に足すことはできません。

さて、まず
a0をDで割った商をa0d、余りをa0m
a1をDで割った商をa1d、余りをa1m
2^bをDで割った商をbd、余りをbm
(a0*2^b+a1)をDで割った商を(d0*2^d+d1)、余りをm

とします。

このとき、元の数 a0、a1、2^bは、
a0 = a0d * D + a0m
a1 = a1d * D + a1m
2^b= bd * D + bm
という式が成り立ちますから、被除数 a0*2^b+a1 は、

(a0*2^b+a1) = (a0d * D + a0m)*2^b+(a1d * D + a1m)
= (a0d*2^b+a1d)*D + (a0m*2^b+a1m)
になります。ここで、右側の2^bに2^b= bd * D + bmを代入すると、
= (a0d*2^b+a1d)*D + (a0m*(bd*D+bm)+a1m)
= (a0d*2^b+a1d+a0m*bd)*D + (a0m*bm+a1m)
になります。

余りについては、
(a0d*2^b+a1d+a0m*bd)*D はDで割って余り0ですから、
m=(a0*2^b+a1)%D = (a0m*bm+a1m) % D
として求めることができます。

商については、
(a0*2^b+a1)/D = ((a0d*2^b+a1d+a0m*bd)*D + (a0m*bm+a1m))/D
= (a0d*2^b+a1d+a0m*bd)*D/D + (a0m*bm+a1m)/D
= (a0d*2^b+a1d+a0m*bd) + (a0m*bm+a1m)/D
になります。

つまり、基本としては、
d0=a0d
d1=a1d+a0m*bd+(a0m*bm+a1m)/D
a=(a0m*bm+a1m)%D
になります。
(ただし、この計算において、d1がb[bit]からオーバーフローする場合もありえます。
その場合をきちんと検査して、d1から適切な値を引いて適宜d0の方を足す、などとといった処理が必要です
また、a0m*bmがb[bit]からオーバーフローする場合もありえますので、そちらの検査も必要。

なお、
> 2^bをDで割った商をbd、余りをbm
については、そのままではb[bit]の演算では表現できませんが、
2^(b-1)をDで割った商をbd'、余りをbm'
とすると、
2^b=2^(b-1)*2 = (bd'*D+bm')*2
= 2*bd'*D+2*bm'
になりますから、
bd=2*bd'+(2*bm')/D
bm=(2*bm')%D
として、b[bit]の演算で求められます。

お礼

理解できました。丁寧に回答していただき、ありがとうございます。