左折を+, 右折を-と表示すると
+ + - + + - - + + + - - + - -
になる. 記号は15個あるが, 中央の + が最初の折り目で, その両側はもともと重なっていたのを開いたから, 並び順が中央を中心にして対象で, しかも+と-が入れ替わっている.
これを X2 + Y2 と書くと,
X2 = + + - + + - -
Y2 = + + - - + - -
である. するとこの両枝は同じなので,
X2 = X1 + Y1
Y2 = X1 - Y1
X1 = + + -
Y1 = + - -
最後は
X0 = +
Y0 = -
この+と-のパターンはなんだろうと思っていたが, はたと思いついたのは, Gray codeであった.
下の図は通常の二進法とGray codeの対応を示す. Gray codeの右の+と-は, Gray codeの1の数が, すぐ上のcodeのそれと較べて, 増えたか減ったかを示す. これが上のパターンと同じなのである.
なぜかというと, 枠で囲った部分がX2とY2で, その間が, 一番左の桁が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)
