Jeans & Development コンピューターのことなどを綴ったメモ (旧：目から鱗 w/SQLite)

プログラミングをしていると、整数値を１０で割るというコードは良く出てくる。例えば、整数を１０進法文字列に変換する場合など。

コンパイラーを用いて、１０で割るコードを記述すると、アセンブリーを見たときに0xcccccccdを掛けて右３５ビットシフトするコードになっていることがある。割り算はCPUにとって非常に高負荷な演算なので、掛け算とシフトに置き換えることで、高速化を図っているようだ。32ビットのほとんどのCPUでは、32ビットどうしの掛け算の結果を64ビット値として得、上位32ビットと下位32ビットを２つのレジスターに格納するようになっているので、「0xcccccccdを掛けて右３５ビットシフト」は非常に効率がよい。

では、１０以外の数値での割り算はどうかと、ネットで検索してみたが、包括的に解説している記事は見つからなかった。そこで、ちょっと調べてみた。

0xcccccccdという値は何かというと、0x100000000(4294967296)を10で割り、左３ビットシフトした値である。正確には3435973836.8であるが、整数値しか扱えなので切り上げて、3435973837(0xcccccccd)にしてある。右３５ビットシフトは、0x800000000(34359738368)での割り算に等しい。従って、「0xcccccccdを掛けて右３５ビットシフト」は、3435973837を掛けた後に34359738368で割る演算である。ここで、「3435973837を掛ける」のではなく「3435973836.8を掛ける」のであれば、数学的に正しい演算をしていることになるが、実際には0.2の誤差がある。この誤差が結果に影響を及ぼさなければ、「0xcccccccdを掛けて右３５ビットシフト」は問題なく使えることになる。

「3435973836.8を掛ける」ではなく「3435973837を掛ける」場合、値が少し大きくなる可能性がある。コンピューターにおける整数型の演算では、割り算の結果を切り捨てにするから、数学的な演算の結果の少数部分が0.9になる場合に、異なる結果を生み出す可能性がある。逆に言えば、数学的な演算の結果の少数部分が0.9の場合でも常に同じ結果を生み出すのであれば、すべての整数値に関して正確に演算できることになる。

32ビット整数では、4294967296より小さな値しか扱わないから、この範囲内での最大の値、4294967289で同じ値になるかどうかを判断すればよい。4294967289*3435973837/34359738368=429496728.925であるので、切り捨てると同じ429496728になることが分かる。

では、他の整数値ではどうだろうかと、調べてみた。次のコードを、C++で実行。

#define div32(x,y,z) ((((unsigned long long)x)*((unsigned long long)y))>>z)

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int i,j,num,div,rem,mul,shift,valid,mul2,shift2;
	unsigned int res1,res2;
	FILE* fh;
	// Open a file to store the result.
	fh=fopen("result.txt","w");
	fprintf(fh,"num,mul,shift,valid\n");
	// Test several numbers used for div.
	for(num=1;num<65536;num++){
		// Determine the parameters
		div=(unsigned long long)0x100000000/(unsigned long long)num;
		rem=(unsigned long long)0x100000000%(unsigned long long)num;
		if (rem==0) {
			// num==2^n
			// Just shifting is the equlvalent of div.
			div=num;
			for(shift=0;(div=div>>1);shift++);
			fprintf(fh,"%d,0x00000001,%d,32\n",num,shift);	
		} else {
			// Determine values to use.
			mul=div;
			shift=32;
			while(mul<0x80000000){
				shift++;
				mul=((unsigned long long)((unsigned long long)1<<shift))/(unsigned long long)num;
			}
			mul++;
			// Check validity
			for(valid=32;valid;valid--){
				j=0xFFFFFFFF>>(32-valid);
				for(i=0;i<num;i++){
					// Check values "num" times from the largest ones.
					if (div32(j,mul,shift)!=j/num) break;
					j--;
				}
				if (i==num) break;
			}
			if (valid!=32) {
				// Try the other ways
				mul2=div;
				shift2=31;
				while(mul2<0x80000000){
					shift2++;
					mul2=((unsigned long long)((unsigned long long)1<<shift2))/(unsigned long long)num;
					mul2++;
					// Check validity
					for(i=0;i<num;i++){
						// Check values "num" times from the largest ones.
						j=0xFFFFFFFF-i;
						if (div32(j,mul2,shift2)!=j/num) break;
					}
					if (i==num) {
						// Found an available combination
						mul=mul2;
						shift=shift2;
						valid=32;
					}
				}
			}
			fprintf(fh,"%d,0x%x,%d,%d\n",num,mul,shift,valid);	
		}
	}
	fclose(fh);
	return 0;
}

結果の一部を、下に示す。

num,mul,shift,valid
1,0x00000001,0,32
2,0x00000001,1,32
3,0xaaaaaaab,33,32
4,0x00000001,2,32
5,0xcccccccd,34,32
6,0xaaaaaaab,34,32
7,0x92492493,34,31
8,0x00000001,3,32
9,0xe38e38e4,35,32
10,0xcccccccd,35,32
11,0xba2e8ba3,35,32
12,0xaaaaaaab,35,32
13,0x9d89d89e,35,32
14,0x92492493,35,31
15,0x88888889,35,32
16,0x00000001,4,32
17,0xf0f0f0f1,36,32
18,0xe38e38e4,36,32
19,0xd79435e6,36,31
20,0xcccccccd,36,32

"num"で割る場合は、"mul"の値を掛けて、右"shift"ビットシフトすればよい。"valid"で示されたビット幅の整数値に関して、エラー無く演算できる。65536までの結果は、こちらを参照されたい。

結果を見て分かるように、すべてのケースに於いて、31ビット長の符号無し整数に関して、有効である。符号付き整数で考えれば、数値はすべて31ビット長で表現されるから、32ビット符号付き整数値のすべてに対応できることになる。C++での確認では、少なくとも、65536までの割り算には対応できる事が確認できた。

この方法が、32ビット符号付き整数・31ビット符号無し整数のすべてに関して有効であることは、数学的には、以下のように証明できる。