再帰曲線

東京大学新聞に2012年度後期日程入試問題が掲載されていた. その総合科目IIにフラクタルの絵があった. 問題はフラクタル次元を計算するものだが, 私としてはその絵を描くプログラムに関心があった.

まず図はこういうものだ.


左からF₁, F₂, F₃

左からG₁, G₂, G₃
問題に記述はこうだ.

はじめに, 1辺の長さ1の正方形をF₀とする. F₀を, 1辺の長さ1/3の9個の小正方形に分割し, 中央の小正方形を取り去ったものをF₁とする.  また, それぞれの小正方形を1辺の長さ1/3のユニットと呼ぶ. 次に, F₁ を構成する8個のユニットのそれぞれについて, これを9個の小正方形に分割し, そこから中央の小正方形を取り去ったものをF₂とする.  また, この分割で得られたそれぞれの小正方形を1辺の長さ1/9のユニットと呼ぶ. 以下, 同様の操作を繰り返して得られる図形をF₃, F₄, ...とする.

PostScriptのこのプログラムは次のようだ.

/n 5 def
/l 540 def
/xs [0 1 2 0 2 0 1 2] def
/ys [0 0 0 1 1 2 2 2] def
/a {n 0 eq {0 0 moveto l 0 rlineto 0 l rlineto l neg 0 rlineto
 closepath fill}
 {/n n 1 sub def
 gsave 1 3 div dup scale
 0 1 7 {/i exch def
 xs i get l mul ys i get l mul gsave translate a grestore} for
 grestore
 /n n 1 add def} ifelse} def
 40 40 translate a

まず全体の次数nを決める. この例では5. 1辺の長さlも決める. 次に8個の正方形を描くので, その順に左下のxとy座標のリストxs, ysを書く. そしてユニットを描く手続きaの定義だ.



n=0なら, 長さlの正方形を書く. そうでないならnを1減らし, スケールを1/3にする. dupはx座標とy座標の両方を1/3にするためのもの. gsaveとそれに見合うgrestoreは, スケールや原点を変えるとき, 以前の環境をスタックするものである. xsとysから各小正方形の原点の座標をとり, 図を各手続きaを呼ぶ.

こうしてn=5を描いたのがこれだ.



次のは少し手ごわい.

はじめに, 1辺の長さ1の正方形G₀を, 1辺の長さ1/2の正方形ユニット4個に分け, 右上のユニットについては, 左下の1辺1/4の正方形を取り去る. こうして得られた図形をG₁とする. 次に, 残った3個の, 欠陥のないユニットのそれぞれについて, 同様の操作を行なう. すなわち, それぞれを4個の1辺の長さ1/4のユニットに分け, 右上にユニットについては左下の1辺の長さ1/8の正方形を取り去る. 得られた図形G₂とする. 続いて, G₂に含まれる1辺の長さ1/4の, 欠陥のない各正方形ユニットについて, 同様の操作を行なう. 得られた図形をG₃とする. これを繰り返して得られる図形の列をG₁, G₂, G₃, ...とする.

目で見ると簡単だが, 欠陥のない正方形をどう判定するか.

私の考え方はこうだ.

各正方形を4区画に分け, 左下, 右下, 左上, 右上の順に下請けに渡すとする. G₀を描く手続きをaとすると, 1/2のサイズで, a,a,aと3回呼び, 最後に左下を取り除いた正方形を描く手続きbを呼ぶ.

aはnを1減らして, a,a,a,bと呼べば良い. bはnを1減らし, 左下を除いて, a,a,aと呼べば良い. そう考えて書いたのが, このプログラムだ. 上のプログラムが理解出来れば, こちらも分かるだろう.

/n 7 def
/l 540 def /l2 l 2 div def
/a {n 0 eq{0 0 moveto l 0 rlineto 0 l rlineto l neg 0 rlineto
 closepath fill}
 {/n n 1 sub def
 gsave
 0.5 dup scale
 gsave 0 0 translate a grestore
 gsave l 0 translate a grestore
 gsave 0 l translate a grestore
 gsave l l translate b grestore
 grestore
 /n n 1 add def} ifelse} def
/b {n 0 eq{
 l2 0 moveto l2 0 rlineto 0 l rlineto l neg 0 rlineto
 0 l2 neg rlineto l2 0 rlineto closepath fill}
 {/n n 1 sub def
 gsave 0.5 dup scale
 gsave l 0 translate a grestore
 gsave 0 l translate a grestore
 gsave l l translate a grestore
 grestore
 /n n 1 add def} ifelse} def
 40 40 translate a

この結果, n=7で描いたのが, 下の図である.



PostScripでこういう図を描くのは思ったより易しい.

太陽太陰暦

英語ではlunisolar calendarというらしいから, 日本語とは順が反対だが, 太陰太陽暦でもいいようだ.

要するに月齢に合わせて月を決めるが, ときどき閏月をおいて, 季節を合わせる. その規則はどこにでも見つけることができる.

• 新月の起きる日を, 新しい月の朔日(ついたち, 1日)とする.

• 24節気のうち, 太陽の黄経が30度の倍数になる中気に各月を対応させる. 中気の対応しない月を閏月とする.

昔の本を読むと, 春一月, 夏四月, 秋七月, 冬十月と書いてあるが, 旧暦では1, 2, 3月が春, 4, 5, 6月が夏, 7, 8, 9月が秋, 10, 11, 12月が冬である. その各月に中気が対応し, 中気のない月が閏と書いてあるから, 手元の天文年鑑を見ながら計算してみた.

新月と節気の日付と時刻を順に書いてみると,

