Build a multiplying machine using NAND logic gates Based on my previous question of the same type, Build an adding machine using NAND logic gates, this time you're being asked to multiply instead of add.

Build a diagram of (two-wire) NAND logic gates that will take the input wires A1, A2, A4, B1, B2, B4, representing two binary numbers A to B from 0 to 7, and return values on the output wires C1, C2, C4, C8, C16, and C32, representing C, which is the product of A and B.

Your score is determined by the number of NAND gates you use (1 point per gate). To simplify things, you may use AND, OR, NOT, and XOR gates in your diagram, with the following corresponding scores:


NOT: 1
AND: 2
OR: 3
XOR: 4


Each of these scores corresponds to the number of NAND gates that it takes to construct the corresponding gate.

Lowest score wins.
60 55 50 48 gates





The original (60 gates) was the systematic approach - multiply each digit with each, and then sum them together. Namely, see Wallace trees and Dadda trees



The top half is the multiplication network - multiply each digit with each, and group output digits with the same weight. Some bits have been left inverted to save gates.

The second half is the adder network. Each box represents a single adder - either a half-adder (5 gates - 1x XOR and an inverter), or a full adder (9 gates - 2x XOR and NAND the inverted carry bits). The top are inputs, the bottom output is the sum, the left output is the carry-out.  see the previous challenge

The 2x2 multiplier has then been hand-optimised to a custom-built 13-gate network, which is the optimal size as found by @boothby. Thanks!

Pasting it into the low-bit corner and reoptimising the adder tree saves five gates (see revision #2). Pasting it into the high-bit corner as well, however, produces overlap. A little bit of math tells us, however, that dropping the low-bit of the high multiplier solves the overlap and what's left to do is to add the remaining two bits and sum up stuff.

This alone, unfortunately, does not provide any savings, but it does open two optimisations. First, the two multipliers have two gates in common, and can be fused together. At this point, we're back at 55. Second, in the addition network, we don't need a half-adder because we know its carry will be zero. We can replace it with an OR. An OR is a NAND with its inputs inverted. This produces us with two 2-chains of NOTs on each branch, which can then be removed, for a total saving of five gates. Unfortunately, the half-adder at C16 still carries, so we cannot do the same there. Third, a full adder has a useful property: if you invert its inputs and its outputs, it still behaves the same. Since all its inputs are already inverted, we can just as well move the inverters behind it. Twice. We could have done the same in the original, but... oh well. We still have a half-adder with two inverted inputs. I want optimise this part more, but I doubt I can.

Since we're pulling out a NOT from inside a component, we have to signify that somehow. We have obtained a half-adder with inverted carry (AKA tapped XOR) at a cost of four gates.

In the meantime, we have also redrawn the diagram significantly.