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 件のコメント:
コメントを投稿