HalfAdder, FullAdder を最小 Nand 数で実装する

[KBone12]

現状の実装だと可読性は高いが、 Nand の数はより少なくできる解があるため、それで実装する。

現状

HalfAdder

(and(a, b), xor(a, b))

FullAdder

let (c0, sum) = half_adder(a, b);
let (c1, sum) = half_adder(sum, c);
(or(c1, c0), sum)

最適解

HalfAdder

let tmp = nand(a, b);
(inv(tmp), nand(nand(a, tmp), nand(tmp, b)))

FullAdder

let tmp1 = nand(a, b);
let tmp2 = nand(tmp3, c);
let tmp3 = nand(nand(a, tmp1), nand(tmp1, b));
(nand(tmp1, tmp2), nand(nand(tmp3, tmp2), nand(tmp2, c)))

[KBone12]

これを行うなら、 Xor も最小 Nand 数にすべき

[KBone12]

効果としては、変数を使うことにより、関数呼び出しが減らせる。