2008年7月24日木曜日

楕円アルゴリズム

MITのHakmemには意外な話題がたくさんある. プロッタで「円を描くアルゴリズム」もその1つだ.

newX=oldX-epsiron*oldY
newY=oldY+epsiron*newX

下の式で, newXを使うところがなんとなく怪しげなところ. さっそくPostscriptでやってみる.

200 200 translate
/x 100 def /y 0 def /eps 0.01 def
x y moveto
1 1 628 {pop
/x x y eps mul sub def %x=x-eps*y
/y y x eps mul add def %y=y+eps*x
x y lineto
} for stroke

とやるとちゃんと円が描ける.

一方, yの計算に昔のxの値を使うには, Postscriptのスタックを活用し

/x x y eps mul sub /y y x eps mul add def def

とすると, おかしいことになる. やはり新しいxが正解である.

epsの値を徐々に大きくすると, 円ではなく, 45度傾いた楕円を描くプログラムだったことが分かる. そこで楕円の長軸と短軸の長さを計算し重ねてみた.

200 200 translate
/x 100 def /y 0 def /eps 0.5 def
x y moveto
1 1 6.28 eps div {pop
/x x y eps mul sub def
/y y x eps mul add def
x y lineto
} for stroke
gsave
1 0 0 setrgbcolor %赤にする
45 rotate %45度傾ける
1.154700 0.894427 scale %長軸と短軸の長さにscaleする
100 0 moveto 0 0 100 0 360 arc stroke
grestore
0 0 1 setrgbcolor
-100 0 moveto 100 0 lineto
0 -100 moveto 0 100 lineto stroke


(100,0)から出発したときのepsに対する長軸と短軸の長さと離心率を数値計算で求めると

eps 長軸 短軸 離心率
0.5 115.47 89.44 0.6325
0.1 102.60 97.59 0.3086
0.01 100.25 99.75 0.0997

のようになる. 要するに「円を描くアルゴリズム」ではなく, 「楕円を描くアルゴリズム」であった.

2008年7月14日月曜日

3 not problem

私が3notの話を最初に聞いたのは, 1960年代の始め頃, サバティカルで東大に滞在していたイリノイ大学のDavid Muller先生からだ. 研究室のお茶の時間に「アメリカの計算機科学科でよく話題になる問題」の1つとして紹介された.

この話が記述されているのはあまり見た記憶がないが MITのHakmemには出ている. item 19の2-NOTs problemがそれである.

x,y,zの3入力, x',y',z'の3出力を持つブラックボックスがある. 入出力の関係は

x'=not x
y'=not y
z'=not z

である. ブラックボックスには, andとorは好きなだけ使われているが, notは2つしかないことが分かっている. 内部はどうなっているか.

Muller先生からこの話を聞いたわれわれは, その日は他の仕事がまったく手につかなかった. 解けてみるとなるほどと目から鱗の問題であった. 要は3は2ビットで表現できるということ.

Marvin Minsky先生の「Computation: finite and infinite machines」には閾値素子によるヒントが書いてある. 最近こういう話題は流行らないみたいで残念だ.

2008年7月9日水曜日

箱根登山電車のスイッチバック

「箱根の山は天下の険」へ行ってきた. あいにく停滞中の前線のせいで, 「雲は山をめぐり 霧は谷をとざす」という状態であり, 景観は今一つであった. まぁ議論の合宿なので, 景観はどうでもよい.

合宿からの帰路, 箱根登山電車で下山した. あじさい電車としてこの季節に有名で, 1万株といわれるあじさいは, 時として車体に触れるほどであった.

この線は名前通りに急勾配の登山電車で, 全線単線. またスイッチバックでも知られている. スイッチバックは昔は中央本線にも数多くあった. 甲府より東京側と甲府以遠とで, 構内配線の基本構造が違っていたが, 電車列車が多くなり, スイッチバックの駅も激減した.

スイッチバックと単線の駅構内配線をおさらいする.


スイッチバックには通過型と折り返し型がある. 図(A)は通過型で, 細い横線は上が低く, 下が高い等高線を示す. 太いのが線路だ. 通過型では, 坂を登り降りする通過列車はスイッチバックを無視し, LからHへ, またはHからLへ直進する. この駅(または信号所)に停車する列車は, Lから来た場合, 図の右方の行き止まり線へ進入し, 左方の行き止まり線へ逆行する. いずれかの行き止まり線にホームがある. その後H方向へ出発する. この型のスイッチバックは, 停車中の列車を引き出すのに, 水平部分の線区が必要ということで設けられた. 折り返し線は等高線に沿っている. 行き止まり線に入ったり, 逆行したりで面倒そうにも思えるが, ボッボッボーと逆行の汽笛を鳴らし, いとも簡単に戻り始める列車を楽しめた.

中央線のはこの型であった. 残存するのの1つに篠ノ井線の姥捨駅がある.

図(B)は折り返し型で, 全列車が, 折り返し線を使って登り降りする.

