% 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つの値の最大公約数を求める場合に、片方または両方が負であっても最大公約数は同じことがわかったのでそれを用いて書き下したのが以下のコードである。

	#include <stdio.h>
	#include <stdlib.h>
	/*
	* a と b の最大公約数を求める関数 gcd
	* a と b が負の数でも通用する。
	*
	* ----
	*
	* これは、以下が自明であることを利用している
	*
	* gcd(a, b) = gcd(-a, b) = gcd(a, -b) = gcd(-a, -b)
	*
	* 最大公約数を G (G > 0)とし、a = Ga' b= Gb' とすると、a と b の符号
	* を入れ替えて如何に組み合わせても最大公約数はGとなる
	*/
	static int gcd(int a, int b)
	{
	int tmp = 0;
	// 絶対値をとることで、a, b のいずれか、または
	// 両方が負であっても通用するようになる
	a = abs(a);
	b = abs(b);
	while (b != 0) {
	if (b < a) {
	// swap (abs(b) is always bigger than abs(a)
	tmp = a;
	a = b;
	b = tmp;
	}
	//
	// s/%/-/ は正しいが、b と a の値の差が圧倒的に大きい
	// ときにずっと同じ値 a を引きつづけるため、非常に遅い
	//
	// b の方が大きい限り a を引き続けるということは、いず
	// れは a で割った余りを求めることと同義になる。よって
	// b % a の方が圧倒的に速い
	//
	// ※ % 演算子のオペランドが負であったときの結果は処理系
	// 定義であることに注意。だが、ここでは a, b は常に
	// 正になるように補正しているので無問題
	//
	b = b % a;
	printf("a:%d b:%d\n", a, b);
	}
	return a;
	}
	int main(int argc, char *argv[])
	{
	// no error processing
	printf("gcd is %d\n", gcd(atoi(argv[1]), atoi(argv[2])));
	}

view raw gcd.c hosted with ❤ by GitHub

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