再帰曲線

ドラゴン曲線に関する最初のブログ(2009年6月19日)に書いたことだが,...

左折を+, 右折を-と表示すると
+ + - + + - - + + + - - + - -
になる. 記号は15個あるが, 中央の + が最初の折り目で, その両側はもともと重なっていたのを開いたから, 並び順が中央を中心にして対象で, しかも+と-が入れ替わっている.

これを X₂ + Y₂ と書くと,
X₂ = + + - + + - -
Y₂ = + + - - + - -
である. するとこの両枝は同じなので,
X₂ = X₁ + Y₁
Y₂ = X₁ - Y₁
X₁ = + + -
Y₁ = + - -
最後は
X₀ = +
Y₀ = -
この+と-のパターンはなんだろうと思っていたが, はたと思いついたのは, Gray codeであった.

下の図は通常の二進法とGray codeの対応を示す. Gray codeの右の+と-は, Gray codeの1の数が, すぐ上のcodeのそれと較べて, 増えたか減ったかを示す. これが上のパターンと同じなのである.




なぜかというと, 枠で囲った部分がX₂とY₂で, その間が, 一番左の桁が1になったことで + になっているのである.

この図からははみ出すが, 16番のところは右から5ビット目が1になり, +となり, 24番のところは右から4ビット目が0になり, -になるのである.

一方, 通常の二進法の右の小さい丸は, 右から1ビット目と2ビット目, 2ビット目と3ビット目のように, 連続して2つの1が続く状態が現れた場所を示す.

1が連続すると, Gray codeの作り方から分かるように, 排他的論理和をとるので, 1が減るのである.

従って, -が現れるのは, 4n+3か, 8n+6か, 16n+12か, ...である.

これだけ分かるとドラゴン曲線のプログラムは書ける.

(define (test n p)
 (cond ((= (modulo n 4) 3) #f)
       ((= (modulo n 8) 6) #f)
       ((= (modulo n 16) 12) #f)
       ((= (modulo n 32) 24) #f)
       ((= (modulo n 64) 48) #f)
       ((= (modulo n 128) 96) #f)
       ((= (modulo n 256) 192) #f)
       ((= (modulo n 512) 384) #f)
       (else #t)))

山場はこのtestだ. こういつまでも書くわけにはいかないから, nがどんなに大きくてもいいように, 下のプログラムでは書き直してある.

(define (moveto x y)
 (display (number->string x)) (display " ")
 (display (number->string y)) (display " moveto\n"))

(define (rlineto x y)
 (display (number->string x)) (display " ")
 (display (number->string y)) (display " rlineto\n"))

(define limit 64)

(define (test n p)
 (cond ((> p (* 2 n)) #t)
       ((= (modulo n p) (* 3 (/ p 4))) #f)
       (else (test n (* p 2)))))

(define (foo n dx dy)
 (rlineto dx dy)
 (if (< n limit)
  (if (test n 4) (foo (+ n 1) (- dy) dx)
                 (foo (+ n 1) dy (- dx)))))
(moveto 0 0)
(foo 1 20 0)