The Art of Computer Programming を読む(2)

前回の続き。

今日は1.3.1の演習問題から。

16.

メモリセルの0000-0099をすべてゼロに初期化する問題。(a)コードが短いプログラムと(b)実行時間が短いプログラムがそれぞれ求められている。

(a)
STZ命令とMOVE命令を使う。MOVE命令は、rI1で指定された場所に、Fで指定された数のワードを動かす。Fは1バイトなのでMIXの規格上63以下しか入れられない。ということでMOVE命令を2回呼ぶ必要がある。

 STZ 0
ENT1 1
MOVE 0(63)
MOVE 0(36)

(b)
MOVE命令は、1uに加えて移動回数*2uの時間がかかり、MOVE命令の1uだけ余計にコストがかかってしまう。一番早いのは、STZを100回呼んでやることである。これが200uで最短。

STZ 0
STZ 1
...
STZ 100

17.

今度はメモリセルの0000からNまで (0≦N≦2999) を初期化するプログラム。NはrI2に入っている。
STZのアドレス修飾をメモリアドレスの走査に使うことになる。

単純に考えると、
1. インデックスを初期化
2. インデックスの番地のメモリをゼロで初期化
3. インデックスをインクリメント
4. インデックスの番地がrI2より大きくないか比較
5. 大きければ終了。大きくなければ2に戻る
となろう。
これを愚直に書くとこちら。CMP系命令は、必ずレジスタの値とメモリの値の比較になるため、比較用にrI2をメモリの3100番地にロードしている。

3000  LD2 31300
3001 ENT3 0
3002  STZ 0,3
3003 INC3 1
3004 CMP3 3100
3005   JG 3002

…とまあこんな感じになったのだが、Knuth先生の答えを見て自分の頭の固さを嘆くことに。

3000  STZ 0,2
3001 DEC2 1
3002 J2NN 3000

rI2をデクリメントする、という方法があったか!
しかも、負の場合ジャンプするという命令を使うことで、比較命令も省略できている。これが文句なく(a)一番コードが短いプログラムだ。

(b)一番実行時間が短いプログラムは省略。(a)は、STZが2u, DEC2, J2NNが1uずつなので、合計4uがN回繰り返されるため4Nuとなるはず。Knuth先生の答えを見てもこれより短くなっているのか、そもそも期待通り動くのかもぱっと見ではわからない。次回までに調べておく。

次回は、演習問題の18と私がしていた勘違いについて。そして演習問題26のGOボタンに取り掛かろうと思う。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

ksk

哲学者でも科学者でもない素人が、哲学とか科学とか科学哲学とかを考えながら本を読む。

TAOCP読書メモ

Donald E. Knuth博士の The Art of Computer Programming の読書メモ。 アスキードワンゴ社から出ている日本語訳を読んでいます。 https://asciidwango.jp/post/122327235600/the-art-of...
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。