Life Game

前回の算法はセル1個ごとに次ステップの値を計算するものであった.

通常の計算機は, 1ビットCPUのconnection machineと違って, 語の処理が出来るから, セルの1行について計算したいとだれでも思うであろう.

前回の演習問題の後半はその行ごと処理である.

ある行xと上の行x^-と下の行x⁺からその行の次のステップの値が計算したい. 出来そうでもあり, 無理そうでもある. アルゴリズムは次の通り.

a←x^-&x⁺ (=z₃), b←x^-⊕x⁺ (=z₄), c←x⊕b, d←c»1 (=z₆),
c←c«1 (=z₂), e←c⊕d, c←c&d, f←b&e, f←f | c (=z₇), e←b⊕e (=z₈), c←x&b, c←c | a, b←c«1 (=z₅), c←c»1 (=z₁), d←b&c, c←b | c,
b←a&f, f←a | f, f←d | f, c←b | c,
f←f⊕c (=S₁(z₁,z₃,z₅,z₇)), e←e | x, f←f&e.
これをグライダーでやってみよう.


図のように, このグライダーは右下へ進む.
  001000 x^-
  000100 x
  011100 x⁺
  000000
xの行の計算は次のように進む.
a 001000 x^-&x⁺ (=z₃)
b 010100 x^-⊕x⁺ (=z₄)
c 010000 x⊕b (=x_nw⊕x_w⊕x_sw)
d 001000 c»1 (=z₆)
c 100000 c«1 (=z₂)
e 101000 c⊕d (=z₂⊕z₆)
c 000000 c&d (=z₂&z₆)
f 000000 b&e (=z₄&(z₂⊕z₆))
f 000000 f | c ((z₄&(z₂⊕z₆))∨(z₂&z₆)=z₇)
e 111100 b⊕e (=z₄⊕z₂⊕z₆=z₈)
c 000100 x&b (=x&(x^-⊕x⁺))
c 001100 c | a (=(x&(x^-⊕x⁺))∨(x^-&x⁺))
b 011000 c«1 (=z₅)
c 000110 c»1 (=z₁)
d 000000 b&c (S₁の計算開始 b=z₅ c=z₁ a=z₃ f=z₇)
c 011110 b | c
b 000000 a&f
f 001000 a | f
f 001000 d | f
c 011110 b | c
f 010110 f⊕c (=S₁(z₁,z₃,z₅,z₇)
e 111100 e | x (= x∨ z₈)
f 010100 f&e

1ステップ後の配列は以下の通り.
  000000
  010100
  001100
  001000

MIT Schemeのfixnum演算を使った実装は以下の通り.

(define (b x- x x+)
(let* ((a) (b) (c) (d) (e) (f))
 (set! a (fix:and x- x+)) (set! b (fix:xor x- x+))
 (set! c (fix:xor x b)) (set! d (fix:lsh c -1))
 (set! c (fix:lsh c 1)) (set! e (fix:xor c d))
 (set! c (fix:and c d)) (set! f (fix:and b e))
 (set! f (fix:or f c)) (set! e (fix:xor b e))
 (set! c (fix:and x b)) (set! c (fix:or c a))
 (set! b (fix:lsh c 1)) (set! c (fix:lsh c -1))
 (set! d (fix:and b c)) (set! c (fix:or b c))
 (set! b (fix:and a f)) (set! f (fix:or a f))
 (set! f (fix:or d f)) (set! c (fix:or b c))
 (set! f (fix:xor f c)) (set! e (fix:or e x))
 (set! f (fix:and f e)) f))