Number of Lines of Code

[kwixson]

The reading for the project suggests the ALU can be defined with ~20 lines, which I assume means 20-ish parts, yes?

I did it with 15 parts, which seems suspicious to me. How much are you all in for? Not counting comments, blank lines, single part broken out to separate lines for readability, etc.

[WBahn]

Off the top of my head, I believe I that 15 is the best you can do using only the parts specified in the text. If you define a 16-bit XOR gate and a 16-way NOR gate, you can cut that to just 9.

[kwixson]

Wow. It blows my mind that you can build something that powerful with so few parts. They weren't kidding when they said it was elegant.

A assume, though, that the shorter code (the 9 line version) is still less efficient because there are ultimately more parts involved, counting the parts in the helper chips. Yes?

[WBahn]

The efficiency is not really very well correlated with the number of parts involved, especially in Nand2Tetris.

For example, the Not gate is implemented using a Nand gate, but while this is nice from the perspective of building everything from a single starting primitive, it is not how a Not gate is really built. In CMOS, this approach uses four transistors but it is actually built using just two. It gets far worse for more complex gates. While N2T doesn't have the student build a Nor gate (only because the project doesn't happen to require one), if they did it would be an Or gate followed by a Not gate. The Or gate, in turn, is likely implemented using a Nand gate and two Not gates. The end result is a gate that would take 16 transistors when a real implementation would use four transistors and be three times as fast.

Another shining example is the Xor gate. Using the intuitive implementation presented in the text, it would use 40 transistors and have 5 prop delays (a prop delay is the amount of time it takes a single to propagate through a single Nand gate) while the usual implementation only uses 16 transistors and has 3 prop delays.

In the case of the part reductions discussed here, the helper chips can significantly reduce the overall transistor count and really speed things up in a real implementation.

The combination of a Not and a Mux to selectively invert a signal can be replaced by a single Xor gate. An Xor gate can be implemented using four Nand gates (for a total of 16 transistors) and have 3 prop delays. The Not/Mux combination, as most N2T students would likely implement them, uses 10 Nand gates (40 transistors) and has 6 prop delays.

[ErikSwan]

It is possible to do using 13 parts (13 lines of code in the PARTS section) with only the chips previously specified in the text.

There is one piece of this minimal 13-part implementation that feels inelegant—as if a specific chip is missing from the set of chips previously defined in Chapter 1.

If anyone has found a way to implement the ALU in less than 13 lines with only the chips previously defined in the text, I would be very curious to know how it's done.

[WBahn]

Yes, 13 was the fewest parts I came up with. The 15 I mentioned earlier in the thread was done off the top of my head and I forgot about one of the parts that is available.