新月 2月22日  7h35m       ---   a月1日(2月)
啓蟄 3月 5日 13h21m 345度
春分 3月20日 14h14m   0度
新月 3月22日 23h37m       ---   b月1日
清明 4月 4日 18h 6m  15度
穀雨 4月20日  1h12m  30度
新月 4月21日 16h18m       ---   c月1日
立夏 5月 5日 11h20m  45度
小満 5月21日  0h16m  60度
新月 5月21日  8h47m       ---   d月1日
芒種 6月 5日 15h26m  75度
新月 6月20日  0h 2m       ---   e月1日(5月)
夏至 6月21日  8h 9m  90度

aの月は春分があるから2月である. eの月は夏至があるから5月だ.




b,c,dが3月と4月とその閏月になる. bの月には黄経30度の穀雨があるから3月になる. cの月は小満があるから4月で, dの月には30度の倍数になる節気がないから, 閏4月だと思った.

ところが旧暦に関するウェブページを見てみると違うのである. 閏は4月21日からの3月の方であって, dの月が4月であった.

なぜかというと, 小満と5月の新月は, 小満の方が7時間半ほど早いが, 同じ日である. 新月が何時でも, その日の午前0時から5月になるのである. 従って小満はd月1日にあることになっているらしい.

天体の運行に基づくカレンダーはこういうところが微妙だ. 平朔とかカレンダー用のアルゴリズムをCalendrical Calculationsでもっと勉強する必要がある.

復活祭公式

前回のブログの最後の方の式, つまり補正した日数から対応する月を求める式

(define (month d) (quotient (+ (* 12 d) 373) 367))

の係数についてである.

前回のブログでは, 各月mの最初の日dを決める式を, 閏月を平均的に挿入し,

d=floor((7*(m+10))/12-6)+30*(m-1)
=floor((7m+70-72)/12)+(360m-360)/12
=floor((367m-362)/12)

のようにして求めた. これを使うと

m = 1 2  3  4  5   6   7   8   9   10  11  12
d = 0 31 61 92 122 153 183 214 245 275 306 336

が得られ, gregorianからfixへの変換に使えた. 今回は逆に与えられたdからmを計算したい. 前回の最後の表

d = 0-30 31-60 61-91 92-121 122-152 153-182 183-213 214-244
m = 1    2     3     4      5       6       7       8

d = 245-274 275-305 306-335 336-366
m = 9       10      11      12

を見ると,

0 ≤ d < 31ならm=1,
31 ≤ d < 61ならm=2,
...

としたい. mからdを決める式を代入すると,

floor((367*1-362)/12) ≤ d < floor((367*2-362)/12) ならm=1,
floor((367*2-362)/12) ≤ d < floor((367*3-362)/12) ならm=2,
...

なので,

floor((367m-362)/12) ≤ d < floor((367*(m+1)-362)/12)

の関係が分かる.

等号を右に移動して ≤d< から <d<≤ の形にするには, 両端の式から1を引くか中央の式に1を足す. また下の図で考えると



floor(f(m)) ≤ d < floor(f(m+1))はdのような, 下が閉区間, 上が開区間の範囲である. 従って, d+1は f(m) < d+1 ≤ f(m+1) となり, floorがいらなくなる.

(367m-362)/12 < d+1 ≤ (367*(m+1)-362)/12

367m-362 < (d+1)*12 ≤ 367*(m+1)-362

367m < (d+1)*12+362 ≤ 367*(m+1)

(m+1)=ceiling((12*(d+1)+362)/367)

m=ceiling((12*(d+1)+362)/367)-1

(12*(d+1)+362)/367-1

=(12*d+12+362-367)/367

=(12*d+7)/367

ceilingをfloorにしたいから, 分子に366を足すと

m=floor((12*d+7+366)/367)
=floor((12*d+373)/367)

で前回の式になった.

復活祭公式

復活祭(Easter)の日取りは, 春分かその後の最初の満月の後の日曜で決るから, このアルゴリズムに関心を持つ人は少なくない.

