Links:

Part 0: What & Why

Part 1: What is a number?

11/30/22

Armed with a basic idea for how to handle number representation, we can start figuring out how to manipulate numbers. The basic building block will be Logic Gates, arrangements of transistors that take in multiple inputs and return an output. Examples of these logic gate include AND, OR, NOT, etc. Carefully chaining these logic gates together allows us to take meaningless bits of electricity and perform useful calculations.

ADDITION:

The Binary Adder seems to be a pretty well tread area, so I won't go too in depth explaining the logic (links to in-depth explanations at the bottom). Essentially, when adding two 1-bit binary numbers, there are only a couple input/output scenarios:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 (and a value of 1 to carry to the next binary place)

A setup like the circuit below will handle the logic of adding two 1-bit numbers, as well as incorporating potential carry values in and out:

Above, when A and B and the Carry In are all zero, the output is zero as expected. When one of the inputs is 1 and the rest are zero, the output is 1:

And two inputs of 1 returns an output of 0, but with a carry value of 1 to the next place:

So if we chain multiple of these simple adders together, linking the Carry Out of one to the Carry In of the next, we can add larger binary numbers. Here is a setup that can add two 8-bit numbers, created by chaining 8 of the simple adders above together:

SUBTRACTION:

It seems like the best way to perform subtraction is to not do subtraction, but instead do addition with a number's additive inverse. "Additive inverse" being the number to add to a number such that the sum equals 0, e.g. "-5" is the additive inverse of "5". So instead of performing the operation A-B=?, we'll instead do A+(-B)=?. This seems like a pedantic setup, but if we can easily find a number's additive inverse, then we don't have to build a whole new logic circuit to handle subtraction, but just reuse the addition logic in place. A long time ago, people smarter than me figured out a system called Two's Compliment that handles the conversion of binary numbers to their additive inverse. There are two steps to find the 2's compliment additive inverse of a number:

1. Flip all of the number's bits (0 -> 1, 1 -> 0)

2. Add 1 to the resulting number

Like so:

You may notice that the negative numbers we've created don't appear out of nowhere. In order to create the negative numbers, we had to take previously large binary numbers and redefine them as negative. For example, in 2's compliment, the number -23 is defined as 11101001. Previously, without the concept of negative numbers, 11101001 would have represented the decimal number 233. We have to sacrifice the large positive numbers to shift our range into the negative realm. With 8 bits, before negative numbers, we could represent the range from 0 to 255. Now with 8 bits we can represent the range -128 to 127. You may also notice that the leftmost digit in the binary number is always 0 for positive numbers and always 1 for negative numbers, which will probably end up being useful down the line.

We can do some testing to verify the 2's Compliment conversion works on the already built adder.

10 + (-10) = 0

15 + (-27) = (-12)

Everything checks out. A little logic to convert a number to its 2's Compliment additive inverse (use NOT gates to flip bits, then a whittled down adder to add one):

And stick this onto our previously built adding machine:

Already the circuitry is getting a little complicated. I don't really want to sketch out the full schematic for Multiplication and Division, but I have some ideas for both, and an idea to simplify the circuitry so the size and cost of the calculator doesn't spiral out of control.

MULTIPLICATION:

Multiplication is really just addition, many times. E.g. 5 × 3 = 5 + 5 + 5. We could just use our adder to sum the first number with itself as many times as required, storing the intermediate value in a yet undefined place/process. However, this approach would probably quickly get out of control, and is vague about what it means to multiply by a fractional number. I saw an eloquent technique that is way more efficient and scalable, that I've seen referred to as Russian Binary Multiplication. The trick is using one of the binary numbers (multiplicand) as a sort of index of how to double the other binary number, and summing the doubles. Confusing sentence- here's what I mean:

Problem: 9 × 13

In binary: 00001001 × 00001101

Consider doubling the number 13 several times:

13

26

52

104

208

And observe the binary representation of those numbers:

13 = 00001101

26 = 00011010

52 = 00110100

104 = 01101000

Any further and we'd have to increase our number of bits, but the pattern persists: doubling a number is equivalent to shifting everything left by one space (and filling the right side with a zero). If we now treat binary 9 like an index, and map the values to the doubles of 13, starting from the right:

1: 13

0: 26

0: 52

1: 104

0: 208

0: 416

0: 832

0: 1664

Now only keep the doubles that map to a 1 in the binary 9:

1: 13

1: 104

And add them to 117, which is 9 × 13.

This example and another:

This method is neat because it can handle fractional numbers as well (with a shift at the end), though we really haven't explored that thoroughly yet. This method also ensures that the maximum number of additions we have to do is equal to the number of bits we have. To do 17 × 7 using the many additions method, we'd either be doing:

17+17+17+17+17+17+17, or

7+7+7+7+7+7+7+7+7+7+7+7+7+7+7+7+7

But instead, we simply do

7+112, or

17+34+68

Much more efficient, and the wiring would be fairly simple. Here is a 4-bit multiplication example:

This approach cannot handle the 2's Compliment negative numbers, however, so we'll have to detect when a negative number is inputted (probably using the first bit), convert, multiply, then convert back to negative.

DIVISION:

Much like the approach to subtraction, I think we should avoid doing division, and instead do multiplication with multiplicative inverses (e.g. 5 -> 1/5). One way to find multiplicative inverses is using Newton's Method. Essentially, iterating this equation several times:

So instead of doing division directly, we can use only addition and multiplication to find a number's multiplicative inverse, then do multiplication with that. I'm intentionally being vague about the implementation, because a lot will have to be changed between now and then. This equation does get very close to the solution very fast:

I could map out the logic and wiring to implement division. We have the tools (addition, multiplication), but the size of the circuit will explode. Working with two 8-bit numbers, for each iteration of the equation there would have to be two multiplications and two additions, as well as a 2's compliment conversion or two. Each multiplication takes somewhere between 1 and 8 additions. And we'd have to do a couple iterations at least to feel comfortable. The number of logic gates is growing rapidly, and we're only at division, much less Time Value of Money math. It's time to get smarter and figure out how to reuse basic functions (like addition) multiple times in a calculation, rather than just brute forcing answers. This will require places to store and recall intermediate calculations, and some form of instruction to guide multi-step processes.

Next up:

Part 3: Storing & Recalling Data

Sources:

Logic Diagram Software - https://sourceforge.net/projects/circuit/

Really good 2's Compliment Calculator - https://www.exploringbinary.com/twos-complement-converter/

Addition (Ben Eater) - https://youtu.be/wvJc9CZcvBc

2's Compliment (Computerphile) - https://youtu.be/lKTsv6iVxV4

Russian Binary Multiplication (Computerphile) - https://youtu.be/HJ_PP5rqLg0