Friday, October 30, 2015

If you know how to add, you know (almost) everything about mathematics

joão pestana

Computers are essentially glorified calculators and all they know is how to add numbers in binary. From there, it's easy to do multiplication — or glorified adding —, subtraction and division — or glorified subtraction. To do a multiplication, you just add the same number over and over the times that you want. To do a division, you do the same procedure, but you remove a certain number over and over until you reach the point when, if you remove it one more time, your result becomes negative. You count the number of times that you did it and the remainder is... well, the remainder. But can we really subtract by adding? Yes! All the mechanical calculators did it — something called the method of complements.

How does it work? It's very simple. Imagine you have two numbers `X` and `Y` and you want to subtract `Y` from `X`. Each number has a certain number of digits, lets say `N` and `M` respectively. So our numbers are `X = x_1 x_2 x_3 ... x_N` and `Y = y_1 y_2 y_3 ... y_M` where `x_i,y_i in {0,1,2,3,4,5,6,7,8,9}`.

For example, if `X=1954` it means `x_1=1`, `x_2=9`, `x_3=5` and `x_4=4`. I want to subtract from that the number `Y=1756` which has the digits `y_1=1`, `y_2=7`, `y_3=5` and `y_4=6`. Usually, we'd do something like `X-Y=1954-1756=198`. We already know our final answer so now we just need to reach it using only the operation of addition.

To do this we need to create `Z` as the complement of `Y`. What this means is that for every `y_i` ranging from `i=1` to `i=M-1`, we write down `z_i` as the distance from that digit to `9` and for the last `y_M` we do just the same thing for `z_M` but this time it's the distance to `10`. In our example, the complement of `y_1=1` is `z_1=8`, `y_2=7` is `z_2=2`, `y_3=5` is `z_3=4` and finally for `y_4=6` is `z_4=4`. Now we have our `Z=8244` as the complement of `Y`.

I added this paragraph some time after writing the article to include a suggestion made by a friend of mine. He pointed out to me that this complement was a subtraction and I agree, but I refuse to call it as such. What I told him is that it's a fixed correspondence. A `1` will always be replaced by an `8` at any digit except the least significant one and will be replaced by a `9` at the later. We can work out the correspondence table 1 for future use.

Original digit `y_i` Most significant digits `z_1 ... z_(M-1)` Least significant digit `z_M`
0 9 0
1 8 9
2 7 8
3 6 7
4 5 6
5 4 5
6 3 4
7 2 3
8 1 2
9 0 1
Table 1 — Correspondence table for the most and least significant digits of Z.

As a final step, to conclude our subtraction by addition, we need to add `Z` to `X` and ignore the first digit — which will be a `1`. That is, `X+Z=1954+8244=10198` and by ignoring the first `1` we get `198`. If you recall, it was our answer!

Why does this work? This exploits a weakness in the machines that we build. In this sense, we can think like the machine and achieve the same result. Imagine that we have a calculator which can only display 4 digits. Our calculator can display exactly 10000 different numbers ranging from `0000` to `9999`. What would happen if we were to add `1` to `9999`? The answer is 10000, but the display can only show the last 4 digits so it discards the first and we'd see the result as `0000`.
The calculator has a limit and we cannot use it to perfom calculations that will result in a number that's larger than 9999, because an overflow will occur and we'll only be able to see the last 4 digits of the result. If we were to perform `9999+9999=19998` in our special 4-digit calculator, we'd see `9998` as a result and be surprised at it — by adding two large numbers we got a smaller one!

What we're actually doing is forcing the calculation to overflow exactly up to the point of the difference between `X` and `Y`. You can think of the complement `Z` as what it would take to make the calculator overflow — or reset — starting at `Y`. So whatever you add to it will yield the difference, because in our calculator `Y+Z=1756+8244=0000` (remember we disregard the first 1).

I can give you another visual example of how this is supposed to work. Imagine that we have 3 identical glasses over some large container. The first is filled with some water and the second is also filled with water, but less than the first one.

You want to find out the amount of water that the first glass has more than the second one. How would you do that? That's when the third glass enters the picture.

If it would so happen that it contained the exact amount of water that would fill up the second glass to the top and you were to pour ir over the first glass, you'd see the exact difference between the first and the second spill out into the larger container.

Full glass
`X-Y` (spillage)
From there, you'd just have to collect and measure the spilled water. It's simple! Now... Could you actually do it using only glasses of water? Here are some rules. You can somehow precisely collect the spillage. You can use how many glasses you need. You have no way of measuring water so you can only rely on overflows.