Defining "Addition" - Building a Simple Computer
Apr 04, 2018
So lately, I have been building a very simplistic computer based on a very simple rule set. This computer is simplistic to the point where I have to define what addition, subtraction, multiplication, and division mean. I'll talk about that project in a later post, but before I can do that, I need to define how these functions work, starting with addition. All of these functions we will be defining assume that values are non-negative integers. It took humanity a while to start worrying about negative numbers, so we'll worry about non-negative integers for now. I might expand upon the concept of negative numbers later.
To begin with, let's talk about incrementing and decrementing. We'll discuss this in terms of a person having a collection of rocks. Increment can be thought of as the person gathering another rock. Decrementing is the opposite, where a rock is taken away from the person.
Now for something that looks a little bit more like computer science. Let's start with Incrementing:
A = 4 INC A [A now equals 5]
Now let's check out Decrementing:
B = 4 DEC B [B now equals 3]
For addition, we will start with 2 values, X and Y. These values are called _addends_ and the solution to the addition problem is called the _sum_. You'll recognize the setup as X + Y.
In order to add Y to X, first check to see if Y is zero. If Y is not zero, decrement Y, then increment X. Repeat this until Y is zero. When Y is finally zero, X will be the solution.
To describe this in the way we did before with a person having a collection of rocks, imagine this time that the person has TWO collections of rocks and wants to add the rocks from the second collection to the first collection. That person would take a rock from the second collection and add it into the first collection, essentially decrementing from the second collection and incrementing from the first collection until the second collection has no more rocks.
This can be described in the following pseudo code function:
Define ADD (X, Y): If Y does NOT equal 0: DEC Y INC X ADD (X, Y)
So let's go through this function to figure out what 3 + 2.
X = 3 Y = 2 ADD (X, Y) Is Y NOT 0? [Yes] DEC Y [Y now equals 1] INC X [X now equals 4] ADD (X, Y) Is Y NOT 0? [Yes] DEC Y [Y now equals 0] INC X [X now equals 5] ADD (X, Y) Is Y NOT 0? [No] ------------------ | 3 + 2 equals 5 | ------------------
You might notice that because the addition function loops in a recursive manner, we technically are doing multiple different but equivalent addition problems, 3 + 2, 4 + 1, and 5 + 0.
The only things we needed in order to define addition is the ability to increment, decrement, specify a value to do actions to, and check if a value is 0.