2011年8月12日金曜日

3での整除

TAOCPに, レジスタ上の64ビットの数が3で整除出来るかどうかの判定プログラムをMMIXで書けという問題7.1.3-215がある.

十進の場合, 各桁の和が3で整除出来るなら, 元の数も3で整除出来るのは知られている.

理由は1も10も100も..., つまり10nが3を法として1であるからだ.

二進の場合も同様に考えられる. 二進の1, 10, 100,...は, 交互に3を法として1と-1だから, ビットに右から0,1,2,...と番号をつければ, 偶数番目の1の数と奇数番目の1の数の差が3の倍数の時に3で整除出来る.

これは十進法で11で整除出来る判定と同じだ. 3003や1023や5060は11で整除出来る.

だから, (nu x)をxの横方向の和をとる関数, (band x y)をxとyとのビットごとのandをとる関数とし, 32ビットでお許し頂くと

(= (modulo (- (nu (band x #x55555555)) (nu (band x #xaaaaaaaa))) 3) 0)

ということになる. 最後にまた3での剰余をとるのは違反っぽいが, 十進の場合の各桁の和の3の整除と同じで, 大きい数をいきなり割るのよりは簡単であり, とりあえずはこういう考えでよかろう.

この辺でTAOCPの解答をみると, 一見妙なプログラムである. MMIXのアセンブリコードに慣れていない向きには申し訳ないが, コメントをつけてある.



最後の3で割った剰余をみるのに, 001001...を左シフトし, 符号ビットが1になるのを利用している. これはうまい.

ではその前は何をしたか. レジスタ0は偶数ビットと奇数ビットの横方向の和(これをr0とする). レジスタ1は偶数ビットの横方向の和(r1とする). ところで, 奇数ビットの横方向の和(r2とする)も欲しい. r2=r0-r1のはず. レジスタ0はその後32-r0になり, 2ADDUでレジスタ1の2倍に足される.

つまりレジスタ1はr1+r1+(32-r0)=32+r1-r2になり, #x249...をこれだけ左シフトすることになる. bの定数は32ビット目, 8文字目の次が#x9なので, r1=r2のとき符号ビットが1, 負数になり, 3で整除出来ることが分かる.

巧妙なプログラムであった. 斯くの如きプログラムの解読は楽しい.

0 件のコメント: