年のうちの春

古今集に「年のうちに春は来にけり一年を去年とや言はむ今年とや言はむ」という和歌がある. 旧暦の正月になる前に立春が来たということで, これだけ読むとこの現象は珍しいのかと思いがちであるが, 旧暦の月名の決めかたからすると, 立春 < 旧正月となる確率は1/2程度である.

旧暦の1ヶ月は天体の月の朔から次の朔の前日までの約30日で, 冬至を含む月を11月とする. 従って冬至が11月のちょうど中間にあると, 翌月の12月の終りまで45日あり, そこが丁度立春になるから, 立春と旧正月が一致するわけだ.

冬至が11月の真ん中より前半に来ると, 立春は12月末より前で, 12月中に来ることになり, 年のうちに春が来てしまう.

そこで2000年から2019年までの旧正月の日付を調べてみた.

    2000 2/5  〇
    2001 1/24 
    2002 2/12 〇
    2003 2/1
    2004 1/22
    2005 2/9  〇
    2006 1/29
    2007 2/18 〇
    2008 2/7  〇
    2009 1/26
    2010 2/14 〇
    2011 2/3
    2012 1/23
    2013 2/10 〇
    2014 1/31
    2015 2/19 〇
    2016 2/8  〇
    2017 1/28
    2018 2/16 〇
    2019 2/5  〇

この〇印が旧正月が立春2/4より遲い年である. 19年のメトン周期に10回あるから, 半分という確率は大体合っていた. なお上の表から1年立つと11日早まるのも読み取れる.

15パズル

先日のブログは15パズルを手で解く方法であった. 今回は計算機でやる話だ. 計算機による解法もいろいろあるが, とりあえずはプログラムを簡単にするという方針でいく.

下に14枚の図がある. これらはどれも4×4の15パズルの盤面の右下の3×3の部分を表している. その証拠はますの左上に斜体の数字で示す番地だ. まず図Aを見てほしい. 数字の代りに文字の変数でこまを示す. 空白のますには文字も書かない. 図Aの下にあるuldrはこれからこまを移動する方向である. 従ってまずgを上げる. hを左へ寄せる. eを下げる. gを右に寄せる. その結果が図Bだ. その矢印が示すように, 10,11,14,15の中でg,e,hが右回転したことになる. ほかのこまには影響しない.

この手順を右回転, 10,11,14,15の4ますを主戰場ということにする.

さて主戰場以外の場所のpを14に移動し(この時ほかのこまに影響があってもよい), 右回転し, 14のこまをpにもどすと(影響はもとに戻って), 15にあったものがpに, pが11に, 11が15に移動したことになる.

p→11,11→15;15→p



どこかのこまを14に移動するには, 図C,Dに見るように, Cでurddluを実行する. するとDのように, 14,13,9,5,6のこまが左大回転する. gが2度のuで2段上に登るのは, 10に空白を残すためである.

ここで主戰場の右回転すると, Eになり, 先程の左大回転を逆回転するとFになって, f,e,hが回転する.

Gからの図では左大回転を2回実行し, 右回転, 右大回転2回で, d,e,hが回転することが分る. Kからの図は先に右大回転をすると, b,e,hが回転することを表す. ここには図がないが, Kの大回転を2回ずつ実行すると, a,e,hが回転することは容易に分る.

以上で5,6,9,13との交換はできたが, ほかの場所との交換は, 大回転の道順を工夫すればよいのも明らかだ. それが次の図である. 上の道順はルート0のつもりで, 左上のrt0である. 6のますに1, 7のますに2とあるのは, それぞれ右大回転を1回, 2回行うという意味だ. 9と13の2と1は左大回転の2回と1回を示す.

これを見れば, 主戰場の外のすべてのますを14へ移動する方法が分る.

   



これをまとめたのが以下で, 最初のrotは右回転, 続くrt0+, rt0-などはrt0の左大回転と右大回転である.
 

  
rot uldr
rt0+ urddlu
rt0- duuuld
rt1+ urrddllu
rt1- drrulld
rt2+ urrddluu
rt2- ddruuuld
rt3+ urdddlluru
rt3- dldrruuuld
rt4+ urrdddlluu
rt4- ddrruuulld

以下はpを11,15と交換する手順を, rtpで示したもので, 例えば左上の0との交換には, 上の図のrt4を4回転するから, rt4-が4回, その後, 右回転, 更にrt4+を4回を示している. rt10,11,14,15がないのは, そこが主戰場だからだ.

