整数演算Tips

整数演算Tips

世の中には、浮動小数点演算(float型、double型)を使わず、計算を行う必要があるケースが結構あります。

ここでは、C言語で整数演算をするときのTipsをまとめています。ほとんど自分用。

四捨五入、切り上げ

C言語で整数演算を行うと、小数点以下は切り捨てになりますが、四捨五入や切り上げしたい時もあります。

正の整数A、Bで、A/Bの計算結果は小数点以下切り捨てになります。
これを四捨五入したい場合は、

(A + B/2)/B

とします。
切り上げしたい場合には、

(A + (B-1))/B

とすれば良いです。

割られる数が大きい場合の割り算(筆算っぽい方法)

割られる数が整数型に収まりきらない場合、割り算の筆算と同様の方法が便利な場合があります。

例えば、X、Yが正の整数として、X * Pを、Yで割る場合を考えます。結果は、32bitに必ず収まるものとします。
この場合、P = A * Bとして、X * A / Yをまず計算し、余りを*Bして、さらにYで割るという、割り算の筆算と同じ操作を行うことにより、整数型に収まらない大きな値を割ることが可能です。

Q = (X * A) / Y
R = (X * A) % Y
R *= B
Q = (Q * B) + (R / Y)
R = R % Y
if(R > Q/2){ R = R + 1 } // 四捨五入

のように計算します。
A, Bの決め方は、下記の図のように、オーバーフローが起こらないように決めます。もしどうしてもオーバーフローが起こる場合、P = A * B * Cとして、三回の割り算に分けることも可能です。

この方法の利点は、精度が高いことです。浮動小数点演算を使った場合と同じ結果が得られます。

割る数が大きい場合

上記割られる数が大きい場合で、さらに割る数も整数型に収まらない場合、割る数Yが完全に未確定でなく、Y1 * Y2の形で表せるのであれば、二段階に分けて割り算すれば良いです。

Q1 = X / Y1
Q2 = Q1 / Y2
※Y = Y1 * Y2

割る数も割られる数も大きい場合

A * X/Yを計算する場合で、X、Yがどちらも変数で大きな数の場合、A*Xの計算もオーバーフローする場合があります。計算結果にある程度の精度劣化が認められるのであれば、A * ((X >> S) / (Y >> S))として計算しても、問題ないかも知れません。

逆数を計算する方法

X, Yを正の整数として、X * P / Yを計算する場合で、Pがかなり大きい数であるため、X * Pが整数型に収まりきらない場合を考えます。(X < Y) PもXも変数で、因数分解できない場合、上記の「筆算のような」方法は使えません。この場合、

Q = Y / X
R = Y % X

として、

P / (Q + R/X)

を計算するという方法があります。筆算の方法と比較して、精度は落ちます。実際は、R/Xでの精度劣化を補うため、(P << S) / ((Q << S) + (R << S)/X)のように、分子、分母共に同じ数をかけておきます。(Sビットシフトで、オーバーフローしないように注意。) Qと比較して、Rの比率が大きくなればなるほど、精度が劣化します。もしY≒Xで有ることが分かっているなら、(Y-X)/Xをこの方法で計算したほうが、精度が保てます。

割り算の結果を二乗する

(A/B)＾2を計算したい場合、精度を保持したまま計算するには、

Q = A / B
R = A % B

result = Q*Q + (2*Q*R + B/2)/B

とします。ただし、2*Q*Rがオーバーフローしないように気をつける必要があります。Rの最大値は、Bであるため、2*Q*Bが32bitに収まることを確認すれば良いことになります。

LOG計算

Xを正の整数として、log_n(X)を、浮動小数点演算なしに計算するには、演算の高速化の為によく用いられる、テーブルを使った手法を使います。基本的には、log₂(X)の関数を用意しておき、log_n(X)の場合は、底の変換を使えば良いです。底が2の関数を用意する理由は、2進数がコンピュータ上で扱いやすいためです。

例えば、log₂(X)の値に100をかけた値を整数値として返す関数を実装するとします。必要な精度に応じて、100*log₂(1) - 100*log₂(2ⁿ)までの値のテーブルを用意します。log₂(X)の計算方法としては、X <= 2ⁿの場合はテーブルの値をそのまま返します。X > 2ⁿの場合、X <= 2ⁿとなるまでX/2 (右シフト)を繰り返します。そして、最終的にX <= 2ⁿとなってテーブルの値を求めた後、そのテーブルの値に、(右シフト回数)*100を足します。
shift_num = 0;
while(X > table_size){
    X >>= 1;
    shift_num += 1;
}
return log2x100[X] + shift_num*100;
log(A*B) = log(A) + log(B)になるという性質を使っています。

整数演算についてまとまった本がなかなか無いので、ここでまとめていきます