高橋先生

堀口大学の詩に

「待つ間の長さ 会う間の短さ 時のおなかは蛇腹です」

のようなのがあったと思う.

今日は6月30日 茅の輪くぐりの日だ.

ことしは月曜だが, 1985年と2002年の6月30日はともに日曜であった.

1985年6月30日は高橋秀俊先生が, 2002年6月30日は高橋延匡先生が他界され, 私にとっては忘れられぬ日だ.

どちらもつい先日のようだが, それからそれぞれ23年と6年が経った.

高橋秀俊先生は1985年1月末に体調をくづされ, 入院生活を送られた. 始めの頃はこの病室からは電車がよく見えてということだったが, 段々と重体になられ, 亡くなる前日, 私を病院に呼ばれた. 小さい声でいろいろ話された. 翌日夕方, 逝去されたと電話を受け, 雨の中, 病院に向かった.

その辺のことは, コンピュータソフトウェアの2巻4号に書いた.

高橋延匡先生の方は急であった. 3月の情報処理学会の全国大会でお目にかかったと記憶するが, あっという間のご逝去であった. HITAC5020やアクレディテーションの活動など, 一緒だったので, 残念なことであった.

ちょうど学会誌の編集長だったので, 会誌にこう書いた.

元副会長 拓殖大学教授 高橋延匡先生, 二豎膏肓に入って療養ご専念中とかねてより聞き及びおりしところ, 紫陽花雨に打たるる6月30日, 不帰の客となられる. 無念千万. 翌7月1日は満69歳の誕生日のはずであった. OSの開発に, 情報の教育に, またアクレディテーションの準備にと終始真摯に立ち向かわれた先生のお姿は永く語り継がれよう.

今日は梅雨の晴れ間, 今年の紫陽花はすでに色あせているが, 毎年6月30日になると, 故人を偲ぶことにしている.

夏至の日に

今年の夏至ももう過ぎた.2至2分の中では私の一番好きな日だ. (2至2分 = 夏至, 冬至, 春分, 秋分 これらの英語は難しい. summer solstice, winter solstice, vernal equinox, autumnal equinox) 今の家では, 6月になるとどこからか郭公が来て, 近くの高い木やアンテナの上で鳴く. この2年くらい郭公を聞かなかったが, 今年は何日か鳴き声が聞けた. 「藤の花咲けども鳴かぬほととぎす雲のいずこに迷いけるらむ」を思い出す季節でもある.

6月12日の朝日新聞の夕刊に, 昭和基地で撮影した「幻の日の出」なる写真が出ていた. 南極は白夜と反対で極夜の最中だが, 地平線の直ぐ下にいる筈の太陽が蜃気楼で地上に見えたという図である. 地平線の下ですれすれだとそういうことも十分ありうる.

