Fuzix-Compiler-Kitの6800用コンパイラ(2)(ベーシックマスター開発 その34)

BASICMASTER, 昔のパソコン

Fuzix-Compiler-Kitの6800用コンパイラ(ベーシックマスター開発 その33) | ず@沖縄の続き。

まだまだ機能は足りないし、バグもあるようだけど、ある程度動くようになった。

どんなプログラムが動くのか

騎士巡歴問題が解けるようになりました。エミュレーターによると、解を一つ見つけるまで 157,440,530サイクルかかりました。

ベーシックマスター実機は クロック754.56KHz(1.325μs/cycle)※1ですので、209秒(3分29秒)になります。

さらに1/60秒ごとのタイマー割り込みと画面表示のオーバーヘッドがかかるので、実機だともう少し時間がかかるはずです。

騎士巡歴問題を解くプログラムはJavascript版をCに書き換えて動かしています。

なお、そのままでは時間がかかりすぎるので盤サイズを16×16にし、コンパイラにも2の累乗の除算は左シフトにする最適化を追加しています。
(シフトに変換しないと281,169,530cycle,372秒かかります)。

さらにtest関数に、隅に行ける時は必ずそこに行く枝刈りを追加しました。

※1 「ベーシックマスターを拡張した 汎用ラボラボオート・システムの製作」インターフェース1980年2月号No.33 p.64
※2 Kinx アルゴリズム – 騎士巡回問題 #JavaScript – Qiita

$ ./emu6800 -d 6800 tests/9006-knight tests/9006-knight.map

Solution 1
 1 64 49 22 37 18  9 20 
48 53 38 33 10 21 36 17 
63  2 31 50 23 34 19  8 
54 47 52 39 32 11 16 35 
43 62  3 30 51 24  7 26 
46 55 44 59 40 27 12 15 
61 42 57  4 29 14 25  6 
56 45 60 41 58  5 28 13 
count=64
0



BASICMASTERエミュレーター(j68)で拙作のGAMEコンパイラでコンパイルしたプログラムを動かすと87.18秒で最初の解が表示されます。

こちらが2.4倍速いです。

プログラムはASCII誌掲載のGAME版※3に 枝刈りを追加したものです。

※3 ASCII 1978年12月号 p.28



速度差の原因は?

書いていたら長くなったので、解説は次回に回します。

リンク