Fuzix-Compiler-Kitの6800用コンパイラ(2)(ベーシックマスター開発 その34)
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
速度差の原因は?
書いていたら長くなったので、解説は次回に回します。
ディスカッション
コメント一覧
まだ、コメントがありません