遥か昔「南極のスコット」という映画を見た. Scott隊が南極からの帰途, 全員遭難した話である. (http://en.wikipedia.org/wiki/Robert_Falcon_Scott) その後極夜になり, 冬至が近づいて再び太陽が戻り, 捜索隊によって遭難の様子が判明する話だ. アナウンスでは「太陽が戻ってきた」といったと記憶するが字幕には「夏が来た」とあった.

北半球の夏は南半球の冬だというのか, 南半球の冬は暑く, 夏は寒いというのか浅学にして知らない. (私は後者の説を支持する.)

夏至は24節気の1つ. 森口繁一先生の「数理つれづれ」に24節気間の時間の図がある. 先生が描かれた方法は分からぬが, 同じようなものを描いてみた. 本年の24節気の月日時分を天文年鑑から取り込んだのが以下のデータである.

( 0 22 15  8 '冬至) ( 1  6  8 25 '小寒) ( 1 21  1 44 '大寒)
( 2  4 20  0 '立春) ( 2 19 15 50 '雨水) ( 3  5 13 59‘啓蟄) 
( 3 20 14 48 '春分) ( 4  4 18 46 '清明) ( 4 20  1 51 '穀雨)  
( 5  5 12  3 '立夏) ( 5 21  1  1 '小満) ( 6  5 16 12 '芒種)
( 6 21  8 59 '夏至) ( 7  7  2 27 '小暑) ( 7 22 19 55 '大暑)
( 8  7 12 16 '立夏) ( 8 23  3  2 '処暑) ( 9  7 15 14 '白露)  
( 9 23  0 45 '秋分) (10  8  6 57 '寒露) (10 23 10  9 '霜降) 
(11  7 10 11 '立冬) (11 22  7 44 '小雪) (12  7  3  2 '大雪)
(12 21 21  4 '冬至)

これをユリウス日を計算するプログラムに入れ, 差を取ると(単位は日)

14.720139 14.721527 14.761112 14.826389 14.922916 15.034028
15.165278 15.295138 15.425001 15.540277 15.632639 15.699306
15.727778 15.727777 15.681251 15.615277 15.508334 15.396528
15.258333 15.133333 15.001388 14.897917 14.804167 14.751389

となり, これをpostscriptで図にする.




地球の軌道が真円でないので, 太陽が(地球が)黄道上を移動する時間が変わるからだ. ところで夏至では昼間の時間が一番長いが, 日出, 日入が一番早く,　また遅いのは夏至の日ではない. この説明は情報処理学会誌45巻3月号の編集系独白に書いたので, 読まれた方もあろう.

天文時計の鐘

N.J.A.Sloaneの書いたMy Favorite Integer Sequencesという記事を見つけた. 面白いことがいろいろある中で, あ!と思ったのは

1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, 43212, 34321, 23432, 123432, 1234321, 2343212, 3432123, 4321234, 32123432, 123432123, 43212343, 2123432123, 432123432, 1, 2, 3, 4, 32, 123,

の数列であった.

説明によると, これはプラハの天文時計(astronomical clock)の鐘の鳴り方だそうだ.

数列の先頭からこのように, 1時には1; 2時には2,...,と鳴り, 正子(0時)には24時として432123432と鳴って, 1時には再び1と鳴る.

この数列の特徴は,

a) n 時に鳴る数列の和はちょうど n になる.

b) カンマを外してみると, 数列は基本パターン"123432"の繰り返しである.

ということだ.

1,2,3,4と書いてあるが, 鐘は1つで, KnuthのTAOCP, v4f2, 7.2.1.2にあるCambridge Forty-Eightのような, 4つの鐘をある順列で鳴らすのではない.

1は1回, 2は2回鳴り, 5時の32はまず3回鳴り, 次に2回鳴る. それを足しながら数えれば時刻が分かる仕掛けだ.しかし24まで間違えずに数えるには, 忍耐もいるであろう.

なぜこういうことが出来るか.

実は, この不思議な数列は24まで続くだけでなく, どこまでも作れる. 計算機が手元にあれば, お茶の子だ.

(1 (1))
(2 (2))
(3 (3))
(4 (4))
(5 (3 2))
(6 (1 2 3))
(7 (4 3))
(8 (2 1 2 3))
(9 (4 3 2))
(10 (1 2 3 4))
(11 (3 2 1 2 3))
(12 (4 3 2 1 2))
(13 (3 4 3 2 1))
(14 (2 3 4 3 2))
(15 (1 2 3 4 3 2))
(16 (1 2 3 4 3 2 1))
(17 (2 3 4 3 2 1 2))
(18 (3 4 3 2 1 2 3))
(19 (4 3 2 1 2 3 4))
(20 (3 2 1 2 3 4 3 2))
(21 (1 2 3 4 3 2 1 2 3))
(22 (4 3 2 1 2 3 4 3))
(23 (2 1 2 3 4 3 2 1 2 3))
(24 (4 3 2 1 2 3 4 3 2))
(25 (1 2 3 4 3 2 1 2 3 4))
(26 (3 2 1 2 3 4 3 2 1 2 3))
(27 (4 3 2 1 2 3 4 3 2 1 2))
(28 (3 4 3 2 1 2 3 4 3 2 1))
(29 (2 3 4 3 2 1 2 3 4 3 2))
(30 (1 2 3 4 3 2 1 2 3 4 3 2))

そこでどこかに繰り返しパターンがないかと, 図を描いてみた. すると1から15までのパターンと16から30までのパターンが殆んど同じになる. 16からは基本パターン1,2,3,4,3,2を1サイクル余計に持っているだけである. 従って31からも同じになると判明した.



10,11,12,13,14はそれぞれ15のcomplementの5,4,3,2,1と相補のパターンだし, 6と9, 7と8も相補パターンなことが分かる.

24がちょうどパターンの最後で終るのも幸いしている. 1から24までの和が300で基本パターンの和15の倍数なので, 当然だが.

1,2の繰り返しでも同様なことが出来ることが判明した.

(1 (1))
(2 (2))
(3 (1 2))
(4 (1 2 1))
(5 (2 1 2))
(6 (1 2 1 2))
(7 (1 2 1 2 1))
(8 (2 1 2 1 2))
(9 (1 2 1 2 1 2))
(10 (1 2 1 2 1 2 1))
(11 (2 1 2 1 2 1 2))
(12 (1 2 1 2 1 2 1 2))
(13 (1 2 1 2 1 2 1 2 1))
(14 (2 1 2 1 2 1 2 1 2))
(15 (1 2 1 2 1 2 1 2 1 2))

しかし, 1,2,3,4,3,2ほど劇的ではない.

火星

火星探査機がパラシュートで降下するのを, 他の火星周回衛星から撮影したニュースには驚いた.

いかにも画面を眺めて, 今だ! とシャッターを切ったかのようなシーンだが,　そんなことは可能だろうか.

火星は昨年12月に衝の位置(火星, 地球, 太陽の順に並ぶ)にあり, 地球, 火星間の距離は0.6天文単位, 今年12月に合の位置(地球, 太陽, 火星の順に並ぶ)になり, 2.6天文単位だ.　今はその中間で, 多分2天文単位くらいであろう. 1天文単位は光で8分ちょっとの時間なので, そう考えると画面を眺めて地上から制御するのはまったく無理と分かる.

NASAのページを見ると, やはりフェニックスの軌道情報を送り, プログラムで制御して撮影したとあった. それにしても相当な離れ業である.

Camera pointing for the image from HiRISE used navigational information about Phoenix updated on landing day. The camera team and Phoenix team would not know until the image was sent to Earth whether it had actually caught Phoenix.

さらに普段は火星に向けて下を向いているカメラを, 斜め方向を撮影するため, 衛星の向きも変えたという. 見事な写真が送られてきたときの, 担当者の喜びが想像できる.

火星

太陽系の中で, 地球と火星は双子の惑星といわれる. 公転周期は地球が1年, 火星が2年. 公転半径は地球が1天文単位, 火星が1.6天文単位. (2年の方を知っていれば, Keplerの法則: 公転周期²/公転半径³=一定 から

(expt (expt 2 2) (/ 1 3)) => 1.5874010519681994)

だが, Bodeの法則を知っていれば距離は一発だ.)

この火星には火星人がいると思われていた. 運河らしいものが見えるからだ. 運河かどうかは分からないが, 火星の表面には多数の筋が見え, それが十字形で交差している. 一方, ガラスの割れ目など自然に出来る筋は, 新しい割れ目が既に割れている割れ目を横切らないから丁字形になる.

というわけで, 火星人襲来というSFはいくつかあるらしい. 私が小学生のころ愛読したのに, 海野十三の「火星兵団」がある. ある晩, 千葉県印旛沼の辺りに火星からのロケットが着陸. 火星人が地上に降り立つ.

H.G.Wellsによると, 火星人は, おむすびのような頭から, 糸のような足が生えている, 細い足を持つ蛸のようだと思われていた. 重力が小さいから細い足で支えられる. 食べ物は苔みたいだから, それをなめる口はおおきい. 空気が薄いので音声は伝わらず, 目が口のようにものを言うので, 目もおおきい. 耳は退化した.Wellsはそういう火星人を想像した.

私が小学生のころ, 上野の科学博物館で, こういう火星人を描いた絵はがきを売っていた.

「火星兵団」によると, 火星にくらべて空気の濃い地球では, 潜水服か宇宙服のような容器を着て, 地上で活躍した.

火星人は「ヒュウーヒュウープクプク」というような言葉を喋る. そのままでは日本人には理解出来ぬが, 彼らはすでに日火両語の音声翻訳機を持っていて,　一方から火星語を入れるともう一方から日本語が出る. 逆ももちろん可能.

まぁそういう話であった.

さて今回, NASAの火星探査機フェニックスが火星の北極近くに着地(着火?)したというニュースだ. 送られてきた火星の地上(火上?)の光景は, 運河は見えねど, 想像とあまり違わない. (いちいち「地」を「火」と言い直すのも面倒だねぇ.)

こう描きながら想像するのは, 火星人はフェニックスをみて, 「これが地球人か」と思ったかということだ. 「地球人襲来」というニュースが流れているかと夏の夢を楽しんでいる.

同一直線上の3点

久野君たちの努力により, Beautiful Codeの翻訳がでた. 以前 三省堂の洋書の棚にあるのを見たことはあったが, その時はパスした.

翻訳をみると, なにしろ多くの人がそれぞれのプログラム言語で書いた自分のプログラムを(それもかなり大きい部分を)自讚しているから, 読むのが大変そうである.

短くて面白かったのは, 33章「『本』のためにプログラムを書く」であった. 要するに平面上の3点A, B, Cの座標が与えられた時, その3点が同一直線上にあるかを判定するプログラムを書くのだ.

私がやっても多分こういうアプローチになるであろうという風に話は展開していく.

まずA,Bの2点を通る直線の式を決め, 点Cがそれに乗っているかを問うもの. これは最初の2点がy軸と平行な線上にあるときの始末が面倒.

次はABを通る直線の勾配と, ACを通る直線の勾配を計算し, それらが一致するかを見るもの. 勾配が無限大になるときはnilを返すようにすると, nil同士もeqで比べればtになるので便利なようだが, 気持は悪い.

3番目はBCの距離a, CAの距離b, ABの距離cを計算し, a,b,cを大きさの順にソートし, 最大の距離が残りの2つの距離の和になるかどうかを見る. この難点はPythagorasの定理で距離を求めるのに関数sqrtを使うことだ. 誤差は避けられない.

このようにして, 最後に辿り着いたのは, 3点で構成する三角形の面積を求め, それが0なら三角形はつぶれて3点は同一直線上にあることが分かるというもの.

たしかに高校生のとき, 三角形 ABC の面積は行列式

|Ax Ay 1|
|Bx By 1|
|Cx Cy 1|

の1/2と習った. 面積が0かとうかを見るのだから, 1/2はいらない, 正負も問題にならないから, A,B,Cを反時計まわりにおくことにこだわることもない.

(Ax*By+Bx*Cy+Cx*Ay)-(Ax*Cy+Bx*Ay+Cx*By)

の計算だから誤差も何もない. これで決りだ.

今年の夏のプロシンのテーマは「プログラムの品格」のようなものだ. 本書もひとしきり話題になりそうな予感.

dancing links

前回のdancing linksの続きである.

TAOCP 4巻分冊0が4月18日に発売になるとアマゾンからメイルが来た. その分冊0は7章の最初の部分で, そこにGraeco-Latin squareの話題が登場する.

Graeco-Latin squareの作り方は, 互いにorthogonalな2つのlatin squareを用意し, それを合わせればよいのだが, あるlatin square Lからそれとorthogonalなlatin square Mの作り方として, Lからtransversalという組を探す. これは直接orthogonalなlatin squareを作るより容易であると本文に書いてある.

その続きは次のようだ.

Once the transversals are known, we're left with an exact cover problem, of 10 stages, which is much simpler than the original 90 stage problem (6). All we need to do is cover the square with ten transversals that don't intersect --- because every such set of ten is equivalent to a latin square M that is orthogonal to L.

10とか90とかの数値は, ここでは10x10のsquareを求めているからである.

しかしこれだけの説明では, よく分からなかったので, 考えた結果がこのblogの趣旨である.

大きいsquareは面倒なので, 4x4を対象とする.
例えば Lとして

L=((0 3 1 2)
   (2 1 3 0)
   (3 0 2 1)
   (1 2 0 3))

は各行 各列に0,1,2,3が1回ずつ現れるから, latin squareになっている. これとorthogonalなlatin squareを求めるべく, Lのtransversalを探す. transversalはLの各行から1個 各列から1個 各文字から1個をとる組で,

A=((0      ) B=((  3    ) C=((    1  ) D=((      2)
   (  1    )    (2      )    (      0)    (    3  )
   (    2  )    (      1)    (3      )    (  0    )
   (      3))   (    0  ))   (  2    ))   (1      ))

E=((0      ) F=((    1  ) G=((      2) H=((  3    )
   (    3  )    (2      )    (  1    )    (      0)
   (      1)    (  0    )    (3      )    (    2  )
   (  2    ))   (      3))   (    0  ))   (1      ))

の8個が存在する.

このうちA,B,C,Dを重ねるとちょうどLになり, またE,F,G,Hを重ねてもちょうどLになる.

定義が後回しになったが, LとMがorthogonalというのは, LとMから対応する位置の要素をとって組にすると, 同じ値の組が複数回は出来ないということである.

したがって各transversalの0,1,2,3の位置には0,0,0,0のように同じ値をおけば, orthogonalなlatin squareが得られる. つまり

A,B,C,Dから
M0=((0 1 2 3)
    (1 0 3 2)
    (2 3 0 1)
    (3 2 1 0))

E,F,G,Hから
M1=((0 3 1 2)
    (1 2 0 3)
    (2 1 3 0)
    (3 0 2 1))

ができる (LM)の組を作ると M0とM1のそれぞれから

((00 31 12 23)  ((00 33 11 22)
 (21 10 33 02)   (21 12 30 03)
 (32 03 20 11)   (32 01 23 10)
 (13 22 01 30))  (13 20 02 31))

が得られorthogonalなことが分かる.

Lからdancing linksでtransversalを得る方法, transversalを使わず, 直接orthogonalなlatin square(Mateという)を得る方法はTAOCP ex7-17参照のこと.