## Crazy Subtraction Algorithm

For the curious, here’s a description of the unusual subtraction algorithm I used in Ecumenicalculator. This algorithm converts subtraction into something that looks like addition of two positive numbers, mostly. It has the advantage of guaranteeing that you’ll never try to borrow from a zero.

As a running example, let’s say we want to compute 937,105 – 172,910.

Step 0: Assure that both numbers are positive and that the second number is smaller than the first. If either of those conditions does not hold, either swap the numbers (and negate the result), or realize that you actually have an addition problem and not a subtraction problem.

Step 1: Line the two numbers up vertically, so that the decimal places line up. This step is the same as “normal” subtraction.

9 3 7 1 0 5

- 1 7 2 9 1 0

===================

Step 2: Replace each digit in the second number with the value (10 – digit). Yes, this means that any 0 digits turn into a 10 “digit”. Deal with it.

9 3 7 1 0 5

+ 9 3 8 1 9 10

===================

Step 3: Add each column, without propogating any carry digits.

9 3 7 1 0 5

+ 9 3 8 1 9 10

===================

18 6 15 2 9 15

Step 4: Starting with the rightmost column and working left: if the “digit” is greater than or eqal to 10, subtract 10 from it; otherwise, leave it alone and subtract 1 from the “digit” to the left.

This will be easier to illustrate one column at a time. The rightmost one is 15, so we simply subtract 10:

9 3 7 1 0 5

+ 9 3 8 1 9 10

===================

18 6 15 2 95

The second-to-last column is 9, so we leave it alone but subtract 1 from the column to the left of it:

9 3 7 1 0 5

+ 9 3 8 1 9 10

===================

18 6 15195

The antepenultimate column is now 1, so we leave it alone but subtract 1 from the column to the left of it:

9 3 7 1 0 5

+ 9 3 8 1 9 10

===================

18 61419 5

The fourth-from-the-right column is now 14, so we subtract 10 from it:

9 3 7 1 0 5

+ 9 3 8 1 9 10

===================

18 641 9 5

The fifth-from-the-right column is 6, so we subtract 1 from the column to the left:

9 3 7 1 0 5

+ 9 3 8 1 9 10

===================

1764 1 9 5

Finally, the leftmost column is 17, so we subtract 10 from it:

9 3 7 1 0 5

+ 9 3 8 1 9 10

===================

76 4 1 9 5

And lo and behold, 937,105 – 172,910 = 764,195.

Do you see why it works?

…

OK, here’s why it works. It’s actually very similar to regular subtraction, just with optimistic borrows and doing the operations in a different order. Take an arbitrary column in the original problem, where we want to compute `a` – `b`. If `a` ≥ `b`, we simply compute `a` – `b` = `c` and are done with it. However, if `a` < `b`, we borrow: we compute (`a` + 10) – `b` = `c` and subtract 1 from the column to the left.

In the crazy algorithm, we instead start off by computing `a` + (10 – `b`) = `d` right off the bat. Note that `a` + (10 – `b`) = `a` + 10 – `b`, which is what we’d normally compute if a borrow were needed. And in fact, if `d` < 10, then `a` + 10 – `b` < 10 and so `a` – `b` < 0 and `a` < `b`, exactly the condition we look for to decide to borrow. Thus, if `d` < 10, then `c` = `d` and we subtract 1 from the column to the left. Otherwise, we compute `c` = `d` – 10, which works because `d` – 10 = `a` + 10 – `b` = `a` – `b`, which is the result for the column if a borrow isn’t needed. Q.E.D.

So there you have it, mathematical proof that this crazy-looking algorithm does in fact work. Also, each column’s intermediate result will always be greater than or equal to 1 (since the “digits” generated in Step 2 always range from 1 to 10 inclusive), so you never wind up trying to borrow from a 0.

And while I proved it for the base-10 case, it generalizes to any arbitrary base, as long as you replace any instances of 10 with your base of choice.

## 2 Responses

Congratulations – you’ve manifested a rube goldberg way of subtracting.

There are actually good technical reasons for having implemented subtraction that way instead of the “normal” way in Ecumenicalculator.

Besides, if you think that’s Rube Goldberg, you ought to see how the stuff I do with Lambda calculus….