rt0 rt4- rt4- rt4- rt4- rot rt4+ rt4+ rt4+ rt4+
rt1 rt2- rt2- rt2- rot rt2+ rt2+ rt2+
rt2 rt2- rt2- rot rt2+ rt2+
rt3 rt3- rt3- rt3- rot rt3+ rt3+ rt3+
rt4 rt1- rt1- rt1- rot rt1+ rt1+ rt1+
rt5 rt0- rt0- rot rt0+ rt0+
rt6 rt0- rot rt0+
rt7 rt3- rt3- rot rt3+ rt3+
rt8 rt1+ rt1+ rt1+ rot rt1- rt1- rt1- 
rt9 rt0+ rt0+ rot rt0- rt0-
rt12 rt1+ rt1+ rot rt1- rt10
rt13 rt0+ rot rt0-

この準備が出来ると, ランダムな配置から元へ戻すことが可能になる. 前回のブログのランダムの例から戻す手順をやってみたのが以下だ.

まず左上0の直ぐ下がランダムな状態で, その下へ進んで(sp10)は空白を10へもっていく命令を実行したところである. 命令の後の1は時間順を表す.

この状態の右下15をみると9のこまがあり, これを8に戻したいから(rt8)を行う. (rt8)2の後のように, こま9は場所8へ移動している. そして10が15に来たから, 次は(rt9)を行う. そして10は9へ入る. 次は13だから(rt12), 次は12だから行先は主戰場の中だ. 従って(rot)をして主戰場の中を回転する. すると8が15に来る. そこで(rt7)を実行して8を7に入れた. これで左端の列は終り, 2列目へ.

2列目は順調に進行する. 3列目の中程, (rt0)で1を左上へ移動すると, 主戰場は11, 12, 15になり, rotしても様子は変らない. この場合はこまの並びで自分の場所にいないものを探す. するとこま4が1にいるから(rt1)を行い, 4を主戰場へ取込み, 1拍おいた後に3へ送る準備をする. それが時間番号でいうと, 18,19,20になる.

このように進んで, 22までくると, 主戰場以外はすべて揃ったので, 後は適当な回数の(rot)を実行し, 右下隅に12が来たら(l)(u)を行い, 最後を揃えて終わる. これをプログラムに書き直すのは簡単だ.

0             (rt2)7        (rot)14       (rot)21        
                              
  7  4 11  2    7  4  3  2   11  4  3  2    1 15  3  4
 15  1 14 __   15  1 14  8    5  1  7  8    5  6  7  8
 13 12 10  5    9 10 __ 11    9 10 __ 12    9 10 __ 11
  8  6  3  9   13  6 12  5   13 14 15  6   13 14 12  2
                                                 
(sp10)1          (rt4)8        (rt5)15      (rt1)22          
                                                 
  7  4 11  2    7  4  3  2   11  4  3  2    1  2  3  4
 15  1 14  5    5  1 14  8    5  6  7  8    5  6  7  8
 13 12 __ 10    9 10 __ 15    9 10 __  1    9 10 __ 15
  8  6  3  9   13  6 12 11   13 14 15 12   13 14 12 11
                                                 
(rt8)2          (rt0)9        (rot)16      (rot)23          
                                                 
  7  4 11  2   11  4  3  2   11  4  3  2    1  2  3  4
 15  1 14  5    5  1 14  8    5  6  7  8    5  6  7  8
  9 12 __ 13    9 10 __  7    9 10 __ 15    9 10 __ 12
  8  6  3 10   13  6 12 15   13 14 12  1   13 14 11 15
                                                 
(rt9)3          (rot)10        (rt0)17      (rot)24          
                                                 
  7  4 11  2   11  4  3  2    1  4  3  2    1  2  3  4
 15  1 14  5    5  1 14  8    5  6  7  8    5  6  7  8
  9 10 __ 12    9 10 __ 12    9 10 __ 11    9 10 __ 11
  8  6  3 13   13  6 15  7   13 14 12 15   13 14 15 12
                                                 
(rt12)4          (rt6)11        (rt1)18      (l) (u)25     
                                                 
  7  4 11  2   11  4  3  2    1 15  3  2    1  2  3  4
 15  1 14  5    5  1  7  8    5  6  7  8    5  6  7  8
  9 10 __  8    9 10 __ 14    9 10 __  4    9 10 11 12
 13  6  3 12   13  6 15 12   13 14 12 11   13 14 15 __
                                   
