整数の割り算の四捨五入

昨日、整数の割り算の四捨五入は (x+(y/2))/y で出来るよ〜と教えられた。どうしてそうなるのか理解出来なかったけれど、
http://aggregate.org/MAGIC/#Divide%20Rounding
でも紹介されているので結構有名な方法なのかも。

視覚的には、

a = x / y
b = x % y
c = x/y + 1/2
c = (x + y>>1) / y

整数演算では単独だと消えてしまう 1/2 を被除数に足しこんで混ぜ合わせて除算の一部として有効活用するって事だと思う。
なんとなーくは分かるんだけど、除数が奇数の場合に、整数演算で1/2、1ビット右シフトするとLSBの1が消えてしまうので一見問題があるように思えててしまうけど、色々考えてみたところ問題が無い事が分かった。

b + y/2 >= y の場合、
b >= y - y/2
y = (y/2) * 2 + 1 なので、
b >= y/2 + 1
b > y/2
整数の場合に奇数は２で割り切れないけれど、割った数に１を足した数は、実数で割り切った数より常に大きい。余りがその数以上なら 0.5以上という事が導ける。よって、四捨五入で１を足すというのを計算式に置き換えると、
(b + y/2) / y
になり、四捨五入計算は以下のように式の変形が行えるので、
c = a + (b + y/2) / y
= (a * y + b + y/2) / y
= (x + y/2) / y

結論：整数の割り算の四捨五入は (x+(y/2))/y で出来る。

自分が今までに書いた四捨五入の方法は、余りの二倍が除数より大きかったら四捨五入する、というものだった。だけどこの方法だと、商と余を一度の割り算命令で生成出来ない場合に…。

あと負の場合はまた別かも。

• • • • -

http://aggregate.org/MAGIC/#Divide%20Rounding
http://www.moge.org/okabe/temp/computer/node34.html
http://journal.mycom.co.jp/column/architecture/084/index.html
http://code.google.com/p/stringencoders/wiki/NumToA
http://www.hackersdelight.org/
http://d.hatena.ne.jp/siokoshou/20091219%23p1
http://d.hatena.ne.jp/melpon/20091110/1257816536
http://ls-al.jp/blog2/item_548.html
http://slashdot.jp/~bero/journal/458777
http://en.wikipedia.org/wiki/Rounding
http://blackfin.s36.coreserver.jp/index.php?id=138
http://akihiro.s56.xrea.com/mt/archives/000045.html