Today I began the second week of the free NAND2Tetris course on computer science from first principles! I started by reading Chapter 2 of The Elements of Computing Systems (PDF) by Noam Nisan and Shimon Schocken.
Notes for Chapter 2
First thoughts: I’m building an arithmetic logical unit? What have I gotten myself into?! That sounds scary!
They say that “most of the operations performed by digital computers can be reduced to elementary additions of binary numbers.” I already knew that, but of course I don’t really understand how it works or why it’s true. But isn’t that amazing?
The magic of positional number systems
Uh oh, their introduction to binary jumps right into scary math equations! A few days ago, while I was having breakfast at my family’s house, my dad asked me, “How do you count in binary?” I was really happy that he asked, and even happier that I could answer his question! He got the gist of it pretty quickly, but when I asked him how to count in base 4, he said he had no clue what to do.
If I showed him this scary equation from the book – even if it does succintly capture the essence of all positional number systems – it would not have helped! Because we develop an intuition about how the decimal system works long before we ever learn about any formal mathematical notation. Anyway, this is defintiely a topic I’d like to dive into more in the future: what’s a fun and interesting and clear way to explain how positional number systems work?
Like they explain in the book, the same addition algorithm taught in elementary school works for binary addition. (It works for all positional number systems!) Somehow that still seems like magic to me!
Signed binary numbers and two’s complement
By “signed” they mean positive and negative numbers, and there are many different ways to represent them using nothing but 0s and 1s. The most common solution used today is called the “two’s complement method” or “radix complement”.
More math stuff here… my eyes glazed over for a moment, but I do understand the example of a 4-bit binary system (from 0000 up to 1111), where all the numbers that begin with 0 are positive numbers from 0 to 7, and all the numbers that begin with 1 are negative numbers from -1 to -8. To reverse the sign of a number, you just subtract it from 10000, which is 2 to the power of 4 in binary.
It’s no coincidence that a 4-bit binary system is based on this magic number 2^4; in a 5-bit binary system, you would be subtracting from 2^5. So they define the two’s complement of a number x in an n-bit binary system as 2^n - x (if x isn’t 0).
Nifty shortcut: To get the negative of a number, just flip all of its bits and add 1 to the result. Magic! Why does that work?
Another magic trick: You can add these signed numbers as if they were all positive numbers! Just throw out the overflow bit and you’ll have the answer! And to subtract a number, you just add its additive inverse using that trick and bam, you can do addition and subtraction with the same circuitry!
The lesson to remember: Thanks to the magic of positional number systems and the two’s complement method, you can build a single chip (the arithmetic logical unit) that can perform all the arithmetic and logical operations required by a computer!
Adding with adders
An adder is a chip that adds numbers! They outline three types: half-adders add 2-bit numbers, full-adders add 3-bit numbers, and n-bit adders can add bigger numbers.
There are also incrementers, chips designed to simply add the constant 1 to a given number. The book says these are convenient but doesn’t explain why, so of course I want to know: why?
They note at the end of the chapter that their suggestion implementation for an adder is “rather inefficient”, but it does work. Something about “carry look-ahead”, which I guess they decided was too advanced to cover in chapter 2. I’ll make a note to learn more about that one day.
The arithmetic logical unit (ALU)
They outline the design of the ALU in some detail, and it took me a while to understand it! Here’s what I understand so far:
- To pick a function to perform, you set six input bits (called “control bits”).
- It has a “fixed repertoire of eighteen possible functions.”
- It could potentially compute 64 different functions (because it has 6 control bits and 2^6 is 64.)
- It can negate 16-bit numbers and add 16-bit numbers, so it can also subtract 16-bit numbers.
- It can perform the AND operator on two 16-bit numbers, and through negations, it can perform the OR operator as well.
- It ignores overflow, so I guess that means I better be careful not to add numbers that are too big, because it won’t even tell me if it can’t add them!
They say that the ALU and the operating system that runs on top of it are what determine the overall functionality of a computer, so designing the ALU is a cost/performance issue. They point out that “hardware implementations of arithmetic and logical operations are usually more costly, but achieve better performance.” For this project, they decided to design a very simple ALU and use the operating system to implement as much functionality as possible – software instead of hardware. I guess they decided it would be easier for us to learn how to do that stuff with software, even if it makes for a less efficient computer.
This raises lots of questions about the trade-offs and limitations of hardware and software! Why is it that we can implement the same functionality in hardware and in software? I don’t really understand how the two work together, but I guess that’s why I’m taking this course!
Apparently the ALU can’t multiply or divide, so I’ll have to implement that on the software side later. How?! Oh, I guess I’ll just tell the hardware to do repeated addition or subtraction. That makes sense. But I wonder what the limitations are.
New concepts and jargon
- Least significant bits (LSB): the right-most digits in a binary number.
- Most significant bits (MSB): the left-most digits in a binary number.
- Overflow: when adding the two MSBs results in a carry bit.
- Two’s complement or radix complement: the most common way to represent positive and negative integers in binary.
- Arithmetic logical unit (ALU): the chip that performs all the arithmetic and logical operations required by a computer.
- Adders: chips that add numbers, including half-adders (2-bit), full-adders (3-bit), and n-bit adders.
- Incrementers: chips that add the constant 1 to a number.
- Control bits: the input bits that determine which function a chip will perform.
- Bit-wise (like bit-wise AND): performing an operation on individual bits.
Questions
- What’s a fun, interesting and clear way to explain how positional number systems work?
- Why does the two’s complement method work?
- How was the two’s complement method discovered?
- Why are incrementers convenient? Why not just use an adder as an incrementer?
- What is a “carry look-ahead” adder?
- How is it that we can implement the same functionality in hardware and in software, and what factors determine their trade-offs?
- Why are hardware implementations of arithmetic and logical operations faster than software implementations?
- What’s the bare minimum set of operations that need to be implemented in hardware in order to support fully-functional computer software?
Learning summary (#TIL)
- Thanks to the magic of the two’s complement method, a single chip called the arithmetic logical unit can perform all arithmetic and logical operations required by a computer!
- If the arithmetic logical unit (ALU) can negate inputs and outputs, set inputs to 0, add two numbers, and perform the bit-wise AND operator on two numbers, then it can also subtract and perform bit-wise OR!
- More advanced operators and functions like multiplication and division can be implemented in software using this minimal ALU.
Next steps
- Watch the video lectures for week 2 on Coursera.
- Start building the second project!
Time breakdown
- Study time: 1 hour 35 min
- NAND2Tetris chapter 2 active reading: 1 hour 35 min