NandGame が面白過ぎて年末年始ハマった その３

NandGame やっていき

せっかく前々回、前回とやってきたので、引き続き NandGame をやっていこうと思う。
ちなみに、今回もバリバリネタバレ全開なので、まさかいないとは思うが万一まだゲームをやっていない方は是非コンプリートしてから読んで欲しい。

Arithmetic Logic Unit

算術論理演算装置である。たいていは ALU と略されていると思う。コンピュータ（電子計算機）の計算機たる所以と言っていいのではないか。（てきとー

Unary ALU

単項 ALU である。まず z によって入力をゼロにするか否かが決まり、次に n によって反転するかどうかが決まる。
手始めに素直に構成してみる。

144 Nand である。まぁここからだ。
まずは Selector 16 だ。自作部品の Selector 16 に切り替えれば Nand 数を減らせるはずだ。

絵面は汚らしいが正解、114 Nand だ。
何やらよくわからない Nand があるのは、あろうことかツールボックス内に Inv が無いため、やむを得ず Nand で代替したからだ。
まだいける。最初の Selector 16 は z が 1 の場合に出力をゼロにするために使用している。
ここで z の inv を考えてみれば、$\bar{\rm z}$ が 1 の時には入力をそのまま出力し、$\bar{\rm z}$ が 0 の時にはゼロを出力する事になる。これってつまり And では？
と言うわけで、Nand を 16 個束ねた自作部品を作る。名前は mask inv 16 だ。

なぜ And じゃなくて Nand なのかと言うと、どうせ既に inv 16 を使用しているので、自作部品の中に inv 16 に相当するものを組み込んでで無駄に Nand 数を増やしたくないからである。
で、これを使って先ほどのものを再構成する。

オーケー、これで 82 Nand である。
mask inv 16 が入力を反転してしまうので、inv 16 の繋がる先は先ほどとは逆になっている。
今回はこれで許してやろう。

ALU

二項 ALU である。
各入力に単項 ALU をかました後、And か Add を実行し、最後に Inv することも可能である。

オーケー、454 Nand である。最早 Selector 16 は初めから自作部品を使用した。
まだまだだ。演算に And 16 を使用しているが、その後 Inv 16 も使用している。これは無駄だ。
残念ながら Nand 16 は存在しないのでこれを構成する。見るまでもないがせっかくのなで付けておく。

そして、これを組み込むのだが、Add の場合と And の場合で Inv 16 を通すかどうかが逆転することに注意する。

正解、442 Nand である。
ちなみに、あろうことが Xor もツールボックスにないので仕方なく Nand で構成している。地味にウザい。
だいたいこんなところだが、まだひと絞りできる事にお気づきだろうか。
Add 16 の Nand 数を調べてみると 144 Nand であることがわかる。つまり、全加算器 9 Nand × 16 ビットである。
しかしよく見て欲しい。Add 16 にはキャリー入力もキャリー出力もない。つまり、最下位ビットは半加算器で良いし、最上位ビットのキャリー出力用の Nand も不要なはずだ。
そう、皆さんお待ちかね、楽しい自作部品の時間だ。

そしてこれを組み込む。

オーケー、絵面は全く変わってないが、目論見通り 437 Nand である。
これをファイナルアンサーとしたい。

Opcodes

こいつだけちょっと毛色が異なる。先ほどの 2 項 ALU の制御入力でどのような演算ができるのかを考える問題である。
まぁ上から順番にやっていけば分かると思う。

Condition

条件判定である。入力値 X が指定されたフラグの状態であれば 1 を出力する。
まずは素直に構成する。

62 Nand で正解だが、当然 Nand 数が多過ぎると怒られが発生する。
And とか Or とかを散々使っているので、こいつを分解再構成する。

オーケー、56 Nand でお墨付きを貰った。
しかし、これではあっけなさすぎる。何かがおかしい。
そもそも、is neg は 0 Nand なので良いとして、is zero が微妙だ。なにしろ最上位ビットも含めて 0 かどうか判定してしまっているが、最上位ビットは符号の判定にも使われている。表にするとこんな感じだ。

最上位ビット	それ以外のビット	判定	フラグ
0	全部0	ゼロ	eq
0	いずれかが0以外	正	gt
1	何でもいい	負	lt

つまり、16 ビット全てがゼロかどうか判定するより、最上位ビットを除く 15 ビットが全てゼロかどうか判定した方が良いのではないか？
と言うわけで、まずその判定用自作部品を作成する。名前は安直だが Cond だ。

出力は最終段に Inv を組み込みたくないので ne にした。また、どうせ 16 ビットを分離するのでついでに lt も判定しておいた。
そしてこれを単純に組み込むとこうなる。

Nand 55 で既に 1 Nand 減っている。Optimal とは何だったのか。
更に Or や And を分解し、うんうん唸っていると、こうなった。

Nand 50 で更に 5 Nand 減った。初期の Optimal（Optimal とは言っていない）からは 6 Nand の削減だ！
これで完成としたい。

終わりが見えてきた

残すところ、必須は Processor だけとなった。何とか終わりまでたどり着けそうだ。
なお、重ね重ねのお願いになるが、もしこれらよりも少ない Nand で解けたら是非教えて欲しい。