(rot)5          (rot)12        (rot)19        
                                   
  7  4 11  2   11  4  3  2    1 15  3  2
 15  1 14  5    5  1  7  8    5  6  7  8
  9 10 __  3    9 10 __ 15    9 10 __ 12
 13  6 12  8   13  6 12 14   13 14 11  4
                                   
(rt7)6          (rt13)13     (rt3)20        
                                   
  7  4 11  2   11  4  3  2    1 15  3  4
 15  1 14  8    5  1  7  8    5  6  7  8
  9 10 __  5    9 10 __  6    9 10 __  2
 13  6 12  3   13 14 12 15   13 14 11 12

最後に一言. これはプログラムをさぼるという方針のため, 実際にこまを動かす回数は膨大になっている. 人手向きではないことに注意が必要だ.

15パズル

15パズルというのは, Rubikキューブよりほぼ百年前に登場した, Rubikキューブと同じ置換パズルである. しかし, Rubikキューブにくらべれば, 解くのははるかに簡単である.

置換パズルについてはそのうち説明るすることにし, 15パズルは下の図のようなものだ. 1から15までの数を書いた正方形のこまが, 16枚収まる正方形の枠に入っている. 図のAのように左上から右下にかけて, 1から15のこまが並び, 最後が1箇所空白になっている. これを整列状態をいおう. 空白に隣接したこまは空白の方向へ滑らせて移動でき, 移動した後が空白になる.

図のBは12のこまを下へ移動したところ; Cは11を右へ移動したところである. このように空白へ隣のこまを移動することで, ランダムになったある状態(例えば図のD)から出発し, こまを上下左右に移動することを繰り返すだけで, 整列状態へ戻すパズルである. こまの色は整列した場所の色としては意味があるが, こま自身の色には意味はない.


  

少しやってみると, すぐに出来るようになるが, 難しい場所もある. 人手でやる場合の戻し方の要領を次の図に示す. こまを上へ動かす, 右へ動かすという代りに, 15パズルの世界ではu, rのように書く. 下, 左はd, lである.



Aはこまのある場所を示す番地の図だ. 番地は以下の文では斜体で書く.  こま1の場所が0なのはややこしいが, とにかくこのように番号をつける. まず0から15の場所から1のこまを探し出し, それを0へ移動してBにするのは簡単だ. 次に2のこまを1へ移動するとCになる. これもなんでもない.

3を2へ入れるのは多少問題で, その時4が3にあればめでたいが, 4以外のものがあるところへ4を入れようとすると, 3に影響が及ぶ. 解決法は3と4をひとまとめにして収めることである. Dのように4を2に入れ, 3には3以外のもの(今はそれをxとする)があるとして3を7に置く. 空白は6に移動しておく.

4を下げ, xを左へ, 3を上, 4を右に動かす. つまり図の下にあるように, dlurを実行すると, Eの図になる. 続いてxを下げ, 3を左, 4を上に動か  すとFのように3と4が収まるのである.

運悪く3の位置に3がある時は, 図のG,H,I,Jのように動かす. Gの下に示すdruを実行すると, Hの図になり, 4と3が縱に並ぶ. この4と3を離したいから, Hの下のuldrでI, 4と3の間にyが闖入した. その下のdluでJ, その下のurdでDの図になる.

この下の段も同じ要領で, 5,6,7,8が収まる. しかし次は9,10,11,12を揃えるのではなく, 9,13を3,4の方法で入れる. さらに10,14も同様にして入る. すると最後は10,11,14,15に11,12,15が残るので, 10に11が来るまでぐるぐる回せば完成である.

15パズルは整列状態からこまを適当に滑らせてランダムにしてみても, そうランダムにはならない. かといって全部のこまをとりだし,バラバラに箱詰めしても, 整列状態には戻らない配置になる可能性がある.


遊んでみるためには, 私の作った下の図のようなのがhttp://www.iijlab.net/~ew/15puz190202.html
にある.
 


空白の隣のこまをクリックすると, そのこまが空白の方向へ移動する. 下のClrをクリックすると整列状態になり, Ranをクリックするとランダムになる.

e1000桁の計算

60年くらい前によく行われていた, Napier's constant eの値を1000桁計算するパラメトロン計算機PC-1のプログラムについてのファイルがあったので, 私のブログに載せておくことにした.

自然対数の底 e の値を小数点以下1000桁まで計算することは,1960年代の計算機で流行した. Taylor展開

e = 1 + 1/1! + 1/2! + ... + 1/n!

