Number of Lines of Code

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

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.
Reply | Threaded
Open this post in threaded view
|

Re: Number of Lines of Code

WBahn
Administrator
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.
Reply | Threaded
Open this post in threaded view
|

Re: Number of Lines of Code

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?
Reply | Threaded
Open this post in threaded view
|

Re: Number of Lines of Code

WBahn
Administrator
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 3 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.