Lermerの篩機械

先日のことだが, Mountain ViewにあるComputer History Museumに行ってきた. 思い込みの深い多くの計算機に対面できた. ただ残念ながらLehmerの初代の自転車のチェーンによる篩機械はドイツに出張中とかで, 見られなかった. これについて私は以前こう書いた. (bit 1997年7月号)

『「先日のことだが, ...」計算整数論者でカリフォルニア大学バークレイ校(以下UCB)教授だったDerrick Henry Lehmer(以下Dick)は昔のエピソードでもこう語り始めるのを好んだ. 私もひとつ真似をしよう.

先日のこと, Dickは集めてきた自転車のチェーンの部品でチェーンの輪を19個作った. それぞれの輪のリンク数は67までの素数だが, 13までの素数に対する輪は小さ過ぎるので64, 27, 25, 49, 22, 26とした. これをそれぞれ同軸に固定した10枚歯のスプロケットに掛け, 回転数をカウンターで数えながら軸をモーターで回転した. 輪は零の位置(または素数の倍数の位置)にピンを立てた時, カウンターが大きな整数Nになるまで軸を回転し, 停止時にどのピンも真上になければNには67以下の素因数はないわけだ.

また探すべき数が, いろいろな素数での法がいくつかという条件さえわかれば, その位置にピンを立て, ピンと接点, リレー, モーターを組合せ, 条件を満たす数が見つかった時点で回転を停止する機構も工夫した.

軸は300rpmで回転したので, 1日に432万個(=10×300×60×24)の整数を調べることができた. だが, この篩計算機を作った目的のMersenne数, 2²⁵⁷-1の素数性を調べるは$10⁷⁰年かかるらしい. さよう, Dickがこの篩を試作したのは, 彼がUCBの学部学生であった1926年のことである. この機械の複製はボストンのコンピュータミュージアムにあるが, 展示はしていないらしい. 』

Computer History Museumは1990年代にBostonからCaliforniaへ移動している. インターネットで探すとcomputer history museumに写真は見つかった.



どういう問題を解くか. Lehmerのような整数論者は高尚な問題を解くだろうが, 簡単な例はChinese Remainder Theoremのようなものである. つまり3で割れば1余り, 5で割れば2余り, 7で割れば3余る数はなにか.

3での剰余がp, 5での剰余がq, 7での剰余がrなら70p+21q+15r mod 105が解で, 今の70+42+45=157, 157 mod 105 = 52 となる. この程度なら篩機械はいらない.

楕円アルゴリズム

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

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

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」には閾値素子によるヒントが書いてある. 最近こういう話題は流行らないみたいで残念だ.

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

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

合宿からの帰路, 箱根登山電車で下山した. あじさい電車としてこの季節に有名で, 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)」でも触れられている. 石本君の解釈は, ダイアモンドクロスは, 揺れがひどく, それを避けたのかも知れないというのである.

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年後も夢幻にならずに使われているだろうか.

高橋先生

堀口大学の詩に

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

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

今日は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月号の編集系独白に書いたので, 読まれた方もあろう.