で計算するのだが, n = 460くらいで1000桁の精度がある.
   
実際には上の式で計算するのではない.

e = 1 + 1/1(1 + 1/2(1 + 1/3(1 + ... +1/459(1 + 1/460)...)))

を使う. さらに例えば4項ずつまとめて計算することを考える.

Q_a-4 = 1 + 1/(a - 3)(1 + 1/(a - 2)(1 + 1/(a - 1)(1 + 1/a・Q_a)))

a = 460, 456, 452, ... 0

Q₄₆₀ = 1

e = Q₀

これはさらに簡単になって

Q_a-4 = {a(1 + (a - 1)(1 + (a - 2)(1 + (a - 3)))) + Q_a}

/{a(a - 1)(a - 2)(a - 3)}

しかし 460×459×458×457 = 44192868840 となり, 36ビットのPC-1のレジスタの容量2³⁵ = 34359738368には収まらない. 連続する4個の整数の積は4で割れるから, 2ビット右シフトして計算すれば, この問題は解決する.以下のプログラムはそのようにしてeの値を計算している.

次は10進数での出力である. 小数を10進法で出力するには, 全体を10倍し,整数部分にでた数を印字する. これでは乗算に時間をかけて1桁しか印字できないので,以下のプログラムでは, 小数部分に一度に10¹⁰をかけ,10桁分の整数部を作り出す. また多倍長の乗算を10区間に分割し,各区間毎に10桁の整数を1桁ずつ印字するようになっている.

作業場所は10進で1000桁なので, 3300ビット必要. PC-1の36ビットの長語を100語使う
(300〜498 300番地の方が小数点側).

作業場所は10進で1000桁なので, 3300ビット必要. PC-1の36ビットの長語を100語使う (300～498 300番地の方が小数点側).

0h=80,0i=100,0p=180,0n=272,0m=300,

70:
 0   it
 1   jl   h   作業場所クリアへ
 2   it
 3   jl   i   計算プログラムへ
 4   it
 5   jl   p   印字プログラムへ
 6   0

0h:
 0   a   8n ┐
 1   x  13r ┘ plant link
 2   p   2n
 3   x   7r
 4   s   3n
 5   z  11r
 6   l  35  　 アキュムレータを0に
 7   tl(  ) 　 作業場所をクリア
 8   p   7r
 9   a   8n
10  jl  3r
11   pl 16n 　 Q₄₆₀を1に
12   tl   m
13   jl(  )

0i:
 0   a   8n ┐ e1000桁計算ルーチン
 1   x   3r ┘ plant link
 2   pl 18n ┐
 3   zl(  ) ┘ a = 0なら帰る
 4   sl 16n 　 a - 1
 5   tl 20n 　
 6   sl 16n 　 a - 2
 7   tl 22n 　
 8   sl 16n 　 a - 3
 9   tl 24n 　
10   vl 22n 　 ×(a - 2)
11   ll 34  　
12   vl 20n 　 ×(a - 1)
13   ll 35
14   vl 18n 　 ×a
15   ll 34 　  a(a-1)(a-2)(a-3)
16   tl 26n 　 を26nLへ
17   p   2n
18   x  22r
19   x  25r
20   s   3n
21   z  29r
22   ql(  ) ┐
23   r  33  │ Qを4で割る
24   ll 33  │
25   tl(  ) ┘
26   p  22r
27   a   8n
28   jl 18r
29   pl 24n 　 a - 3
30   al 16n 　 + 1
31   vl 22n 　 x(a - 2)
32   ll 35
33   al 16n 　 + 1
34   vl 20n 　 x(a - 1)
35   ll 35
36   al 16n 　 + 1
37   vl 18n 　 x a, aは4の倍数なので
38   ll 33  　 最後の2ビットは0
39   al   m 　 Rレジスタは0
40   tl   m
41   p   2n
42   x  46r
43   x  48r
44   s   3n
45   z  52r
46   ql(  ) ┐ 多倍精度/単精度
47   dl 26n │ a(a-1)..(a-3)で割る
48   tl(  ) ┘
49   p  46r
50   a   8n
51   jl 42r
52   pl 24n
53   sl 16n
54   tl 18n
55   jl  3r

0p:
 0   a   8n ┐ 出力ルーチン
 1   x  68r ┘ plant link
 2   q  16n
 3   p   4n
 4   x   8r
 5   x  12r
 6   s   5n
 7   z  16r
 8   pl(  ) ┐ 　
 9   wl 12n │