箱根登山鉄道とともに山岳鉄道の代表であった草軽電鉄の上信両州の境, 国境平駅のすぐ北に二度上という駅があった. 坂が急なので, 荷物を半分にし, 2回に分けて上げたという地名であるが, 草軽電鉄も二度上で折り返し型スイッチバックした.

この度の箱根登山線では, 金魚ばちといわれる運転席の後に陣取り, 箱根登山の線路の様子を見てきた. この線には, 両終点を除き, 信号所も含めて, 通過型の駅と折り返し型の駅がある. 折り返しがスイッチバックを兼ねる. それらは図に示すと, 通過型は図(A), 折り返し型は図の(B), (C)であった. (B)と(C)は左右が逆なだけで, 機能的には同じと見てよい. (B)は上大平台と出山の信号所, (C)は大平台であり, 彫刻の森の他は, 仙人台信号所を含めてすべての通過型の駅の構造は(A)である. (D)については後述する.

Hは山の上(強羅)側, Lは下(湯本)側である. 図にはポイントがいくつも示してあり, 脇にSとあるのは, スプリング型のポイントで, 定位の方の線がつなげて描いてある. つまり対向に進むとき(進行方向へ分岐している)は, 実線がつながっている方向へ進行する. 背向に進むとき(左右からの線路が合流する)は, 線が切れていても(ポイントが反対を向いていても), 列車は車輪のフランジで無理に押し分けて進む. 列車が去った後, スプリングにより, ポイントは定位に戻る.

線路の横にある短い実戦はホームのつもり.

さて(A). 山から降りてきた列車は, 対向のスプリングポイントで左へ分岐し, 上り列車用のホームへ進入する. 下から登ってきた列車も, 同様に左へ分岐し, 下り列車用のホームへ進入する. 駅の構造は, 進入してくる列車が入れる方を定位とする.

出発すると, 再び単線区間に入るので, 通常は出発方向の先に安全側線が設けられるが, どの駅も下向きにしか安全側線はなかった. あえぎながら登ってくる列車は, 暴走して通過する心配はないと考えたのであろうか.

折り返し型の駅の構造も面白い. 原則として, 進入する列車は渡りを通らず直行する. 上り下りの列車が同時に進入できるためであるのはいうまでもない. この構造だと, 駅から出発する両列車は, 同一区間を同一方向に走ることがあるので, その先のポイントの転轍操作は必要になる.

2つのわたり線はなぜダイアモンドクロスになっていないかと不思議に思うのは当然だ. そうすると図(B)を描きなおした図(D)のように4つのポイントはすべてスプリングにすることが出来るからである. つまりHからの列車は最初の対向ポイントSを直進, 次の背向ポイントでも直進, ホームに入る. 逆行してからは, 最初の対向ポイントで渡り, 次の背向ポイントでL方向へ入る. Lからの列車も同様である.

このことは昔石本祐吉君と話したことがあり, その後石本君が出版した「鉄のほそ道--写真で綴る線路の話--(アグネス技術センター 1996)」でも触れられている. 石本君の解釈は, ダイアモンドクロスは, 揺れがひどく, それを避けたのかも知れないというのである.

2008年7月2日水曜日

Lisp 50歳

織田信長の 人間五十年 下天のうちを比ぶれば 夢まぼろしの如くなり は有名だ. ところで最近計算機のまわりで50年を迎えるものが目立つ.

パラメトロン計算機 PC-1 は今年3月26日に完成50年を祝った. 来年1月のプログラミング・シンポジウムは第50回だ(49年ということ). 同じく1960年に設立された, 情報処理学会も50周年の事業を準備中と聞く.

ところで今度は本年10月20日に, Lisp50歳の誕生日を祝うというニュースが来た. 計算機に比べて, プログラム言語はいつが誕生日か判定が難しいところだ. 上のニュースによると, 1958年10月にMcCarthyが発表した論文にLISPという名前が始めて使われたとある. 20日というのは, 丁度そのころOOPSLAが開催されているかららしい.

McCarthyのLispの論文といえば, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part Iが知られていて, CACM, 1960年4月号に載ったもので, McCarthyのウェブページにも, This was the original paper on LISPと書いてある. これはそのウェブページからダウンロード出来る. しかしこれが1958年10月に出た論文と同じかは不明である. 似たような論文がいくつかあるからだ.

1958年の11月頃, 私はMITを訪れた. その折, MITに滞在中の藤村先輩から面白いからといってMcCarthyの論文を渡された. それがひょっとして1958年10月の論文かも知れないと思っている. (CACMに載った論文の紹介は, 情報処理学会誌44巻3号にある.)

最近あまり聞かなくなった, Algolも最初に発表されたのは, 1958年であったから, 同様にお祝いされてもいいはずだが, すぐに改良版Algol 60としてより広く知られるようになり, Algol 58の名前を覚えている人は少ない. そのAlgol 60も今や風前の灯火で, AlgolはJISからも抹殺された. しかしAlgol 60の精神はScheme(の特にRevised Report)に受け継がれている.

OOPSLAの会議では「next 50 years of Lisp」についても議論するという. 50年後も夢幻にならずに使われているだろうか.