% operator

http://0xcc.net/blog/archives/000083.html

剰余を求める % 演算子はプログラムの世界では非常によく用いられる。特に一定の範囲の数値があった場合に、剰余が同じ値で数値をグループ化する用途に役立つのは皆様ご存知でしょう。

たまたま2つの値の最大公約数を求める関数を再発明する機会があり、コードを書いていた。この問題に対して、この世界でよくある解法が「ユークリッドの互除法」である。これは以下の手順(※)で成り立つ

1. 2つの値のうち大きなものから小さなものを引く
2. 1. の結果と、値の小さなものについて、上記 1. を繰り返す
3. 1. の結果が0になったとき、その時に引いた小さい値が最大公約数である

上記 2. を繰り返すことは、最終的には値の小さなもので割ったときの余りを求めることと同義なので、この手順は剰余で代用することで速度向上を図るのが普通だ。これをコードにすると以下のような感じである。

b = b % a;

このときに、b と a のどちらか（もしくはいずれか）が負の数値だったらどうなるか。このコードをレビューしていた pascaljp から「オペランドが負の場合、結果も負の場合があるよ」と指摘されてびっくらこいた。

よーく考えると、負の剰余って複数通りの解釈ができる。

7 % -5 -> 余りは -3(商は-2)または 2(商は-1)
-7 % 5 -> 余りは 3(商は-2)または -2(商は-1)
-7 % -5 -> 余りは 3(商は-2)または -2(商は1)

これについては処理系によってまちまちのようで、それを詳しく示したのが上記の高林さんのエントリである。

実際、剰余演算子を使う場合、「余りの値については殆どの場合興味がなく、グループ化する用途には役立ってればいい」という考え方もあるだろうが、今回の場合みたく問題になることもあるんだなと再認識した次第である。

よく考えたら、2つの値の最大公約数を求める場合に、片方または両方が負であっても最大公約数は同じことがわかったのでそれを用いて書き下したのが以下のコードである。



(※) これは A, B の最大公約数をGとすると、B と A - B の最大公約数もGとなるという考え方に基づく。その証明は ここ あたりでもどうぞ。