10   tl 28  │ 1回目の10¹⁰倍
11   ql 28  │
12   tl(  ) ┘
13   p   8r
14   s   8n
15   jl  4r
16   p   4n ┐
17   tllt   │ 2. と印字
18   s  70r │
19   tllt   ┘
20   p   6n 　 20行用カウンタ設定
21   x   9n
22   p   7n 　 5ブロック用カウンタ設定
23   x  10n
24   z  65r
25   pl 28
26   tl 68
27   p    n 　 10¹⁰倍10回カウンタ
28   x  11n 　 初回は0に設定
29   q  16n
30   p   4n
31   x  39r
32   x  43r
33   s   5n
34   z  62r
35   p  11n
36   z  47r 　 10回カウンタを調べる
37   s  17n
38   x  11n
39   pl(  ) ┐
40   wl 12n │
41   tl 28  │ 10¹⁰倍
42   ql 28  │
43   tl(  ) ┘
44   p  39r
45   s   8n
46   jl 31r
47   ql 68  　 10¹⁰倍10回終り
48   tl 28  　 1文字 印字へ
49   p    n
50   dl 14n 　 10⁹で割る
51   l  18
52   a  56r
53   x  54r
54   p (  ) 　 文字コードを取る 
55   tllt   　 印字
56   q   2n 　 アドレス部分は52で使う
57   vl   n
58   ql 28
59   tl 68
60   p   1n
61   jl 37r
62   p  10n
63   s  17n
64   jl 23r
65   p   9n
66   s  17n
67   z (  ) 　 link
68   x   9n
69   p   8n
70   l  12  　 CR
71   tllt
72   l   2  　 LF
73   tllt
74   r   1  　 SP
75   tllt
76   tllt
77   jl 22r

0n:
 0   0       ┐
 1   10      ┘ 10(長語)
 2   229676   (0) 300 以下文字コード
 3   233972   (1) 500 と定数
 4   197106   (2) 498
 5   172332   (3) 300
 6   135188   (4)  20
 7   217093   (5)   5
 8   245762   (6)   2
 9   180224   (7) (  ) カウンタ
10   143360   (8) (  ) カウンタ
11   184320   (9) (  ) カウンタ
12   38146   ┐
13   254976  ┘ 10¹⁰ 
14   3814    ┐
15   182784  ┘ 10⁹
16   0       ┐
17   1       ┘ 1 (長語)
18   0       ┐
19   460     ┘ a (長語)
                この後27nまで作業場所
jl70.

PDP8のプログラム技法

前回のブログで基本ループの動くのは分ったが, calのプログラムを書くにはまだmon0, mon1のデータを用意する仕事がある. そのプログラムの話だ.

mon0は各月の1日の曜日が決ったとき, その週の最左端の枠, つまり日曜の日付けである. 1日の曜日の計算は月の定数にその年の定数と(日付けの)1を足す.

その年の定数は, 年の下2桁をyとして, (y+floor(y/4)+世紀の定数)%7である. 世紀の定数は, 年の上2桁を4で除した剰余の0,1,2,3について, それぞれ+4, +2, 0, -2である.

この辺までを計算するのが次のプログラムの000行から034行である.



000行はプログラムの200番地からの格納の指定. 001行はアキュムレータとリンクのリセット. 002,3行で1文字(1数字)を読みaへ置く. 009行までで4文字(4数字)を読み, 1000,100,10,1の各桁がa,b,c,dへ入る. 次のgetchは改行を読み, eへ入れるがこれはそれを捨てアキュムレータをクリアする.
 
012行からが上のy+floor(y/4)の計算. 016行まででcを10倍し, dを足す. それをeへ格納し, 20行までで2桁右シフト. それにeを足して計算完了.

024行からは上2桁の4で除した剰余をとる. それにはa+a+bを3でマスクする. 一旦fに入れ(028行), 031行までで剰余を5倍し, 世紀内の定数eを足しさらに033行で5を足す.

0,1,2,3から7を法として4,2,0,-2を作るのに, 5倍して4を足した. つまり4,9,14,19は7を法として4,2,0,-2だからである. 4を足すのではなく5を足すのは, 1日の分を足すからである. これをyconstに置く(034行.)

035行から051行は閏年の判定である.



