C++でa/bの除算の切り上げが(a+(b-1))/bでできる理由

 メモ的な記事になります。

 除算の際に式を(a+(b-1))/bとする(a、bは整数型)ことで、除算の結果の切り上げができるということが感覚的にすぐには理解できませんでした。時間をかけて一応は理解したので、それについて記しておきます。

 まず、整数型で除算を行なった場合、デフォルトでは、切り捨てになります。例えば、a=9、b=2であれば、9/2=4.5で計算結果は切り捨てとなるため4となります。ここで、切り捨てではなく、切り上げで除算を行いたい場合、

(a+(b-1))/bとすれば、除算の結果を切り上げで計算できます。a、bに先ほどと同様の値を用いると、(9+(2-1))/2=(9+1)/2=5となります。この場合は5ぴったりになりましたね。他にもa=11、b=3の場合、(11+(3-1))/3=(11+2)/3=13/3≒4.33となります。そして、計算結果は切り捨てなので、4になりますね。a/b=11/3≒3.66のため、確かに切り上げの計算が行えています。

 (a+(b-1))/bを分解してみると(a/b)+1-(1/b)となります。私は最初1/bを引く意味がわからず、1を足すだけでいいのではと思いました。ただ、1を足すだけですと、例えば、a=4、b=2などのように除算を行なった際に余りが出ないような場合には除算の結果が1大きくなってしまいます。

 次に抱いた疑問点は1を足して1/bを引いた場合にうまく切り上げができない(結局従来の切り捨てと同じ計算結果になってしまう)のではないかということです。例えば、a/bの計算結果が4.1であった場合、欲しい答えは5になります。ここで、1/bが0.2などになってしまった場合には、結局(a/b)+1-(1/b)の計算結果は4.9になってしまい、切り捨てなので結果は4になってしまうのではないかということです。

 上記のようなことがどういった場合に起こるかということを考えてみると、a/bの小数部分よりも1/bの方が大きくなることがあれば、上記のようなことが起こってしまいます。そこで、a/bの小数部分と1/bの大小について考えました。ここでは、a、b共に1以上の整数とします。

1)a<bの場合

 a<bなので、計算結果は0<a/b<1になります。また、欲しい答えは1になります。この場合、aは整数型なので、1以上の値をとります。従って、a/b≧1/bとなります。従って、(a/b)+1-(1/b)≧1となるため、正しく切り上げられることがわかります。

2)a=bの場合

 (a/b)+1-(1/b)=2-(1/b)となります。b=1の場合にはa=1であり、欲しい計算結果は1です。b>1の場合には0<1/b<1であるため、1<(a/b)+1-(1/b)<2となるため、計算結果として1が得られることがわかります。

3)a>bの場合

 a>bなのでc、kを整数(cはb未満の整数)としてa=kb+cで表せます。よって、(a/b)+1-(1/b)=((kb+c)/b)+1-(1/b)=k+1+(c/b)-(1/b)となります。 ここで、kがa/bの整数部分、c/bがa/bの小数部分になります。cは整数であるため、1以上の値をとります。従って、a/bの小数部分は1/b以上の値をとります。

コメント