2012年6月13日の私のブログ「復活祭公式」にある, Winning Waysが「3月28日 Doomsday(最後の審判の日)」という日の曜日は実はなかなか重要である.
曜日としては3月28日は3月0日と同じだが, この曜日は4月4日, 6月6日, 8月8日, 10月10日, 12月12日の曜日と一致する. (これらを目印の日といおう.) 4月から後については, 偶数4≤m≤10のm月m日と(m+2)月(m+2)日の間隔は, 大の月が1回と小の月が1回と2日あるから31+30+2=63で, これが7で整除出来るから同じなわけだ.
5月以降の奇数月については, 大の月m∈{5,7}ではm月(m+4)日, 小の月m∈{9,11}ではm月(m-4)日が同じ曜日になる. つまり大の月のm月m日と次の(m+1)月(m+1)日の間隔は31+1=32日, 従ってm月(m+4)日から後の目印の日までの間隔は4日減って28日になる. 小の月のm月m日と(m+1)月(m+1)日の間隔は30+1=31日, m月(m-4)日から後の目印の日までの間隔は4日増えて35日になり, どちらも7で整除できる. ブラボー!
このように4を足したり引いたりするより, 4ヶ月離れた5月9日と9月5日, 7月11日と11月7日が目印の日と私は覚えているが, 次のパラグラフの1月のことを考えると+4日という情報は覚えておく価値がある.
さてその4月より前の月はどうか. 3月は最初に書いたように0日が目印の日だ. 3月が31日あり, 4月4日までは35日あるから確かに. もちろん3月は大の月だから, 3月(3+4)日が目印の日になる, 1月と2月については前年の13月と14月と思えはよいが, 14月14日は途中に大の月が2回あるから, 上の偶数月とは同じ関係にはならない. が, 上記のような理由を理解していれば2月は14-1=13日が前年の目印の曜日になる. また1月は大の月だから13-1+4と1月16日になる.
昨年の目印の曜日は月曜であった. 今年のカレンダーを見直すと, 1月16日, 2月13日は, 月曜で当たりだ. 今年は来年の2月まで水曜, 水曜と唱えていれば, 各月の曜日の計算はお茶の子である.
2012年6月13日水曜日
復活祭公式
復活祭からずいぶんたって, いまや聖ヨハネ節が近い. 気が抜けた話題だが, Winning Waysを眺めていたら, そこにも復活祭公式があった. 存外簡単である.
復活祭は春分満月の後の日曜であり, そこで春分満月の公式が重要である.
本書によると, 春分満月の日は
(4月19日=3月50日)-(11G+C)mod 30
だが, それが4月19日なら4月18日にする; 4月18日でG>=12なら4月17日にする.
ただし黄金数Gは
G=(年 mod 19)+1
世紀項Cは
19xx, 20xx, 21xx年は-6.
2012年で計算すると
(+ (modulo 2012 19) 1) => 18 ;G
(modulo (+ (* 11 18) -6) 30) => 12
従って19-12で4月7日になる.
次に本書によると3月28日をDoomsday(最後の審判の日)といい, 今年は水曜であった. すると3月25日が日曜, 4月1日が日曜, 4月8日が日曜で, 復活祭はまだ記憶にあるように4月8日であった.
Doomsdayの曜日は, (世紀初頭のDoomsday+その後の年に12が含まれる数+その余りの数+その余りに4が含まれる数)mod 7と計算でき, 21世紀初頭(2000年)は火曜であった.
従って2012年は
(let ((y 12))
(+ (quotient y 12) (modulo y 12) (quotient (modulo y 12) 4)))
=> 1
で水曜だ.
Gregorian暦の曜日は400年で一周するから, 世紀初頭の曜日は2000年の火曜から始まり, 2100年日曜, 2200年金曜, 2300年水曜で循環する. (100年に閏年が24回だと5日進み, 25回だと6日進む. 2000年3月28日は閏日を過ぎているから, 2100年3月28日までは25回だと6日進む. 2000年3月28日は閏日を過ぎているから, 2100年3月28日までは5日進んで, 水木金土日, 次も月火水木金, 次も土日月火水, 最後が6日進んで木金土日月火になるわけだ.)
我々は当面火曜を覚えておけば暮らしていける.
復活祭は春分満月の後の日曜であり, そこで春分満月の公式が重要である.
本書によると, 春分満月の日は
(4月19日=3月50日)-(11G+C)mod 30
だが, それが4月19日なら4月18日にする; 4月18日でG>=12なら4月17日にする.
ただし黄金数Gは
G=(年 mod 19)+1
世紀項Cは
19xx, 20xx, 21xx年は-6.
2012年で計算すると
(+ (modulo 2012 19) 1) => 18 ;G
(modulo (+ (* 11 18) -6) 30) => 12
従って19-12で4月7日になる.
次に本書によると3月28日をDoomsday(最後の審判の日)といい, 今年は水曜であった. すると3月25日が日曜, 4月1日が日曜, 4月8日が日曜で, 復活祭はまだ記憶にあるように4月8日であった.
Doomsdayの曜日は, (世紀初頭のDoomsday+その後の年に12が含まれる数+その余りの数+その余りに4が含まれる数)mod 7と計算でき, 21世紀初頭(2000年)は火曜であった.
従って2012年は
(let ((y 12))
(+ (quotient y 12) (modulo y 12) (quotient (modulo y 12) 4)))
=> 1
で水曜だ.
Gregorian暦の曜日は400年で一周するから, 世紀初頭の曜日は2000年の火曜から始まり, 2100年日曜, 2200年金曜, 2300年水曜で循環する. (100年に閏年が24回だと5日進み, 25回だと6日進む. 2000年3月28日は閏日を過ぎているから, 2100年3月28日までは25回だと6日進む. 2000年3月28日は閏日を過ぎているから, 2100年3月28日までは5日進んで, 水木金土日, 次も月火水木金, 次も土日月火水, 最後が6日進んで木金土日月火になるわけだ.)
我々は当面火曜を覚えておけば暮らしていける.
2012年6月2日土曜日
Life Game
前回のこのブログでは, キックバックを利用した希薄銃の実現法を述べた. その少し先にConwayはグライダーの列から連続する3機のグライダーを消滅させる方法を書いている.
120クロック毎に打ち出されるグライダーの列があるとする.
(i) 1機目のグライダーが別のグライダーでキックバックされ, 元の方向へ戻る．
(ii) 2機目が戻ってきた1機目と正面衝突し, ブロックを生じる.
(iii) 3機目がこのブロックに衝突して消える.
これを読んでなるほどと思ってもよいが, やはりシミュレートしてみたい.
この図はグライダーの列が右上から左下へ飛んでいるところで，先頭のaがまさにキッバックされる位置にいる. 後続のbとcは120クロック離れている．dはキックバックを仕掛けるグライダーで, 左上から右下へ飛んでいる. その先にイーターEを置く.
この時点のクロックを0としよう.
次の図は, クロック8で, キックバックが終わり，1機目(a)が向きを反転したところである.
この2つの図の間の様子は前回のブログのキックバックの遷移図の0から8である.
その後しばらくしてクロック60では1機目(a)と2機目(b)があわや衝突寸前になる.
クロック66でこの2機はブロックになる.
次はクロック172で, 3機目(c)がブロックに迫る.
クロック176ではブロックと機体の破片だけになり, 次のクロックでは何もなくなる.
この図で右上に見えるeはちょうどキックバックのグライダーが来るのでなければ, 消えることなく左下へ進む.
これで安心して先が読める. この機構を利用し, グライダー列による情報を複製する話にるのだが, それも結構複雑で, Life Gameは万能とはいえ素子があまり単純な故であろう.
うまく動くシミュレーションを眺めるのは楽しい.
120クロック毎に打ち出されるグライダーの列があるとする.
(i) 1機目のグライダーが別のグライダーでキックバックされ, 元の方向へ戻る．
(ii) 2機目が戻ってきた1機目と正面衝突し, ブロックを生じる.
(iii) 3機目がこのブロックに衝突して消える.
これを読んでなるほどと思ってもよいが, やはりシミュレートしてみたい.
この図はグライダーの列が右上から左下へ飛んでいるところで，先頭のaがまさにキッバックされる位置にいる. 後続のbとcは120クロック離れている．dはキックバックを仕掛けるグライダーで, 左上から右下へ飛んでいる. その先にイーターEを置く.
この時点のクロックを0としよう.
次の図は, クロック8で, キックバックが終わり，1機目(a)が向きを反転したところである.
この2つの図の間の様子は前回のブログのキックバックの遷移図の0から8である.
その後しばらくしてクロック60では1機目(a)と2機目(b)があわや衝突寸前になる.
クロック66でこの2機はブロックになる.
次はクロック172で, 3機目(c)がブロックに迫る.
クロック176ではブロックと機体の破片だけになり, 次のクロックでは何もなくなる.
この図で右上に見えるeはちょうどキックバックのグライダーが来るのでなければ, 消えることなく左下へ進む.
これで安心して先が読める. この機構を利用し, グライダー列による情報を複製する話にるのだが, それも結構複雑で, Life Gameは万能とはいえ素子があまり単純な故であろう.
うまく動くシミュレーションを眺めるのは楽しい.
2012年5月21日月曜日
Life Game
Life Gameはuniversalであるといわれる. つまり計算機を構築する部品がいろいろ考案され, それを組合せればよいという議論らしい. ただ, von Neumannの自己増殖機械みたいに, 縦何セル, 横何セル, 遺伝子のセル何個で出来るというような具体的な数値がないので, これで時間さえかければ解けるよね, といわれている程度にしか納得できない.
さて, そういう部品の一つに希薄銃(thin gun)というのがある. Life Gameで作る計算機の情報(信号)は, 2次元世界を飛び回わるグライダーだが, グライダー銃は30クロックごとにグライダー1個を発射し, これでは濃すぎる(多すぎる)ので, もっと間引いたグライダー列を作りたい. その機構が希薄銃である. 本当に出来るかなと思いやってみた.
次の図が希薄銃の様子を示す. これはProcessingのシミュレータで動いているもののある時点でのスナップショット(をPostScriptで書き直したもの)である.
赤い丸で数字を囲ったのが3個所あり, それぞれグライダー銃がグライダーを発射する場所だ. 左上のグライダー銃0は, 右下へグライダーを出し続ける. 図に見えるグライダーに先頭からa, b, c,...と標識を付ける.
(グライダー銃はもっと複雑な形だが, こんな大きなものをシミュレータに書き込むと, 広い面積が必要になるので, このシミュレーションでは, シミュレータがどのタイミングにどの位置でどの方向へグライダーを発射するかのシナリオに従ってグライダーを発生する.)
右端の中ほどに1番のグライダー銃があり, これは左上へグライダーを送る. こちらのグライダーをf, g, h,...とする.
これらグライダーの2列の間で, eというグライダーが右上に向っている. これはConwayのいうキックバックで, eは2つのグライダー列の間を右上と左下で往復する. eは間もなくfと接触し, eとfは消滅し, eと逆向きのグライダーが出現する.
そうして戻ってくるキックバックのグライダーは, タイミング的には0番のグライダー列のdと接触し, dを消し, また右上へキックバックする.
eが前回右上に向う前に, 左下へ向っていたグライダーはaの1機前のグライダーに衝突し, 右上へキックバックしていたのである. 0番のグライダー列は, したがって, a, b, cとキックバック地点を通過した後, dは消滅し, その後また3個通過し, 1個消滅する,... を繰り返す.
左上へ進んでいる1番のグライダー列も, 4個に1個はキックバックで消えるが, 3個はキックバックされずに通過する. しかしキックバック後のグライダーは要らないから, Eと書いたイーターで吸い込む.
上の図には中央あたりに2番のグライダー銃があり, グライダーを左下へ発射している. そこへキックバックを回避してきた0番のグライダー列が近づく. この衝突は, 両者が消滅する位相であって右下へ通過するグライダーはないが, すでにキックバックで消えた0番グライダーに対応するホールでは, 2番のグライダーは衝突を免れ, 左下へ進む. 図の左下のグライダーiは, そのように抜けてきたものである. その後3機の2番のグライダーは, キックバックを免れた0番のグライダーのために消滅してホールになる. jはaの前のグライダーがホールだったため, 抜けてきたのである.
このようにして, キックバックで3/4になった0番のグライダー列により, 1/4に希薄になったグライダー列が発生出来る.
次は, キックバックの起こし方だ. グライダーの位置決めのため, ある方向に進むグライダーの4位相パターンのそれぞれに, 注目点を決めよう.
この右下へ移動するグライダーの図で, 左上, 右上, 左下, 右下が赤字のようにそれぞれ位相0,1,2,3で, 一番進行方向に近い場所を注目点とする. 位相0はいわゆるハッカーエンブレムの形で, 4クロック後には右へも下へも1セル分移動する.
Conwayの示すキックバック機構の図は以下の通り.
白黒を問わず, 丸が生きているセルである. 下の数字0から8は相対クロックだ. クロック0では上に左下へ進むグライダー, 下に右下へ進むグライダーが見える. 黒丸は次のクロックでも生き残るセル. 白丸は次には消えるセル, 点は今は死んでいるが, 次のクロックで生まれるセルだ.
この反応を経て, クロック6,7,8では右上へキックバックされるグライダーが形成され, 8が丁度0と180度逆転している. つまり, ターンで8クロックかかるわけだ.
グライダーの列は30クロック間隔なので, 向こうでもう一度キックバックされ, 30の倍数で戻ってくれば, 後続のグライダーとうまく衝突出来る. こちらのターンで8, 向こうで8かかると, 16クロック. 1歩進むのに4クロックかかるから, その距離往路と復路で8クロック. 16足す何倍かの8クロックの和で30の倍数になるのは,
30=16+8*1.75
60=16+8*5.5
90=16+8*9.25
120=16+8*13
だから, 最後のが解で13ステップの距離を往復し, 片側で120クロック毎にキックバックを起すことになる. 120はグライダー間隔30クロックも4倍なので, 4機に1機が犠牲になる.
この計算から分かるように, 240クロックでもグライダー間隔を28にすればキックバック出来る. Conwayの記述には, 1/Nに希釈出来るが, Nは4の倍数でなければならないとある.
先ほどの図で, グライダー0とキックバックしたとして, 次のグライダー1とのキックバックはどこだろうか. タイミング0の下のグライダーの注目点(下の3x3の正方形の右下)をx=0,y=0とすると, タイミング8の右上に出発しようとするグライダーの注目点はx=0,y=5である(yは上向きに測る.)
次の衝突のタイミング0は13セル間隔離れているから, x=13, y=18, つまりタイミング0の上のグライダーの注目点がそこである. 従って, その時点で1番のグライダーの注目点は, 0の下のグライダーと180度回転した形で, xが1少なく、yが4多い. x=12, y=22にグライダーがあれば良い. そのタイミングでグライダーを発射するように1番のグライダー銃を配置する. または, xとyを1ずつ遠ざけると, 発射の位相を4早める.
キックバックの図を描くプログラムを利用して, 2個のグライダー消滅の様子も描いてみよう.
この図のように, 左上から来るグライダー(下)と右上から来るの(上)とが, この位置で出会うと4クロック後に消滅する. 右上の2番から出続けるグライダーは, 左上のグライダーがあると消滅し, ないと飛び続けるから, これをNot回路という.
シミュレータを使うノウハウも結構たまったので, またいろいろ遊べそうだ.
さて, そういう部品の一つに希薄銃(thin gun)というのがある. Life Gameで作る計算機の情報(信号)は, 2次元世界を飛び回わるグライダーだが, グライダー銃は30クロックごとにグライダー1個を発射し, これでは濃すぎる(多すぎる)ので, もっと間引いたグライダー列を作りたい. その機構が希薄銃である. 本当に出来るかなと思いやってみた.
次の図が希薄銃の様子を示す. これはProcessingのシミュレータで動いているもののある時点でのスナップショット(をPostScriptで書き直したもの)である.
赤い丸で数字を囲ったのが3個所あり, それぞれグライダー銃がグライダーを発射する場所だ. 左上のグライダー銃0は, 右下へグライダーを出し続ける. 図に見えるグライダーに先頭からa, b, c,...と標識を付ける.
(グライダー銃はもっと複雑な形だが, こんな大きなものをシミュレータに書き込むと, 広い面積が必要になるので, このシミュレーションでは, シミュレータがどのタイミングにどの位置でどの方向へグライダーを発射するかのシナリオに従ってグライダーを発生する.)
右端の中ほどに1番のグライダー銃があり, これは左上へグライダーを送る. こちらのグライダーをf, g, h,...とする.
これらグライダーの2列の間で, eというグライダーが右上に向っている. これはConwayのいうキックバックで, eは2つのグライダー列の間を右上と左下で往復する. eは間もなくfと接触し, eとfは消滅し, eと逆向きのグライダーが出現する.
そうして戻ってくるキックバックのグライダーは, タイミング的には0番のグライダー列のdと接触し, dを消し, また右上へキックバックする.
eが前回右上に向う前に, 左下へ向っていたグライダーはaの1機前のグライダーに衝突し, 右上へキックバックしていたのである. 0番のグライダー列は, したがって, a, b, cとキックバック地点を通過した後, dは消滅し, その後また3個通過し, 1個消滅する,... を繰り返す.
左上へ進んでいる1番のグライダー列も, 4個に1個はキックバックで消えるが, 3個はキックバックされずに通過する. しかしキックバック後のグライダーは要らないから, Eと書いたイーターで吸い込む.
上の図には中央あたりに2番のグライダー銃があり, グライダーを左下へ発射している. そこへキックバックを回避してきた0番のグライダー列が近づく. この衝突は, 両者が消滅する位相であって右下へ通過するグライダーはないが, すでにキックバックで消えた0番グライダーに対応するホールでは, 2番のグライダーは衝突を免れ, 左下へ進む. 図の左下のグライダーiは, そのように抜けてきたものである. その後3機の2番のグライダーは, キックバックを免れた0番のグライダーのために消滅してホールになる. jはaの前のグライダーがホールだったため, 抜けてきたのである.
このようにして, キックバックで3/4になった0番のグライダー列により, 1/4に希薄になったグライダー列が発生出来る.
次は, キックバックの起こし方だ. グライダーの位置決めのため, ある方向に進むグライダーの4位相パターンのそれぞれに, 注目点を決めよう.
この右下へ移動するグライダーの図で, 左上, 右上, 左下, 右下が赤字のようにそれぞれ位相0,1,2,3で, 一番進行方向に近い場所を注目点とする. 位相0はいわゆるハッカーエンブレムの形で, 4クロック後には右へも下へも1セル分移動する.
Conwayの示すキックバック機構の図は以下の通り.
白黒を問わず, 丸が生きているセルである. 下の数字0から8は相対クロックだ. クロック0では上に左下へ進むグライダー, 下に右下へ進むグライダーが見える. 黒丸は次のクロックでも生き残るセル. 白丸は次には消えるセル, 点は今は死んでいるが, 次のクロックで生まれるセルだ.
この反応を経て, クロック6,7,8では右上へキックバックされるグライダーが形成され, 8が丁度0と180度逆転している. つまり, ターンで8クロックかかるわけだ.
グライダーの列は30クロック間隔なので, 向こうでもう一度キックバックされ, 30の倍数で戻ってくれば, 後続のグライダーとうまく衝突出来る. こちらのターンで8, 向こうで8かかると, 16クロック. 1歩進むのに4クロックかかるから, その距離往路と復路で8クロック. 16足す何倍かの8クロックの和で30の倍数になるのは,
30=16+8*1.75
60=16+8*5.5
90=16+8*9.25
120=16+8*13
だから, 最後のが解で13ステップの距離を往復し, 片側で120クロック毎にキックバックを起すことになる. 120はグライダー間隔30クロックも4倍なので, 4機に1機が犠牲になる.
この計算から分かるように, 240クロックでもグライダー間隔を28にすればキックバック出来る. Conwayの記述には, 1/Nに希釈出来るが, Nは4の倍数でなければならないとある.
先ほどの図で, グライダー0とキックバックしたとして, 次のグライダー1とのキックバックはどこだろうか. タイミング0の下のグライダーの注目点(下の3x3の正方形の右下)をx=0,y=0とすると, タイミング8の右上に出発しようとするグライダーの注目点はx=0,y=5である(yは上向きに測る.)
次の衝突のタイミング0は13セル間隔離れているから, x=13, y=18, つまりタイミング0の上のグライダーの注目点がそこである. 従って, その時点で1番のグライダーの注目点は, 0の下のグライダーと180度回転した形で, xが1少なく、yが4多い. x=12, y=22にグライダーがあれば良い. そのタイミングでグライダーを発射するように1番のグライダー銃を配置する. または, xとyを1ずつ遠ざけると, 発射の位相を4早める.
キックバックの図を描くプログラムを利用して, 2個のグライダー消滅の様子も描いてみよう.
この図のように, 左上から来るグライダー(下)と右上から来るの(上)とが, この位置で出会うと4クロック後に消滅する. 右上の2番から出続けるグライダーは, 左上のグライダーがあると消滅し, ないと飛び続けるから, これをNot回路という.
シミュレータを使うノウハウも結構たまったので, またいろいろ遊べそうだ.
2012年5月9日水曜日
PC-1シミュレータ
パラメトロン計算機 PC-1のシミュレータは何回も書いたことがある. 数年前にC言語とxlibで実装したのは, 計算機のインディケータの点滅も再現していて, 見ていると楽しい. それを公開したいと思っていたが, うまい方法が見つからず, 延び延びになっていた.
しかし, 情報処理学会コンピュータ博物館のウェブページで, 「PC-1 パラメトロン式計算機」を見ると, 「現在PC-1の現物は存在しないが, 和田英一によりノートPC上でPC-1シミュレータが実現され, 当時のプログラムが動作している.」と書いてあるので, 早く公開しなければと少しずつ公開用の実装を進めていた.
今回, やっとProcessingで実装した同様のシミュレータが完成したので, お目にかけたい. ただ, 私の新しい4CPUのMacBook Airでは順調に走るのだが, 古い方のMacBookAirでは, インディケータが高速には点滅せず, 臨場感がいまいちだ. また私のウェブページパラメトロン計算機 PC-1も参考にされたい.
さて, 今回のシミュレータである.
http://playground.iijlab.net/~ew/pc1sim/pc1sim.html
にアクセスすると, 下のような画面が現れる. これがシミュレータのインターフェースだ.
中央左よりの緑の小箱の列は, インディケータで, 最上段の左18ビットが命令レジスタ, その右11ビットがSCC(シーケンスコントロールカウンタ), その下で36個並ぶのは, 上からメモリーレジスタ, アキュムレータ, Rレジスタである. PC-1は1語が18ビットだが, 2語つなげて36ビットを長語として演算が出来た.
各レジスタの内容の0(白で)と1(オレンジ色で)が表示される.
情報処理学会のコンピュータ博物館にパラメトロン計算機PC-1のウェブページがあり, 後藤さんと高橋先生がPC-1の前にいる写真がある. そのPC-1の上の方にネオン管が並んでいるが, それがこのインディケータである.
インディケータの右で3行3列に並ぶ枠がスイッチである. 上の3個は左からクリアスタート(Clear Start), イニシアルスタート(Init Start), リスタート(Restart). リスタートは中断したプログラムを再開する. PC-1では, 停止したとき, 次の命令が命令レジスタに読み出されているから, それを棄て, SCCの示す場所の命令からスタートするのがイニシアルスタートである. さらにSCCを0にした上でイニシアルスタートするのがクリアスタートである.
このシミュレータは先読みしないので, 中と右のスタートは同じである.
中段の3個は左からイニシアルロード(Init Load), フリーラン(Free Run), ストップ(Stop)で, フリーランは連続実行モードをオンにし, ストップはオフにする. オフの時のスタートスイッチは, 命令のステップ実行になる. 左端のイニシアルロードは, イニシアルオーダーのテープを読込む.
下段は左からイニシアルオーダーテープを用意する(Place R0); e1000桁のテープを用意する(Place e1000)スイッチである. 右端は, 他のデモテープを選択する(Place Tape)スイッチで, 現れたメニューから選ぶ.
テープ選択スイッチを押すと,
のように右上にメニューが出るので, 使いたいデモプログラムをクリックする.
デモテープは次の4つが用意してある.
a. factorize32 2^31-1, 2^31-3, ..., 2^31-19 を素因数分解する (5分55秒)
b. eratosthenes 篩を使い256から11327までの素数の表を作る (7分)
c. lucaslehmer 3から199までの素数pについてMpの素数性を調べる
d. e1000 自然対数の底eの値を1000桁計算する (6分15秒)
lucas lehmer以外のそれぞれの最後は私が最近ウェブでテストしたの終了までの時間である.
シミュレータを使うには, まず左下のLoad R0スイッチで, イニシアルオーダーR0 のテープを用意する. 次にその上のInit Loadスイッチで, R0を読込む. テープの6列分がメモリーレジスタに読込まれ, 長語(36ビット)として, SCCの表示する0番地, 2番地, ..., に読込まれ, 同時にアキュムレータの各ビットとXORをとってアキュムレータに戻す. 読み終わったとき, アキュムレータが0になるようにパリティビットがテープに入っている.
e1000桁は当時ポピュラーだったデモプログラムである. フリーランにして, クリアスタートでテープ読込みと計算が始まる.
このプログラムは460の階乗分の1までで計算するが, 4回分を一度にまとめて計算するので, インディケータの規則的な繰り返しが115回で計算は終了. その後は結果の二進十進変換になる. このプログラムはR0を壊さないから, 次のデモはR0の再読込みなしで始められる.
factorize31は 231-1, 231-3, 231-5,...231-19を素因数分解するデモプログラムである. このテープは入力サブルーチンのテープを読込んだ後, 停止するから, フリーランをクリックし, リスタートしなければならない. 結果は以下のようになる.
最初と最後が素数であり, 特に最初はMersenne素数である. 231の平方根 46340までの疑似素数で割ってみる. 割る値がRレジスタに見えている. 46340は八進法では132404なので, Rレジスタの中央より右が132000くらいになると素数でも計算は終了する.
このデモプログラムはR0を破壊するので, 次のデモの前にはR0を再読込みする必要がある.
eratosthenesの篩 256から11327までの素数を篩で探す. 篩には36ビット長語の32ビットを使い, 残りの4ビットには疑似素数の差を保持する.
最初3で篩い, 次に5で篩い, ..., 11327の平方根106で篩うまで篩えばよいのだが, このプログラムは, 疑似素数の差の循環時に終了テストをするから, 231(八進で347)になるまで篩う. 篩う数はRレジスタに見え, 篩う数が大きくなると, 篩うのに要する時間短くなるのが分かる.
篩終わると, 出力ルーチンが読込まれ, 結果の1315個の素数を持つ素数表257. 263. ... . 11321. が印字される. このデモプログラムはR0を破壊しない.
Lucas Lehmerテスト ある素数pについて, Mp=2p-1が素数の時, MpをMersenne素数という. この素数性を調べるLucas Lehmerテストというのがある. s0=0, sn=sn-12-2(mod Mp)を計算し, sp-2=0(mod Mp)ならMpは素数である.
デモプログラムlucas lehmerはp=2,3,...,199の素数について, Mpの素数性をしらべ, 素数ならpを, 合成数ならcを印字する.
最後まで実行すると相当時間がかかるので, 適当なところで中断しよう. PC-1が活動していた頃, 分かっていたMersenne素数はM3217くらいまでであった.
デモプログラムはplayground.iijlab.net/~ew/pc1sim/{e1000, factorize31, eratosthenes, llt}で見られる.
これらのシミュレーションは50年前の実機より格段に速い. しかしネオン管の明滅は当時を彷彿とさせる. 最近のCPUはブラックボックスになって, なにがどうなっているか分からないが, 当時はこのようなインディケータを眺めて計算の進行状況を知り, 一喜一憂していたものだ. 出力も印刷電信機で, 大きな音をたて, 机をゆさゆさ揺らしながら, 文字を出力していた. あれから半世紀が過ぎた.
しかし, 情報処理学会コンピュータ博物館のウェブページで, 「PC-1 パラメトロン式計算機」を見ると, 「現在PC-1の現物は存在しないが, 和田英一によりノートPC上でPC-1シミュレータが実現され, 当時のプログラムが動作している.」と書いてあるので, 早く公開しなければと少しずつ公開用の実装を進めていた.
今回, やっとProcessingで実装した同様のシミュレータが完成したので, お目にかけたい. ただ, 私の新しい4CPUのMacBook Airでは順調に走るのだが, 古い方のMacBookAirでは, インディケータが高速には点滅せず, 臨場感がいまいちだ. また私のウェブページパラメトロン計算機 PC-1も参考にされたい.
さて, 今回のシミュレータである.
http://playground.iijlab.net/~ew/pc1sim/pc1sim.html
にアクセスすると, 下のような画面が現れる. これがシミュレータのインターフェースだ.
中央左よりの緑の小箱の列は, インディケータで, 最上段の左18ビットが命令レジスタ, その右11ビットがSCC(シーケンスコントロールカウンタ), その下で36個並ぶのは, 上からメモリーレジスタ, アキュムレータ, Rレジスタである. PC-1は1語が18ビットだが, 2語つなげて36ビットを長語として演算が出来た.
各レジスタの内容の0(白で)と1(オレンジ色で)が表示される.
情報処理学会のコンピュータ博物館にパラメトロン計算機PC-1のウェブページがあり, 後藤さんと高橋先生がPC-1の前にいる写真がある. そのPC-1の上の方にネオン管が並んでいるが, それがこのインディケータである.
インディケータの右で3行3列に並ぶ枠がスイッチである. 上の3個は左からクリアスタート(Clear Start), イニシアルスタート(Init Start), リスタート(Restart). リスタートは中断したプログラムを再開する. PC-1では, 停止したとき, 次の命令が命令レジスタに読み出されているから, それを棄て, SCCの示す場所の命令からスタートするのがイニシアルスタートである. さらにSCCを0にした上でイニシアルスタートするのがクリアスタートである.
このシミュレータは先読みしないので, 中と右のスタートは同じである.
中段の3個は左からイニシアルロード(Init Load), フリーラン(Free Run), ストップ(Stop)で, フリーランは連続実行モードをオンにし, ストップはオフにする. オフの時のスタートスイッチは, 命令のステップ実行になる. 左端のイニシアルロードは, イニシアルオーダーのテープを読込む.
下段は左からイニシアルオーダーテープを用意する(Place R0); e1000桁のテープを用意する(Place e1000)スイッチである. 右端は, 他のデモテープを選択する(Place Tape)スイッチで, 現れたメニューから選ぶ.
テープ選択スイッチを押すと,
のように右上にメニューが出るので, 使いたいデモプログラムをクリックする.
デモテープは次の4つが用意してある.
a. factorize32 2^31-1, 2^31-3, ..., 2^31-19 を素因数分解する (5分55秒)
b. eratosthenes 篩を使い256から11327までの素数の表を作る (7分)
c. lucaslehmer 3から199までの素数pについてMpの素数性を調べる
d. e1000 自然対数の底eの値を1000桁計算する (6分15秒)
lucas lehmer以外のそれぞれの最後は私が最近ウェブでテストしたの終了までの時間である.
シミュレータを使うには, まず左下のLoad R0スイッチで, イニシアルオーダーR0 のテープを用意する. 次にその上のInit Loadスイッチで, R0を読込む. テープの6列分がメモリーレジスタに読込まれ, 長語(36ビット)として, SCCの表示する0番地, 2番地, ..., に読込まれ, 同時にアキュムレータの各ビットとXORをとってアキュムレータに戻す. 読み終わったとき, アキュムレータが0になるようにパリティビットがテープに入っている.
e1000桁は当時ポピュラーだったデモプログラムである. フリーランにして, クリアスタートでテープ読込みと計算が始まる.
このプログラムは460の階乗分の1までで計算するが, 4回分を一度にまとめて計算するので, インディケータの規則的な繰り返しが115回で計算は終了. その後は結果の二進十進変換になる. このプログラムはR0を壊さないから, 次のデモはR0の再読込みなしで始められる.
factorize31は 231-1, 231-3, 231-5,...231-19を素因数分解するデモプログラムである. このテープは入力サブルーチンのテープを読込んだ後, 停止するから, フリーランをクリックし, リスタートしなければならない. 結果は以下のようになる.
2147483647.=2147483647. 2147483645.=5.19.22605091. 2147483643.=3.715827881. 2147483641.=2699.795659. 2147483639.=7.17.18046081. 2147483637.=3.3.3..13.6118187 2147483635.=5.11.337.115861. 2147483633.=5843.367531. 2147483631.=3.137.263.19867. 2147483629.=2147483629.
最初と最後が素数であり, 特に最初はMersenne素数である. 231の平方根 46340までの疑似素数で割ってみる. 割る値がRレジスタに見えている. 46340は八進法では132404なので, Rレジスタの中央より右が132000くらいになると素数でも計算は終了する.
このデモプログラムはR0を破壊するので, 次のデモの前にはR0を再読込みする必要がある.
eratosthenesの篩 256から11327までの素数を篩で探す. 篩には36ビット長語の32ビットを使い, 残りの4ビットには疑似素数の差を保持する.
最初3で篩い, 次に5で篩い, ..., 11327の平方根106で篩うまで篩えばよいのだが, このプログラムは, 疑似素数の差の循環時に終了テストをするから, 231(八進で347)になるまで篩う. 篩う数はRレジスタに見え, 篩う数が大きくなると, 篩うのに要する時間短くなるのが分かる.
篩終わると, 出力ルーチンが読込まれ, 結果の1315個の素数を持つ素数表257. 263. ... . 11321. が印字される. このデモプログラムはR0を破壊しない.
Lucas Lehmerテスト ある素数pについて, Mp=2p-1が素数の時, MpをMersenne素数という. この素数性を調べるLucas Lehmerテストというのがある. s0=0, sn=sn-12-2(mod Mp)を計算し, sp-2=0(mod Mp)ならMpは素数である.
デモプログラムlucas lehmerはp=2,3,...,199の素数について, Mpの素数性をしらべ, 素数ならpを, 合成数ならcを印字する.
最後まで実行すると相当時間がかかるので, 適当なところで中断しよう. PC-1が活動していた頃, 分かっていたMersenne素数はM3217くらいまでであった.
デモプログラムはplayground.iijlab.net/~ew/pc1sim/{e1000, factorize31, eratosthenes, llt}で見られる.
これらのシミュレーションは50年前の実機より格段に速い. しかしネオン管の明滅は当時を彷彿とさせる. 最近のCPUはブラックボックスになって, なにがどうなっているか分からないが, 当時はこのようなインディケータを眺めて計算の進行状況を知り, 一喜一憂していたものだ. 出力も印刷電信機で, 大きな音をたて, 机をゆさゆさ揺らしながら, 文字を出力していた. あれから半世紀が過ぎた.
2012年4月22日日曜日
再帰曲線
東京大学新聞に2012年度後期日程入試問題が掲載されていた. その総合科目IIにフラクタルの絵があった. 問題はフラクタル次元を計算するものだが, 私としてはその絵を描くプログラムに関心があった.
まず図はこういうものだ.
左からF1, F2, F3
左からG1, G2, G3
問題に記述はこうだ.
はじめに, 1辺の長さ1の正方形をF0とする. F0を, 1辺の長さ1/3の9個の小正方形に分割し, 中央の小正方形を取り去ったものをF1とする. また, それぞれの小正方形を1辺の長さ1/3のユニットと呼ぶ. 次に, F1 を構成する8個のユニットのそれぞれについて, これを9個の小正方形に分割し, そこから中央の小正方形を取り去ったものをF2とする. また, この分割で得られたそれぞれの小正方形を1辺の長さ1/9のユニットと呼ぶ. 以下, 同様の操作を繰り返して得られる図形をF3, F4, ...とする.
PostScriptのこのプログラムは次のようだ.
まず全体の次数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の正方形G0を, 1辺の長さ1/2の正方形ユニット4個に分け, 右上のユニットについては, 左下の1辺1/4の正方形を取り去る. こうして得られた図形をG1とする. 次に, 残った3個の, 欠陥のないユニットのそれぞれについて, 同様の操作を行なう. すなわち, それぞれを4個の1辺の長さ1/4のユニットに分け, 右上にユニットについては左下の1辺の長さ1/8の正方形を取り去る. 得られた図形G2とする. 続いて, G2に含まれる1辺の長さ1/4の, 欠陥のない各正方形ユニットについて, 同様の操作を行なう. 得られた図形をG3とする. これを繰り返して得られる図形の列をG1, G2, G3, ...とする.
目で見ると簡単だが, 欠陥のない正方形をどう判定するか.
私の考え方はこうだ.
各正方形を4区画に分け, 左下, 右下, 左上, 右上の順に下請けに渡すとする. G0を描く手続きをaとすると, 1/2のサイズで, a,a,aと3回呼び, 最後に左下を取り除いた正方形を描く手続きbを呼ぶ.
aはnを1減らして, a,a,a,bと呼べば良い. bはnを1減らし, 左下を除いて, a,a,aと呼べば良い. そう考えて書いたのが, このプログラムだ. 上のプログラムが理解出来れば, こちらも分かるだろう.
この結果, n=7で描いたのが, 下の図である.
PostScripでこういう図を描くのは思ったより易しい.
まず図はこういうものだ.
問題に記述はこうだ.
はじめに, 1辺の長さ1の正方形をF0とする. F0を, 1辺の長さ1/3の9個の小正方形に分割し, 中央の小正方形を取り去ったものをF1とする. また, それぞれの小正方形を1辺の長さ1/3のユニットと呼ぶ. 次に, F1 を構成する8個のユニットのそれぞれについて, これを9個の小正方形に分割し, そこから中央の小正方形を取り去ったものをF2とする. また, この分割で得られたそれぞれの小正方形を1辺の長さ1/9のユニットと呼ぶ. 以下, 同様の操作を繰り返して得られる図形をF3, F4, ...とする.
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の正方形G0を, 1辺の長さ1/2の正方形ユニット4個に分け, 右上のユニットについては, 左下の1辺1/4の正方形を取り去る. こうして得られた図形をG1とする. 次に, 残った3個の, 欠陥のないユニットのそれぞれについて, 同様の操作を行なう. すなわち, それぞれを4個の1辺の長さ1/4のユニットに分け, 右上にユニットについては左下の1辺の長さ1/8の正方形を取り去る. 得られた図形G2とする. 続いて, G2に含まれる1辺の長さ1/4の, 欠陥のない各正方形ユニットについて, 同様の操作を行なう. 得られた図形をG3とする. これを繰り返して得られる図形の列をG1, G2, G3, ...とする.
目で見ると簡単だが, 欠陥のない正方形をどう判定するか.
私の考え方はこうだ.
各正方形を4区画に分け, 左下, 右下, 左上, 右上の順に下請けに渡すとする. G0を描く手続きを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でこういう図を描くのは思ったより易しい.
2012年4月11日水曜日
太陽太陰暦
英語ではlunisolar calendarというらしいから, 日本語とは順が反対だが, 太陰太陽暦でもいいようだ.
要するに月齢に合わせて月を決めるが, ときどき閏月をおいて, 季節を合わせる. その規則はどこにでも見つけることができる.
• 新月の起きる日を, 新しい月の朔日(ついたち, 1日)とする.
• 24節気のうち, 太陽の黄経が30度の倍数になる中気に各月を対応させる. 中気の対応しない月を閏月とする.
昔の本を読むと, 春一月, 夏四月, 秋七月, 冬十月と書いてあるが, 旧暦では1, 2, 3月が春, 4, 5, 6月が夏, 7, 8, 9月が秋, 10, 11, 12月が冬である. その各月に中気が対応し, 中気のない月が閏と書いてあるから, 手元の天文年鑑を見ながら計算してみた.
新月と節気の日付と時刻を順に書いてみると,
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でもっと勉強する必要がある.
要するに月齢に合わせて月を決めるが, ときどき閏月をおいて, 季節を合わせる. その規則はどこにでも見つけることができる.
• 新月の起きる日を, 新しい月の朔日(ついたち, 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でもっと勉強する必要がある.
登録:
投稿 (Atom)