まずcとd(下2桁)を足し, 和が0(100の倍数)ならhへ. そうでないならc+c+dを持ってjへ. hではa+a+bを持ってjで合流. これらが4の倍数なら閏年である. 3でマスクし, 0でなければ048行で-1を置き, 閏年なら049へスキップしてきて1増やすから, 閏年なら1が出来, 平年なら-1が1増えるから0が出来る.

050行は上の結果をマイナスにし, 051行でそれをmleapへ入れる.
 
これまででyconstとmleapが出来たので, mon0とmon1の表の修正を開始する.



修正はまず月の定数のうち, 1月と2月から1を引くのと, 月の日数のうち, 2月を1増やすことである. 052でmon0のアドレスをeに入れ, 054で1月の値を取り出し, mleapを足してもとへ戻す. iszでアドレスを増やし, 2月についても同様にする.

061行からは2月の日数の調整である. mon1の表は負数になっていたから, 2月の値から1引くわけで, それが065行だ.

mon0はyconstを足した(072行)のが1日の曜日であった. これからその月の最初の枠の日付けの計算に移る. 067行のm14は十進では-12のことで, 12回ループの準備をする.

この計算はmon0の値にyconstを足し, 7の法をとり(073行,) その後, 各月の1日の値がnなら, -n+1で置き換える. -nの操作が074行. 1足すのが075行である. これを実行すると, 前回のブログにあったmon0とmon1の表が得られる.

次の081行から097行は定数で, m7770, m7774はand命令で使うマスクビットである.


 
085行からのmon1は各月の日数だが八進法なのでちょっと異様にも見える.

098行からは1文字読込み(getch)と7の剰余をとるサブルーチン(mod7)である.



getchでは西暦の年号を読むだけなので, 数字のコードの八進260を引く.
 
mod7は法をとる披除数をアキュムレータに置き, 上9ビットをa, 下3ビットをbとし, aが0でなくなるまでaを3ビット右シフトしてbに足す操作を繰り返す. aが0になったらbからを引き, 結果が正, つまり0ならそのまま, 負なら7を足して戻る.

これでcalのブログラムの主要な部分は大体完成した.

PDP8のプログラム技法

私がいろいろなプログラム言語で書いたcalのプログラムは, unixのcalのコマンドで印刷されるのと同じものだ.

例えば

cal 2000

とすると, 2000年の12ヶ月のカレンダーが印字される.

こういうプログラムをpdp-8用に作るための工夫を書いてみたい.

かなり前のことだが, アメリカにJerry Weinbergという心理学者が活躍していて, 私も何回か会ったことがある. 当時プログラムを書くのにトップダウンがいいかボトムアップがいいかという無益な議論があった. その時Jerryが「難しいところから書く」を主張していて, 私と同じ考えの人がいると思った.

というわけで, 一番中心部分のプログラミングから始めよう. 見出しの類いはあとからゆっくり追加すればよい.

まずは各月の第1日の曜日と各月の長さが必要である.

