【算術演算小話その二】負の剰余について

今回は負の剰余の話です。

剰余は正の数同士の場合は何も問題ないのですが、負の剰余をとってしまうとはまることがあります。なぜなら言語処理系依存だからです。C++, pythonのそれぞれを比較すると下記のようになります。

(C)       -2 % 5 = -2
(python)  -2 % 5 = 3

計算結果は違っていますが、この二つプログラミング言語の剰余は、両者とも、以下の等式が成り立つような値と定義されています。

 x == (x / y)*y + x%y

つまり剰余の値は、

 x % y = x - (x / y)*y

という式で得られます。

剰余の計算結果が異なっている原因は負の値に対する除算の値が異なるからです。

(C)       -2 / 5 = 0
(python)  -2 / 5 = -1

下のグラフを見ていただければわかると思うのですが、pythonの場合、除算の結果は「x 以下の最も大きい整数」で返しますが、Cの場合は「絶対値で0に近い整数」となります。

これは、Cの場合、負の数については切り上げを行い、正の数については切り下げを行うという処理になります。これを0の方向に丸めるといいます。 (ここでの「切り下げ」「切り上げ」の定義は、切り下げが負の無限大方向への丸め, 切り上げは正の無限大方向への丸めです。)

C++では負の除法に対する定義は処理系定義となっていますが、C99で除算した場合は0方向へ丸めると定義されているためそれに従うのが一般的のようです。

Cでpython形式の剰余を使いたいという場合は以下のように定義すれば良いのではないかと思います。

int imod(int i, int j){
  if(j < 0){
    return (i < 0) ? -(-i % -j) : (i % -j) + j;
  }else{
    return (i < 0) ? -(-i % j) + j : i % j;
  }
}

最初は条件分岐を無くそうとしたのですが、残念ながら難しいようでした。

これはj > 0かつ除算が0方向に丸められるという前提をおくと、以下のように簡単化できます。つまり負の値の剰余に対しては、忘れずにjを足すと覚えれば大丈夫なようです。

int imod(int i, int j){
  return i % j + (i < 0 && -i != j) ? j : 0;
}

これは、例えば以下のような問題を解く時に便利かなと思いました。

問題設定: 現在時刻が与えられた時に40分前の時刻を返しなさい。

python形式の剰余を使うと、よりシンプルにかけるようになる気がします。

int hour = 2;  int min = 27;
min -= 40;
if(min < 0)
    hour = imod(hour - 1, 24);
min = imod(min, 60);
printf("%02d:%02d\n", hour, min);

参考URL

また作成したグラフはwikipediaの床関数のグラフの作り方を参考にさせて頂きました。

・【算術演算小話その一】倍数への切り上げ・【算術演算小話その二】負の剰余について】・【算術演算小話その三】コンパイラの除算最適化