Knuth先生のThe Art of Computer Programming(TAOCP)にも演習問題として使われている. (TAOCP Vol.1,3rd Ed.,ex1.3.2-14, Fasc1.1,ex1.3.2'-32). 私も興味を持っていて, 数セミの1982年9月号に書いたりしたので, それを知った杉本敏夫さんや新井正夫さんが資料を送ってくださったことがある.

春分とか満月とか天体の運行に関連して日が決るように思えるが, 実は春分は3月21日に固定するとか, 年初の月齢を使うとか, アルゴリズムで決っているのである. とはいえ, TAOCPの演習問題でも分かるように, 結構面倒である.

先日, 以前頂いた資料をのんびりと見ていたら, Gaussの公式というのがあった. これは意外と簡単であった.

(define (easter20 y)
 (let* ((m 24) (n 5) (a (modulo y 19)) (b (modulo y 4))
   (c (modulo y 7)) (d (modulo (+ (* 19 a) m) 30))
   (e (modulo (+ (* 2 b) (* 4 c) (* 6 d) n) 7)))
  (if (> (+ d e) 9) (list 'april (+ d e -9))
   (list 'march (+ 22 d e)))))

という具合いに剰余しかとらない. let*の始めの方のmとnは世紀に依存する定数で, 2000年から2099年までは24と5である. そのため関数名に20をつけた. 杉本さんの資料に詳しい説明があるが, その話はまたいつかにして, 今回はReingoldとDershowitzのCalendrical Calculationsにある復活祭公式の話だ.

簡単にいえば, 計算法はKnuthのアルゴリズムと同様である. ただ計算の記述が本書では一風変っているので, その辺の話をしたい.

この本では, 日の計算に, fixed day number (fixed dateとかR.D.ともいう) の通日を使う. ユリウス日のようなものだが, Gregorian暦が過去まで使われたとして, その1年1月1日を第1日とするのである. その日は月曜なので, fixed dateを7で除した剰余が日曜を0とする曜日と重なって都合が良い,

Gregorian暦は400年毎に繰り返すから, 2001年1月のカレンダーをcal 1 2001で出力してみると

    January 2001
 S  M Tu  W Th  F  S
    1  2  3  4  5  6
 7  8  9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31

でGregorianの1年1月1日が月曜であることが確認出来る.

Calendrical Calculationのeasterのアルゴリズムはこうだ. Schemeに書き直してある.

(define (easter g-year)
 (let* ((century (+ (quotient g-year 100) 1))
   (shifted-epact (modulo (+ 14 (* 11 (modulo g-year 19))
     (- (quotient (* 3 century) 4))
     (quotient (+ 5 (* 8 century)) 25)) 30))
   (adjusted-epact
    (if
     (or (= shifted-epact 0)
      (and (= shifted-epact 1) (< 10 (modulo g-year 19))))
       (+ shifted-epact 1) shifted-epact))
   (paschal-moon (- (fixed-from-gregorian g-year april 19)
    adjusted-epact)))
  (kday-after paschal-moon sunday)))

最後の行から見ると, easterはpaschal-moon(春分満月)の後の日曜を探すようになっている. kdayというのは, kがsunやmonや...やsaturで, それらをまとめてkdayという. (k曜日ということだ.) つまり春分満月の後の日曜を求めるのだ.

その前のlet*の中は, century(世紀), epact(歳首月齢), paschal-moonなどを計算する. paschal-moonは(fixed-from-gregorian year month day)で, 引数の(Gregorian暦の)年月日のR.D.を計算し, adjusted-epactを引いたものが春分満月であり, その直後の日曜(のfixed date)を計算する.

2012年の復活祭を計算すると, 734601と得られる.

Gregorian暦からR.D.への変換は以下の通り. まず定数を定義する. (ここには今必要なものしか書かない.) 次にその年が閏年であるかみる関数gregorian-leap-year?. そして本体だ.

(define sunday 0) (define april 4)
(define january 1) (define march 3)
(define gregorian-epoch 1)

(define (gregorian-leap-year? g-year)
 (and (= (modulo g-year 4) 0)
  (not (member (modulo g-year 400) '(100 200 300)))))

(define (fixed-from-gregorian year month day)
 (+ gregorian-epoch -1 (* 365 (- year 1))
 (quotient (- year 1) 4)
 (- (quotient (- year 1) 100)) (quotient (- year 1) 400)
 (quotient (- (* 367 month) 362) 12)
 (cond ((<= month 2) 0)
       ((and (> month 2) (gregorian-leap-year? year)) -1)
       (else -2))
 day))

結構オーソドックスに書いてある. ここで面白いのは, 前月末日までの年内の総日数の計算である. 一応2月が30日あるとして計算する式を用意し, 3月以降を平年か閏年かで補正する.

(map (lambda (m) (quotient (- (* 367 m) 362) 12)) (a2b 1 13))

をやってみると次の上の段が得られる. 次の段は平年の正しい値で, 1,2月はよいが, 3月以降は平年は2, 閏年は1多いので, 補正項を計算する. この結構きわどい係数をどのように見つけたのか.

 (0 31 61 92 122 153 183 214 245 275 306 336)
 (0 31 59 90 120 151 181 212 243 373 304 334)
月1  2  3  4   5   6   7   8   9  10  11  12

Calendrical Calculationsにはごたごた書いてあるが, 要するにこう導出したらしい.

前述のように2月が30日あるとすると, 1年は367日. 12ヶ月に31日の閏月(大の月)を7回平均的に置くとすると, 次のような図が描ける.



これは勾配7/12の線のfloorをとったもので, 1段上がるときを閏月だと思って1年の月を当てはめると, 図のように大の月と小の月が対応する. すこし位相をずらして見ると

(map (lambda (m) (floor (- (* (/ 7. 12) (+ m 11)) 6))) (a2b 0 12))
=> (0. 1. 1. 2. 2. 3. 3. 4. 5. 5. 6. 6.)

が得られ, 上のリストの1桁目と一致する. これに毎月30日ずつ足せば, 前月までの日数dになるわけだ.

従って上の式のm=0のところを1月に対応させると,

d=floor((7*(m+10))/12-6)+30*(m-1)
=floor((7m+70-72)/12)+(360m-360)/12
=floor((367m-362)/12)

大の月が7, 8月, 12, 1月と並んでいるのも, 結構平均的であったと改めて気づく.

dateの後のk曜の計算は, kday-on-or-beforeを使う.

(define (kday-after date k)
 (kday-on-or-before (+ date 7) k))

(define (kday-on-or-before date k)
 (- date (day-of-week-from-fixed (- date k))))

(define (day-of-week-from-fixed date) (modulo date 7))

たとえば3月20日の前の水曜(=3)は20日から3を引いた日(17日)の曜日(木=4)を知り, 20日からその4を引いた16日が水曜という計算をする.

さて, 復活祭の日がR.D.で教えられても有難くないから, Gregorian暦に変換する. まずR.D.のある年を計算する.

(define (gregorian-year-from-fixed date)
 (let* ((d0 (- date gregorian-epoch))
  (n400 (quotient d0 146097)) (d1 (modulo d0 146097))
  (n100 (quotient d1 36524)) (d2 (modulo d1 36524))
  (n4 (quotient d2 1461)) (d3 (modulo d2 1461))
  (n1 (quotient d3 365))
  (year (+ (* 400 n400) (* 100 n100) (* 4 n4) n1)))
 (if (or (= n100 4) (= n1 4)) year (+ year 1))))

n400は400年のあった回数. d1は400年内の日数. n100は100年のあった回数. d2は100年内の日数. n4は4年の回数. d3は4年内での日数. n1は年の回数. するとdateの年は, yearのようになるが, 閏の調整を最後に行う.

年が判明すると, R.D.の年月日が計算できる.

(define (gregorian-from-fixed date)
 (let* ((year (gregorian-year-from-fixed date))
  (prior-days
   (- date (fixed-from-gregorian year january 1)))
  (correction
   (cond ((< date (fixed-from-gregorian year march 1)) 0)
    ((and (>= date (fixed-from-gregorian year march 1))
     (gregorian-leap-year? year)) 1)
    (else 2)))
  (month (quotient
   (+ (* 12 (+ prior-days correction)) 373) 367))
  (day (- date (fixed-from-gregorian year month 1) -1)))
 (list year month day)))

fixed-from-gregorianを何回も使うが, なんとかしたい.

ここでも年内の日数から月を見つける方法がこの本の独特な点である. correctionを別として, 年内日数dからmonthが得られる関数である. 係数が前の式と微妙に違うが, 似たように計算出来よう.

(define (month d) (quotient (+ (* 12 d) 373) 367))

でクリティカルなところを調べるとちゃんと計算出来ている.

0-30 31-60 61-91 92-121 122-152 153-182 183-213 214-244
1    2     3     4      5       6       7       8

245-274 275-305 306-335 336-366
9       10      11      12

やはり3月以降は正しい値と違うので, 補正を先にしてから計算に取り掛かる. 先ほどのR.D.の復活祭は

(gregorian-from-fixed 734601)=>(2012 4 8)

で4月8日と判明した.

再帰曲線

3次元のHilbert曲線. 前回で2次までは描けることが分かった. まぁしかし, 3次を描くとどうなりそうかにも興味があってやってみた. ご用とお急ぎの方のために, 先ず結果をお目にかけるとこのようになる.



中央少し下の赤い点が出発点, 一番上の緑の点が到着点である. 今回はこの絵の描き方を説明したい.

天下り的だが,

(define (z+y^ d x y z)
 (x+z^ (/ d 2) x y z) (y+z^ (/ d 2) (+ x d) y z)
 (y+z^ (/ d 2) (+ x d) (+ y d) z)
 (z+xv (/ d 2) x (+ y d) z) (z+xv (/ d 2) x (+ y d) (+ z d))
 (y-zv (/ d 2) (+ x d) (+ y d) (+ z d))
 (y-zv (/ d 2) (+ x d) y (+ z d)) (x-zv (/ d 2) x y (+ z d)))

は1辺の長さdのz+y^をx,y,zを起点にして描く起動関数である. 描くといっても, 下請け関数が節点の座標を出力するだけで, 実際に描くのはPostScriptにまかせる.

この関数は下請けを8回呼ぶ. 最初のx+z^の場合は, 下請けの起点は貰ってきたx,y,zである. 次のy+z^の場合は, xを(+ x d), つまりxの位置をdだけずらす. z+y^のGrayコードが000, 001, 011,...と始まったのを反映している. だからその次はyも(+ y d)として呼ぶ. このようにして8回呼ぶと終わる.

その下請けは, やはりそれぞれのGaryコードに基づき,

(define (x+z^ d x y z)
 (p x y z) (p x (+ y d) z) (p x (+ y d) (+ z d)) 
 (p x y (+ z d)) (p (+ x d) y (+ z d))
 (p (+ x d) (+ y d) (+ z d)) (p (+ x d) (+ y d) z)
 (p (+ x d) y z))

(define (y+z^ d x y z)
 (p x y z) (p (+ x d) y z) (p (+ x d) y (+ z d))
 (p x y (+ z d)) (p x (+ y d) (+ z d))
 (p (+ x d) (+ y d) (+ z d))
 (p (+ x d) (+ y d) z) (p x (+ y d) z))
...

のようにして, x+z^, y+z^, z+xv, y-zv, x-zvの5個用意する. (p x y z)は(display (list x y z))である. 座標の8個出力後の改行もpの担当である. (z+y^ 2 0 0 0)と起動関数を呼ぶと, 64個の座標

(0 0 0)(0 1 0)(0 1 1)(0 0 1)(1 0 1)(1 1 1)(1 1 0)(1 0 0)
(2 0 0)(3 0 0)(3 0 1)(2 0 1)(2 1 1)(3 1 1)(3 1 0)(2 1 0)
(2 2 0)(3 2 0)(3 2 1)(2 2 1)(2 3 1)(3 3 1)(3 3 0)(2 3 0)
(1 3 0)(1 2 0)(0 2 0)(0 3 0)(0 3 1)(0 2 1)(1 2 1)(1 3 1)
(1 3 2)(1 2 2)(0 2 2)(0 3 2)(0 3 3)(0 2 3)(1 2 3)(1 3 3)
(2 3 3)(3 3 3)(3 3 2)(2 3 2)(2 2 2)(3 2 2)(3 2 3)(2 2 3)
(2 1 3)(3 1 3)(3 1 2)(2 1 2)(2 0 2)(3 0 2)(3 0 3)(2 0 3)
(1 0 3)(1 1 3)(1 1 2)(1 0 2)(0 0 2)(0 1 2)(0 1 3)(0 0 3)

が得られ, この座標に適当な倍率を掛けて, PostScriptで描くと


この絵は2次だが, さて, 3次まで描くには, 上にあった起動の関数と下請け関数を統合し,

x+y^ x+yv x+z^ x+zv x-y^ x-yv x-z^ x-zv
y+z^ y+zv y+x^ y+xv y-z^ y-zv y-x^ y-xv
z+x^ z+xv z+y^ z+yv z-x^ z-xv z-y^ z-yv

の24個について関数を書く必要がある. もちろん1個ずつ手書きするわけにはいかない. 当然関数発生関数を書くことになる. それを使い,

(3dgen 2 0 1 0) =>
(define (z+y^ d x y z) (if (= d 1) (begin (p x y z)
(p (+ x d) y z) (p (+ x d) (+ y d) z) (p x (+ y d) z)
(p x (+ y d) (+ z d)) (p (+ x d) (+ y d) (+ z d))
(p (+ x d) y (+ z d)) (p x y (+ z d)))
(begin (x+z^ (/ d 2) x y z) (y+z^ (/ d 2) (+ x d) y z)
(y+z^ (/ d 2) (+ x d) (+ y d) z) (z+xv (/ d 2) x (+ y d) z)
(z+xv (/ d 2) x (+ y d) (+ z d))
(y-zv (/ d 2) (+ x d) (+ y d) (+ z d))
(y-zv (/ d 2) (+ x d) y (+ z d)) (x-zv (/ d 2) x y (+ z d)))))

のような関数を24個揃える. そして(z+y^ 4 0 0 0)と起動すると, 512個の座標

(0 0 0)(0 0 1)(1 0 1)(1 0 0)(1 1 0)(1 1 1)(0 1 1)(0 1 0)
(0 2 0)(0 3 0)(1 3 0)(1 2 0)(1 2 1)(1 3 1)(0 3 1)(0 2 1)
(0 2 2)(0 3 2)(1 3 2)(1 2 2)(1 2 3)(1 3 3)(0 3 3)(0 2 3)
(0 1 3)(0 1 2)(0 0 2)(0 0 3)(1 0 3)(1 0 2)(1 1 2)(1 1 3)
(2 1 3)(2 1 2)(2 0 2)(2 0 3)(3 0 3)(3 0 2)(3 1 2)(3 1 3)
(3 2 3)(3 3 3)(2 3 3)(2 2 3)(2 2 2)(2 3 2)(3 3 2)(3 2 2)
(3 2 1)(3 3 1)(2 3 1)(2 2 1)(2 2 0)(2 3 0)(3 3 0)(3 2 0)
(3 1 0)(3 1 1)(2 1 1)(2 1 0)(2 0 0)(2 0 1)(3 0 1)(3 0 0)

(4 0 0)(4 0 1)(4 1 1)(4 1 0)(5 1 0)(5 1 1)(5 0 1)(5 0 0)
(6 0 0)(7 0 0)(7 1 0)(6 1 0)(6 1 1)(7 1 1)(7 0 1)(6 0 1)
(6 0 2)(7 0 2)(7 1 2)(6 1 2)(6 1 3)(7 1 3)(7 0 3)(6 0 3)
(5 0 3)(5 0 2)(4 0 2)(4 0 3)(4 1 3)(4 1 2)(5 1 2)(5 1 3)
(5 2 3)(5 2 2)(4 2 2)(4 2 3)(4 3 3)(4 3 2)(5 3 2)(5 3 3)
(6 3 3)(7 3 3)(7 2 3)(6 2 3)(6 2 2)(7 2 2)(7 3 2)(6 3 2)
(6 3 1)(7 3 1)(7 2 1)(6 2 1)(6 2 0)(7 2 0)(7 3 0)(6 3 0)
(5 3 0)(5 3 1)(5 2 1)(5 2 0)(4 2 0)(4 2 1)(4 3 1)(4 3 0)

(4 4 0)(4 4 1)(4 5 1)(4 5 0)(5 5 0)(5 5 1)(5 4 1)(5 4 0)
(6 4 0)(7 4 0)(7 5 0)(6 5 0)(6 5 1)(7 5 1)(7 4 1)(6 4 1)
(6 4 2)(7 4 2)(7 5 2)(6 5 2)(6 5 3)(7 5 3)(7 4 3)(6 4 3)
(5 4 3)(5 4 2)(4 4 2)(4 4 3)(4 5 3)(4 5 2)(5 5 2)(5 5 3)
(5 6 3)(5 6 2)(4 6 2)(4 6 3)(4 7 3)(4 7 2)(5 7 2)(5 7 3)
(6 7 3)(7 7 3)(7 6 3)(6 6 3)(6 6 2)(7 6 2)(7 7 2)(6 7 2)
(6 7 1)(7 7 1)(7 6 1)(6 6 1)(6 6 0)(7 6 0)(7 7 0)(6 7 0)
(5 7 0)(5 7 1)(5 6 1)(5 6 0)(4 6 0)(4 6 1)(4 7 1)(4 7 0)

(3 7 0)(2 7 0)(2 7 1)(3 7 1)(3 6 1)(2 6 1)(2 6 0)(3 6 0)
(3 5 0)(3 4 0)(3 4 1)(3 5 1)(2 5 1)(2 4 1)(2 4 0)(2 5 0)
(1 5 0)(1 4 0)(1 4 1)(1 5 1)(0 5 1)(0 4 1)(0 4 0)(0 5 0)
(0 6 0)(1 6 0)(1 7 0)(0 7 0)(0 7 1)(1 7 1)(1 6 1)(0 6 1)
(0 6 2)(1 6 2)(1 7 2)(0 7 2)(0 7 3)(1 7 3)(1 6 3)(0 6 3)
(0 5 3)(0 4 3)(0 4 2)(0 5 2)(1 5 2)(1 4 2)(1 4 3)(1 5 3)
(2 5 3)(2 4 3)(2 4 2)(2 5 2)(3 5 2)(3 4 2)(3 4 3)(3 5 3)
(3 6 3)(2 6 3)(2 6 2)(3 6 2)(3 7 2)(2 7 2)(2 7 3)(3 7 3)

(3 7 4)(2 7 4)(2 7 5)(3 7 5)(3 6 5)(2 6 5)(2 6 4)(3 6 4)
(3 5 4)(3 4 4)(3 4 5)(3 5 5)(2 5 5)(2 4 5)(2 4 4)(2 5 4)
(1 5 4)(1 4 4)(1 4 5)(1 5 5)(0 5 5)(0 4 5)(0 4 4)(0 5 4)
(0 6 4)(1 6 4)(1 7 4)(0 7 4)(0 7 5)(1 7 5)(1 6 5)(0 6 5)
(0 6 6)(1 6 6)(1 7 6)(0 7 6)(0 7 7)(1 7 7)(1 6 7)(0 6 7)
(0 5 7)(0 4 7)(0 4 6)(0 5 6)(1 5 6)(1 4 6)(1 4 7)(1 5 7)
(2 5 7)(2 4 7)(2 4 6)(2 5 6)(3 5 6)(3 4 6)(3 4 7)(3 5 7)
(3 6 7)(2 6 7)(2 6 6)(3 6 6)(3 7 6)(2 7 6)(2 7 7)(3 7 7)

(4 7 7)(4 7 6)(4 6 6)(4 6 7)(5 6 7)(5 6 6)(5 7 6)(5 7 7)
(6 7 7)(7 7 7)(7 6 7)(6 6 7)(6 6 6)(7 6 6)(7 7 6)(6 7 6)
(6 7 5)(7 7 5)(7 6 5)(6 6 5)(6 6 4)(7 6 4)(7 7 4)(6 7 4)
(5 7 4)(5 7 5)(4 7 5)(4 7 4)(4 6 4)(4 6 5)(5 6 5)(5 6 4)
(5 5 4)(5 5 5)(4 5 5)(4 5 4)(4 4 4)(4 4 5)(5 4 5)(5 4 4)
(6 4 4)(7 4 4)(7 5 4)(6 5 4)(6 5 5)(7 5 5)(7 4 5)(6 4 5)
(6 4 6)(7 4 6)(7 5 6)(6 5 6)(6 5 7)(7 5 7)(7 4 7)(6 4 7)
(5 4 7)(5 4 6)(5 5 6)(5 5 7)(4 5 7)(4 5 6)(4 4 6)(4 4 7)

(4 3 7)(4 3 6)(4 2 6)(4 2 7)(5 2 7)(5 2 6)(5 3 6)(5 3 7)
(6 3 7)(7 3 7)(7 2 7)(6 2 7)(6 2 6)(7 2 6)(7 3 6)(6 3 6)
(6 3 5)(7 3 5)(7 2 5)(6 2 5)(6 2 4)(7 2 4)(7 3 4)(6 3 4)
(5 3 4)(5 3 5)(4 3 5)(4 3 4)(4 2 4)(4 2 5)(5 2 5)(5 2 4)
(5 1 4)(5 1 5)(4 1 5)(4 1 4)(4 0 4)(4 0 5)(5 0 5)(5 0 4)
(6 0 4)(7 0 4)(7 1 4)(6 1 4)(6 1 5)(7 1 5)(7 0 5)(6 0 5)
(6 0 6)(7 0 6)(7 1 6)(6 1 6)(6 1 7)(7 1 7)(7 0 7)(6 0 7)
(5 0 7)(5 0 6)(5 1 6)(5 1 7)(4 1 7)(4 1 6)(4 0 6)(4 0 7)

(3 0 7)(3 0 6)(2 0 6)(2 0 7)(2 1 7)(2 1 6)(3 1 6)(3 1 7)
(3 2 7)(3 3 7)(2 3 7)(2 2 7)(2 2 6)(2 3 6)(3 3 6)(3 2 6)
(3 2 5)(3 3 5)(2 3 5)(2 2 5)(2 2 4)(2 3 4)(3 3 4)(3 2 4)
(3 1 4)(3 1 5)(3 0 5)(3 0 4)(2 0 4)(2 0 5)(2 1 5)(2 1 4)
(1 1 4)(1 1 5)(1 0 5)(1 0 4)(0 0 4)(0 0 5)(0 1 5)(0 1 4)
(0 2 4)(0 3 4)(1 3 4)(1 2 4)(1 2 5)(1 3 5)(0 3 5)(0 2 5)
(0 2 6)(0 3 6)(1 3 6)(1 2 6)(1 2 7)(1 3 7)(0 3 7)(0 2 7)
(0 1 7)(0 1 6)(1 1 6)(1 1 7)(1 0 7)(1 0 6)(0 0 6)(0 0 7)

が得られ, 始めの図が描けることになった. 折角描いてはみたが, 期待したほどには美しくなかったのが残念だ.

私がHilbert曲線の話を書いたのは2009年6月19日のブログであった. そこの図で分かるように, 2次元の曲線では, 1次の曲線が縦向きに出発するなら, 2次は横向き, 3次はまた縦向き,...のように交互に出発する.

今回, 3次元のHilbert曲線を3次まで描いて分かったのは, 前回のブログの最初の図で, 赤線の1次の曲線が0からx軸方向へ出発し, 2次が0からy軸方向へ出発したのに対し, 今回の図では, 赤点から予想通りz方向へ出発していることだ. そういうものだったのだ.

上の64行にわたる512の座標は, 8行ずつ8つのブロックにして書いてある. ブロックを上から順に0,1,2,...,7ということにすると, ブロック0の座標はxもyもzも0から3である.つまり原点に近い1/8の空間を占めている. ブロック1はxが4から7なので, x方向だけが4ずれた空間にある. 最後のブロック7はzが4から7で, z方向へずれた空間にあるわけだ.

ブロック0をもう一度書いてみる.

(0 0 0)(0 0 1)(1 0 1)(1 0 0)(1 1 0)(1 1 1)(0 1 1)(0 1 0)
(0 2 0)(0 3 0)(1 3 0)(1 2 0)(1 2 1)(1 3 1)(0 3 1)(0 2 1)
(0 2 2)(0 3 2)(1 3 2)(1 2 2)(1 2 3)(1 3 3)(0 3 3)(0 2 3)
(0 1 3)(0 1 2)(0 0 2)(0 0 3)(1 0 3)(1 0 2)(1 1 2)(1 1 3)
(2 1 3)(2 1 2)(2 0 2)(2 0 3)(3 0 3)(3 0 2)(3 1 2)(3 1 3)
(3 2 3)(3 3 3)(2 3 3)(2 2 3)(2 2 2)(2 3 2)(3 3 2)(3 2 2)
(3 2 1)(3 3 1)(2 3 1)(2 2 1)(2 2 0)(2 3 0)(3 3 0)(3 2 0)
(3 1 0)(3 1 1)(2 1 1)(2 1 0)(2 0 0)(2 0 1)(3 0 1)(3 0 0)

赤く書いてあるのは, すべての座標が2で割り切れるもので, 各行の1つずる現れる. 各行が1つのGrayコードになっていて, その原点に近いものがそれである. 下の図の8つの赤点に対応する.

それを2で割ると

(0 0 0)(0 1 0)(0 1 1)(0 0 1)(1 0 1)(1 1 1)(1 1 0)(1 0 0)

となり, 2次の64個の座標の1行目と同じになるが, 当たり前だ.

再帰曲線

今回は3次元のHilbert曲線が話題である. この2月は思わぬ風邪引きで, それも歳をとったせいか, 全治に時間がかかった.

それで家に引き籠もっている折, 例の「ハッカーのたのしみ」を眺めていたら, 3次元Hilbert曲線の基本部品という図を見つけた. 確かに3次元でも出来そうであるが, さてどうやったら描けるのか. しばらくそれが気になっていた.

2次元だと, 右折, 左折などを繰り返すと何となくアルゴリズムが見つかるが, 3次元の場合, これをどういえばよいか. 試行錯誤の結果, 基本部品に名前をつけ, それを組合せると描けそうだというところまで来た. もっともまだ最後まで出来たわけではなく, 今後挫折するかもしれないのだが.

とりあえず, 1次と2次の図を描いてみたのが下だ.



赤の太い線が1次, 黒の細いのが2次である. 通過した順が分かるように, 節点に0から番号を付けてある. 1次のは向こうの下の方0から始まる. この座標を000としよう. それから図で左下へ進む. この方向をxとする. つまり次の点1の座標はzyxの順に書けば001である. 今度は右下へ進む. この方向をyとする. 次の点2の座標は011だ. この伝でいくと, 010, 110, 111, 101, 100のように進むことになる.

もう1度揃えて書くと

zyx
000
001
011
010
110
111
101
100

これは誰が見てもGrayコードである.

ところで, 2次を見ると, 1次の0の回りを0→1→...→7と同様にGrayコードで進む8点で囲む. 1の回りを8→9→...→15の8点で囲む. ... 7の回りを56→57→...→63の8点で囲む. この8点の形はよく見ると5種類ある. つまり1と2(B), 3と4(C), 5と6(D)の回りの8点はそれぞれ同じで, その他に0(A)と7(E)で5種類である. Grayコードの部品がたくさんあるが, 全体がGrayコードになっているのではない.

A    B    C    D    E
zyx  zyx  zyx  zyx  zyx
000  000  011  110  101
010  001  001  111  111
110  101  000  011  011
100  100  010  010  001
101  110  110  000  000
111  111  100  001  010
011  011  101  101  110
001  010  111  100  100
x+z^ y+z^ z+xv y-zv x-zv

さてこれに分かりやすい名前を付けたい. Aを見ると最上段と最下段ではxが0から1と増えている. zは0から1になり0に戻る. yはふらふらして元に戻るから無視すると, xは増え(x+)zは010(^)の凸型ということで, x+z^と呼ぶことにする. 他のBからEも同じ要領で命名してある. 上にあった1次の形は, この方式でいうとz+y^である.

そのそれぞれを描くと次のようになる. 左上は1次の形である.



この1次の形z+y^は2次で描くとA, B, B, C, C, D, D, Eで出来ていたのだ. つまり

z+y^ = x+z^ 2(y+z^) 2(z+xv) 2(y-zv) x-zv.
        A      B       C       D     E

x座標はAで増え, Cで2回減増し, Eで減るから変化なし.
y座標はBで増え, Dで減るからy^である.
z座標はAで増減し, Cで増え, Eで減増するからz+である. 全体でz+y^となるわけだ.

2次のA, B, C, D, Eがこのように分解出来るなら, 3次も描けることになる.



分解を上の図を見ながらもう一度考えてみよう.

最初の+か-を伴う座標を主軸といおう. 次の^かvの座標を副軸といおう. 最後に名称に出てこないのを従軸といおう.

• 3と4は主軸の+, -により+か-になる. +の場合, 0,1,2では主軸は^, 5,6,7ではvになり, -なら逆になる.

• 副軸は^なら1と2で+, 5と6で-, vなら逆になる.

• 従軸の初期値は, 主軸と副軸の初期値と偶数パリティになるようにとる. それが0なら0で+, 3と4でv, 7で+. 1なら逆になる.

さっそく挑戦してみる.

x+z^ = y+x^ 2(z+x^) 2(x+yv) 2(z-xv) y-xv.

そう分かるとプログラムが書ける.

(define (xyz a) (list-ref '(x y z) a))
(define (+- b) (list-ref '(+ -) b))
(define (ud b) (list-ref '(^ v) b))

(define (bar a0 b0 a1 b1)
 (let ((a2 (- 3 a0 a1)) (b2 (modulo (+ b0 b1) 2)))
  (list
   (list (xyz a0) (+- b0) (xyz a1) (ud b1))
   (list (xyz a2) (+- b2) (xyz a0) (ud b0));0
   (list (xyz a1) (+- b1) (xyz a0) (ud b0));1,2
   (list (xyz a0) (+- b0) (xyz a2) (ud (- 1 b2)));3,4
   (list (xyz a1) (+- (- 1 b1)) (xyz a0) (ud (- 1 b0)));5,6
   (list (xyz a2) (+- (- 1 b2)) (xyz a0) (ud (- 1 b0))))));7

(z + y ^)は(bar 2 0 1 0)と入力する. すると

(bar 2 0 1 0) =>
((z + y ^) (x + z ^) (y + z ^) (z + x v) (y - z v) (x - z v))

と得られる. リストの先頭は入力パターンである. 従って上の図と同じになる.

Aを分解すると,

(bar 0 0 2 0) =>
((x + z ^) (y + x ^) (z + x ^) (x + y v) (z - x v) (y - x v))

一方, Grayコードを得るには次のプログラムでよい.

(define (foo a0 b0 a1 b1)
 (let ((b '()) (a (list 0 0 0)) (a2 (- 3 a0 a1))
  (b2 (modulo (+ b0 b1) 2)))
  (list-set! a a0 b0) (list-set! a a1 b1) (list-set! a a2 b2)
  (set! b (cons (reverse a) b))
  (list-set! a a2 (- 1 (list-ref a a2)))
  (set! b (cons (reverse a) b))
  (list-set! a a1 (- 1 (list-ref a a1)))
  (set! b (cons (reverse a) b))
  (list-set! a a2 (- 1 (list-ref a a2)))
  (set! b (cons (reverse a) b))
  (list-set! a a0 (- 1 (list-ref a a0)))
  (set! b (cons (reverse a) b))
  (list-set! a a2 (- 1 (list-ref a a2)))
  (set! b (cons (reverse a) b))
  (list-set! a a1 (- 1 (list-ref a a1)))
  (set! b (cons (reverse a) b))
  (list-set! a a2 (- 1 (list-ref a a2)))
  (set! b (cons (reverse a) b))
  (reverse b)))

初期値を設定してから, 従軸, 副軸, 従軸, 主軸, 従軸, 副軸, 従軸の順に1と0を交換する. "z+y^"は(foo 2 0 1 0)と入力する.

(foo 2 0 1 0) =>
((0 0 0)(0 0 1)(0 1 1)(0 1 0)(1 1 0)(1 1 1)(1 0 1)(1 0 0))

と得られる.

Aを１次とみて, その2次の絵を描いてみると,

なんだかうまく行っているらしい. 春から縁起がいいわ.

素因数探し

前回の素因数探しのブログ(1月23日)に「Edlerの作ったカードのセットはどこかに残っていないかしら」と書いた後, 探したら, factor stencilの画像はインターネットに存在した. 駄目元で探してみるものだ.

これ, 紙のカード?と思うが, その画像をコピーさせて頂く.





2004年にWashington D.C.のSmithsonian National Museum of American Historyの展示で撮影されたらしい.

1枚目の写真は, カードというよりは鳩サブレーのような厚みが感じられる. 2枚目のには文字がプリントしてあるが, それが読めないのが残念.


さて一方, 田中君と試作しようとしたstencil cardには, 2月3日に鎌倉のFabLabで再度挑戦した.

今回はこういう図を用意した.

これはR=2のプリントパターンである.



つぎはR=-1のカット用パターンだ.



今回試作するR=-1と2について, それぞれプリントパターンをカット用パターンを作った. とはいってもプリントパターンは, カード左上の見出しの数値だけが違う.

それぞれのパターンの四隅にある鉤の手は, 位置合わせのトンボだ.

まず多少厚手の白紙の中央に, プリントパターンを印刷する. 見出しの数値が2つあるのは, 内側のが完成したカードに残るもの, 外側がカット用パターンとの対を示す, 操作に安全を期すためのものである.

パターンを印刷した紙を, カッターマットに両面テープで張り付ける. しっかり止めないと, 精密な作業は出来ない. この結果, craftroboのカッターの刃先はマットにまで食い込むのである. また, 紙の端からトンボまで距離などを一応計測し, カットのソフトウェアに教える. そしてマシンをスタート.

craftroboはセンサーでトンボを位置を読み取り, 続いてカードの孔を切り始める. 孔が小さいから目にも止らぬ速さだ. ただ, どういう順にカットしているのか不思議である. 端から順に行くかと思うとそうでもない. そうこうしているうちに孔を切り終わり, 周囲を一周して終了する. この間約10分であった.

やってみると, カット圧力の調整が微妙なことが判明した. すなわち, 圧力が強いと孔から浮いたチップがカード上に散らばり, カッターの移動を妨害するのである. 従って, カットはするが, 紙片がはずれぬ程度の強さにしなければならぬ. そして, カッターが停止してから, ピンセットで孔を押し, 孔を開けることになる.

また反対に圧力が弱いと, 孔を手で押し開ける時に, きれいに切れないことになる. という次第で, 微妙であった.

また, トンボがあるにもかかわらず, カットした孔が, プリントした数字にきちんと重ならず, すこしずれ気味であったり, この辺の調整は難しいという経験をした.

カッターマットから外した紙からカードの形を抜き取り, カードの裏側(数字の印刷してない側)から, 孔を押し開ける. カードに約400個所の孔があるから, これも一仕事であった. (もちろん自宅へ戻ってからの仕事)

やはり, 計算機に接続されているIBMカードパンチを探さなければ.

完成したものは, 以下のとおり.





2月6日からローマで開催されたIFIP WG2.1の会合で, こんなもの作ったと見せたら, やんやの喝采を受けた. この作業では, SFCの田中浩也君に大変お世話になった. ありがとう.