このブログでも何度か述べたように, 1月から12月について次の表が重要になる. (ある月の定数は前の月の定数に前の月の日数を足し, 7による法をとったもの(と等価なもの)だ.）

 
 

1	2	3	4	5	6	7	8	1	9	10	11	12
2	5	5	8	3	6	1	4	1	7	2	5	0

この表とその年の定数から各月の0日の曜日が判る. 2000年の定数は4なので, 例えば2000年8月15日は(4+4+15)mod 7=2で火曜だ. 注意すべきは2000年が閏年だったので, 1月と2月はこの表から1引くことである. 従ってこの表は補正後は, 1,4,5,8,3,... のように始まる.

それに年の定数を足して7の法をとると, 5,1,2,5,0,... になる. すると1月1日は4+1+1=6で土曜である. 1日が土曜だと, 金曜が0, 木曜が-1, 水曜が-2, 火曜が-3, 月曜が-4, 日曜が-5に相当し, 1月の第1週は-5日から始まる. そこから1日ずつ増えて, 1になるのが土曜である. 従って次の図のmon0と書いた表の最上段(1月)に7773, つまり10000-5を入れる. mon0はこのように出来ている. 年の定数が変るとか, 年の定数が同じでも閏年であったりするから, この表の内容は年により違う.





右側にあるmon1の表は, 上から順に各月の日数の負の値である. 日付が順に増えてゆき, 日数を過ぎると表示を空白にしなければならず, それには日数を減算するが, PDP-8には減算がないので, 最初から負数にしてある.

最初のカレンダーの構造からわかるように, このプログラムは大局的には3ヶ月のカレンダーの4回の繰返しである. その1回分は, 1ヶ月の3回の繰返し; 1ヶ月は週の6回の繰返し, 週は日の7回の繰返しなので, 以下のプログラムは4重のループで出来ている.



00行はこのプログラムが八進の200番地から格納することを示す. 02行からmon0pの値をaへ, mon1pの値をbへ置く. 06行から4,6,3,7のカウンタを初期化する. 15行 aの指す内容(今は1月の先頭の日付け)の1未満を調べるため, アキュムレータに-1を置きmon0の値いを足す. それが負なら空白を出力するためl1へ. (0も-1に  なるので, 飛ぶ) 次にこの月の日数を引き(18行), 正になればこれも空白出力へ進む.

日付を出力できる条件を満すと, 21行からそれを出力し26行へ行き日付を進める. 日付の値は負から始まり, 正へ進むが, isz命令は0になった場合, 次の命令をスキップするから, isz命令の次にjmp .+1かnop(7000)を置く.

この後1週間分, つまり7回出力したかを見, そうなら次の月の1週目に進むから, aとbのポインタを進める(31,32行目.) 33行目はそれを3ヶ月やったかの確認で, 3ヶ月済むとまた左端の月に戻るので, 35行目からaとbを3ずつ減らす. これで1行出力したから, 改行する(41行目.)

42行めは6週間のテスト. 市販のカレンダーでは1日が金曜か土曜だと, 30日や31日は23日や24日と一枠を共有するが, calではそうせず, 次の行にするので, 1ヶ月は最大6行になる. その6行が終ったかを調べる.

それが終わると続く3ヶ月に移るので, 44行目からは, aとbを3増やす段取りだ.

 

53行目からは定数や作業場所, 基本的なルーチン類になる. 54行, 57行が上の図のmon0とmon1である. 59行からはカウンタの初期値, 64行からのa, b, c, d, e, fが作業場所になる.

このプログラムの出力が以下だ. 横7文字目, 14文字目の次に縦線を引き, 6行, 12行, 18行の下に横線を引くと, 最初のカレンダーと同じ情報が得られる. 1日がA, 2日がB, 26日がZだから, アルファベット各文字が何番目かを熟知しているひとには, カレンダーとして十分役立つと思われる(^^).

@@@@@@A@@ABCDE@@@ABCD
BCDEFGHFGHIJKLEFGHIJK
IJKLMNOMNOPQRSLMNOPQR
PQRSTUVTUVWXYZSTUVWXY
WXYZ[\][\]@@@@Z[\]^_@
^_@@@@@@@@@@@@@@@@@@@
@@@@@@A@ABCDEF@@@@ABC
BCDEFGHGHIJKLMDEFGHIJ
IJKLMNONOPQRSTKLMNOPQ
PQRSTUVUVWXYZ[RSTUVWX
WXYZ[\]\]^_@@@YZ[\]^@
^@@@@@@@@@@@@@@@@@@@@
@@@@@@A@@ABCDE@@@@@AB
BCDEFGHFGHIJKLCDEFGHI
IJKLMNOMNOPQRSJKLMNOP
PQRSTUVTUVWXYZQRSTUVW
WXYZ[\][\]^_@@XYZ[\]^
^_@@@@@@@@@@@@@@@@@@@
ABCDEFG@@@ABCD@@@@@AB
HIJKLMNEFGHIJKCDEFGHI
OPQRSTULMNOPQRJKLMNOP
VWXYZ[\STUVWXYQRSTUVW
]^_@@@@Z[\]^@@XYZ[\]^
@@@@@@@@@@@@@@_@@@@@@

PDP8のプログラム技法

今から50年程前にDEC(Digital Equipment Corporation)が発売していたPDP8というミニコンがあった. 思うにこれはMITのTX-0を源とする似たようなアーキテクチャの計算機である.

簡単に概要を示すと, 1語は12ビット, 記憶装置は12ビットの4096語. 1ページが128語の32ページで構成される.

演算装置の中心は12ビットのアキュムレータで, 2の補数(4096の補数)で演算される. アキュムレータの左に1ビットのリンクがあり, 加算の結果繰上がりがあると, リンクのビットは反転される. アキュムレータのシフトは回転シフトであり, リンクを経由する. アキュムレータのクリアはリンクに影響しない.


図の2段目は記憶装置参照命令で12ビット. 下の図のような構成である.

左端の3ビットが命令コード. 右端の7ビットがページ内アドレスである. ビット4が0の時は第0ページの番地を示し, 1の時はその命令のあるページ内でのアドレスを示す.

ビット3が1の時は, その語の内容を番地とする.

記憶場所の八進法で0010から0017までの場所を間接番地で参照すると, この番地の内容を1増やしてから使われるから要注意である.
 
記憶場所参照命令は, 命令コードの0から5が次のようである.

0 AND
1 TAD  
2 ISZ
3 DCA
4 JMS
5 JMP

ANDは番地の指す記憶場所の内容とアキュムレータのビット毎のANDをとり, 結果をキュムレータに置く.
 
TADは番地の指す記憶場所の内容をアキュムレータに加える. 繰上がりはリンクを反転する.

ISZは番地の指す記憶場所の内容を1増やし, その結果が0になれば, 次の命令をスキップする.

DCAはアキュムレータの内容を番地の指す記憶場所に入れ, アキュムレータをクリアする.

JMSはこの命令の次ぎの番地を番地の指す記憶場所に入れ, その次の命令に進む. つまりサブルーチンジャンプする.

JMPは番地の指す記憶場所の命令に進む.

命令コード6は入出力命令で, テレタイプのキーボードから読んだり, プリンタに印字したり, 紙テープリーダから読み込んだりする. この話しは省略する.

命令コード7はマイクロプログラム命令で, 図に示すようにビット3の0, 1に従って, グループ1とグループ2とがある.

グループ1はビットの4,5,6,7が1だと, アキュムレータをクリア(CLA), リンクをクリア(CLL), アキュムレータの各ビットを反転(CMA), リンクを反転(CML)する.

ビット8, 9はアキュムレータとリンクを繋げた左(RAL)または右(RAR)回転で, ビット10の0/1に従って1ビットか2ビット(RTL, RTR)になる. ビット11が1だと, アキュムレータを1増やす(IAC).

マイクロプログラムでは実行順が重要である. 最初がクリア, 次が反転, 次がIAC, 最後が回転となる.

グループ2は, ビット4が1の時アキュムレータのクリア(CLA), ビット5,8が1,0の時アキュムレータの負(ビット0が1)でスキップ(SMA), 1,1の時アキュムレータの正でスキップ(SPA). ビット6,8が1,0の時アキュムレータの=0でスキップ(SZA), 1,1の時アキュムレーの≠0でスキップ(SNA). ビット7,8が1,0の時リンクの≠0でスキップ(SNL), 1,1の時リンの=0でスキップ(SNL)である.

ビット9が1の時, コンソールの12ビットのスイッチをアキュムレータとビットごとORする. ビット10が1の時計算機を停止する(HLT).

実行順はまずスキップ, クリア, スイッチ読込みと停止である.

プログラムでは, CMA IACのように書くだけである. こう書くとアキュムレータがビット反転され, 1足されるので, アキュムレータの値を負にする. PDP8には減算命令はなく, A-BはBをアキュムレータに置き, CMAで1の歩数を取ってからIACで1を足す.

ところでPDP8ではプログラムは原則八進法で書く. 格納開始番地は星印(*)を使い

*200

のように書く. 記号アドレスの定義は

start,

のようにコンマ(,)を使う. 命令のアドレス部には記号アドレスや, この命令の番地を示すピリオド(.)や, プラス, マイナス(+, -)に数を続ける.

斜線(/)はコメントの開始を示す. プログラムの最後には($)を書く.

例えばアキュムレータにある正を数を十進法の10で割り, 商をq, 剰余をrに置くサブルーチンdiv10を八進の100番地からに入れるには

*100
div10,0  /サブルーチンの入口. 帰り番地が入る
dca r    /披除数をrに入れる
dca q    /商の場所qをクリアする
tad r    /部分剰余をアキュムレータに置く
tad m10  /10を引く
spa      /剰余が正ならスキップ      
jmp .+3  /負になったので後始末へ
isz q    /剰余を1増やす
jmp .-4  /4命令前へ戻る
tad p10  /引き過ぎた剰余を戻す
dca r    /剰余をrに入れる
jmp i div10 /主プログラムへ戻る
m10,-12  /定数 -10
p10,12   /定数 10
r,0      /剰余の場所
q,0      /商の場所

のように書く.

PDP8はこの程度の計算機だから, シミュレータやアセンブラを書くのも簡単だ. 今回PDP8を説明したのは, 私がいろいろなプログラミング言語で書いている例題, 与えられた年のカレンダーを出力するcalをPDP8でも書くためである.

それはまた次回に.