2010年2月12日金曜日

入れ子のかっこ

Gosperのハック

定数ステップで次を求めるかっこの足跡のアルゴリズムは, Gosperのハックにヒントがあるらしい. GosperのハックはMITのAIラボのHAKMEMのitem 175にあり, To get the next higher number with the same number of 1 bits のプログラムである. 元はPDP10の機械語だが, TAOCPのex7.1.3--20に通常の書き方がしてある. それをまたSchemeにすると

(define (gosper x)
(let* ((u (iand x (- x)))
(v (+ x u)))
(+ v (irsh (quotient (ixor v x) u) 2))))

iand, ixor, irshは符号なし整数値を二進数とみてビット演算する. 途中結果も含めて計算の進行状況を見るとこうなる.

x u v xor x / u y
000111 000001 001000 001111 001111 001011
001011 000001 001100 000111 000111 001101
001101 000001 001110 000011 000011 001110
001110 000010 010000 011110 001111 010011
010011 000001 010100 000111 000111 010101
010101 000001 010110 000011 000011 010110
010110 000010 011000 001110 000111 011001
011001 000001 011010 000011 000011 011010
011010 000010 011100 000110 000011 011100
011100 000100 100000 111100 001111 100011
100011 000001 100100 000111 000111 100101
100101 000001 100110 000011 000011 100110
100110 000010 101000 001110 000111 101001
101001 000001 101010 000011 000011 101010
101010 000010 101100 000110 000011 101100
101100 000100 110000 011100 000111 110001

これをみて理由を考える. まずxがα01a0bであったとする. ただしa≥1, b≥0である. (1aは1がa個並んでいること.) 上からの4行についていえば
x=000111, α=00, a=3, b=0
x=001011, α=001, a=2, b=0
x=001101, α=0011, a=1, b=0
x=001110, α=0, a=3, b=1
である. uは右端の1だから u=10b. vはxの右端の1に1を足すから, a桁連続している1が0になり, 繰上げが出る. v=α10a+b. xとvをxorするとαがキャンセルされて, 1a+10bになる. uで割ると0bがなくなり, 2ビット右シフトすると, 1a+1が1a-1になり, 結局 α10b+11a-1が得られる.
xのαの右にあった0は1に変り, bが1増え, aが1減り, 場所が交代した.
結果的に1の数は変らない.

Gosparハックの逆関数もある.(TAOCPex7.1.3--21)


(define (igosper y)
(let* ((t (+ y 1)) (u (ixor t y)) (v (iand t y)))
(- v (quotient (iand v (- v)) (+ u 1)))))


次にように計算が進行する.

y t u v and -v u+1 x
111000 111001 000001 111000 001000 000010 110100
110100 110101 000001 110100 000100 000010 110010
110010 110011 000001 110010 000010 000010 110001
110001 110010 000011 110000 010000 000100 101100
101100 101101 000001 101100 000100 000010 101010
101010 101011 000001 101010 000010 000010 101001
101001 101010 000011 101000 001000 000100 100110
100110 100111 000001 100110 000010 000010 100101
100101 100110 000011 100100 000100 000100 100011
100011 100100 000111 100000 100000 001000 011100
011100 011101 000001 011100 000100 000010 011010
011010 011011 000001 011010 000010 000010 011001
011001 011010 000011 011000 001000 000100 010110
010110 010111 000001 010110 000010 000010 010101
010101 010110 000011 010100 000100 000100 010011
010011 010100 000111 010000 010000 001000 001110


方法としては, yの右端が0の時, 最も右の`10'を'01'にする. yの右端が1の塊の時, その左の0を挟んだ左の1から右を01と1の塊にし, その右に0を詰める.
これをifで分岐せずに実行するのが味噌であるが, 説明は場合を分ける.

yの右端が0の時, y=α10b(b≥1), t=α10b-11, u=1, v=y, v and -v=10b, quotient (v and -v) (+ u 1)=10b-1; x=α010b-1.

yの右端が1の時, 1が全部右に寄ったら終りなので, 右の1の塊の左に0があり, その左に1があるとする. つまりy=α10a1b(a,b≥1)とする. t=α10a-110b, u=1b+1, v=α10a+b, v&-v=10a+b, u+1=10b+1 quotient (v&-v)(u+1)=10a-1, これをvから引くとα10a+b-10a-1=α01b+10a-1.

0 件のコメント: