Dividing using subtraction

In this article I will go into a way of dividing that’s possibly unusual – repeated subtraction, with some doubling along the way.  It’s related to other articles I’ve already done:

• Multiplying using doubling, halving and adding
• Multiplying using doubling, halving and adding 2

First, I’ll go into how we get division if we do repeated subtraction.  Then I’ll talk about how to speed this up, which is particularly useful as the answer gets bigger.

Division as repeated subtraction

I’ll explain this with the help of a simple example: 28 / 7.  To recap some terms: in this sum 28 is the numerator and 7 is the denominator.  Even though it might be immediately obvious to you what the answer is, I’ll go through the steps slightly laboriously, so you can see how this is a process that will apply in general and not just for a particular example.  I’ve done maths for quite a while, but nonetheless I had to work through an example like this in my head to reassure myself that division can be expressed as repeated subtraction.

Imagine we have counted out as many little squares as the value of the numerator (28) and arranged them into a rectangle.  This rectangle is conveniently as wide as the denominator (7).  Underneath the rectangle we have some buckets that can hold the squares, and we have as many buckets as the value of the denominator.

Division means: when we share the little squares out equally among the buckets, how many squares does each bucket have? (And how many are left over?)  We’ll slice off the bottom row of the rectangle, and share its squares out equally among the buckets.  This will do 2 things:

• Reduce the number of squares left in the rectangle by 7, i.e. we’re subtracting 7 from 28.
• Increase the number of squares in each bucket by 1, i.e. we’re increasing the answer by 1.

After subtracting 7 once, we have the answer 1 and 3 rows left in the rectangle.  I’ll skip the next two steps – each of them will take off 1 more row from the rectangle and add 1 to each bucket.  We’ll be left with the final row of the rectangle.  I realise it does feel a bit weird to slice off this row, because there’s nothing left to slice it from.  However, we’ll still share it out equally among the buckets, bringing each bucket’s total to 4.  I.e. because the number of times we can subtract 7 from 28 is 4, that means that 28 / 7 = 4.

If, instead of 28, we had 30 squares then they would be arranged into 4 rows of 7 plus an extra row on the top that had only 2 squares.  As we can’t share these 2 squares equally among 7 buckets will just declare them as the remainder.  I.e. 30 / 7 = 4 remainder 2.

How long will this take?

In the example above, we subtracted the denominator 4 times before we ran out of rows.  This seems OK, but what about the sum 456 / 7?  The answer is 65 remainder 1.  If we followed the approach above then we would be subtracting 7 many times (65).  That’s 65 separate bits of maths we have to do, making no mistakes.

So, as the answer grows, the number of subtractions we need to do exactly matches that.  Is there a way we can reduce the number of subtractions but still reliably end up with an answer?  I’ll describe one way in the next section.

Slicing off bigger chunks

Our initial example was a small one, where the answer was less than 10.  When facing a bigger task such as the second example, subtracting 1 row at a time seems painfully slow.  What if, rather than subtracting 1 row at a time, we start by subtracting blocks of several rows?  In the world of the diagrams we’ve been using so far, a block of 10 rows seems like an arbitrary size but it matches a number that’s easy to calculate (e.g. 7 -> 70).

How many of these bigger blocks can we remove?  In this case the answer is 6.  Each time we slice off a block we’ll increase the number of squares in each bucket by 10:

After we’ve sliced off as many of these big blocks as we can, we’re still left with 5 full rows and odd row with a single square.  We can fall back to our first approach, where we slice off a row at a time, increasing the answer by 1 each time.

We’ll end up doing 6 subtractions of the big block plus 5 subtractions of single rows, leading to 11 subtractions in total.  This is much better than 65 subtractions.

This is a process we can extend as the answers get even bigger.  If we had a sum such as 123,456 / 7, we could try subtracting blocks of 10,000 rows, then blocks of 1,000 rows, 100 rows, 10 rows and then single rows.  We can’t go for 100,000 row blocks because that would be 700,000 squares, and we have only 123,456 squares to start with.  The answer is 17,636 remainder 4.  Instead of doing 17,636 subtractions as in the simple technique we’ll do:

• 10,000 row blocks  -> 1 subtraction, removing 70,000
• 1,000 row blocks -> 7 subtractions, removing 49,000
• 100 row blocks -> 6 subtractions, removing 4,200
• 10 row blocks -> 3 subtractions, removing 210
• Single rows -> 6 subtractions, removing 42

This gives a total of 23 subtractions.  This is an amazing saving compared to 17,636 subtractions.  You might have noticed that the list of numbers of subtractions is simply the list of digits in the answer.

If you plot the number of subtractions needed for the simple technique vs the number of subtractions for what I’m calling a decimal technique (using blocks that grow by a factor of 10 each time), you get this:

The number of subtractions in the simple technique is equal to the answer.  The number of subtractions in the decimal technique is equal to the sum of the digits in the answer.  The extra cost of the decimal technique is the multiplications we have to do to create these larger blocks, but we chose the block size such that this multiplication is relatively easy.

Even better, most of the time

We picked a factor of 10 in the previous section because it was easy to calculate, and seemed to give a big improvement in the number of subtractions.  It might seem counter-intuitive, but most of the time things will go even faster if we pick a factor of 2.

In the example above, 123,456 / 7 = 17,636 remainder 1.  Using the decimal technique we use 23 subtractions.  Using blocks that grow by a factor of 2 each time gives the following:

• 16,384 row blocks -> 1 subtraction, removing 114,688
• 8,192 row blocks -> 0 subtractions
• 4,096 row blocks -> 0 subtractions
• 2,048 row blocks -> 0 subtractions
• 1,024 row blocks -> 1 subtraction, removing 7,168
• 512 row blocks -> 0 subtractions
• 256 row blocks -> 0 subtractions
• 128 row blocks -> 1 subtraction, removing 896
• 64 row blocks -> 1 subtraction, removing 448
• 32 row blocks -> 1 subtraction, removing 224
• 16 row blocks -> 0 subtractions
• 8 row blocks -> 0 subtractions
• 4 row blocks -> 1 subtraction, removing 28
• 2 row blocks -> 0 subtractions
• Single rows -> 0 subtractions

There are several things to note here:

• This is only 6 subtraction
• There are many more sizes of blocks than before (15 rather than 5), which means more multiplication to set things up
• When a block is used, it’s used at most once
• If you run the number of subtractions across the various block sizes together in order, you get 100010011100100.  This is the binary version of 17,636 .

It’s worth comparing how often a given size of block is used in the two approaches, and what effect using it has on the work still to do.  In the previous approach, a given size of block could be used up to 9 times.  In this approach, a given size of block could be used at most once.  That’s because using a block will at least remove half of the remaining rows.  For instance, in the first step we start with 123,456.  Once we remove a block of 16,384 rows we remove 114,688 to leave 8,768.

If you compare that with the decimal approach, in some cases a block could remove a lot of the remaining number, such as 13 rows becomes 3 rows if you remove a block of 10 rows. You’ve made the remaining number much smaller. However, if there were 93 rows, then removing a block of 10 rows would only reduce the number to 83 rows. The chances of a block of 10 removing most of the remaining number are relatively small, compared to how effective removing a block is in this approach.

If you plot the graph of the number of subtractions using the decimal approach vs. the number of subtractions using this approach (the binary approach) you get this:

With small answers, the decimal approach has fewer subtractions than the binary approach some of the time, but this gets less often as the answer gets bigger.  For answers above 900, the binary approach always has fewer subtractions.  Note that this graph doesn’t show the number of multiplications involved, which is always less for the decimal approach than for the binary approach.

If these were implemented as computer programs, the complexity of the different approaches would be as follows:

• Simple approach = O(n)
• Decimal approach = O((n mod 10) + ((n mod 100) / 10) + ((n mod 1000) / 100) + …)
• Binary approach = O(log(n))

Is binary easier?

The answer to this one is: it depends.  If I were using paper and pencil, I think that the decimal approach would be easier.  If I were using a counting cloth (see the article on multiplying using halving, doubling and adding for more on counting cloths), then the binary approach is easier.

That’s because doubling on a counting cloth is easy.  You don’t need to do the mental arithmetic or remember your times tables – you simply clone the number to make a fresh one, then put a new counter next to each counter in the cloned number.  Then you do basic tidying up (the equivalent of carrying) – for instance, 2 counters in the 5 rank are swapped for a single counter in the 10 rank.  I’ve successfully done 919 / 27 on a counting cloth (the answer is 34 remainder 1).  I had to prepare 6 different sizes of blocks (1 to 32), but ended up using only 2 of them for subtractions (2 and 32).

On a counting cloth

Now we get to where things started for me with this – a counting cloth. I’ve hinted at the technique earlier, but I’ll try to be clearer here. In summary the technique is:

1. Set up the numerator and denominator at opposite edges of the counting cloth.
2. Make copies of the denominator, doubling each time. Stop just before you make a copy that’s bigger than the numerator.
3. Subtract as many of the different copies of the denominator from the numerator as you can, working from biggest copy to smallest copy, skipping any copies that are bigger than what you have left of the numerator. When you subtract a copy, add the multiple of the denominator that this copy represents (1, 2, 4, 8 etc.) to a tally, e.g. a separate slate or piece of paper.
4. Once you’ve done all the subtraction you can, the answer is the total of all the numbers on the tally, and what’s left on the counting cloth is the remainder.

I’ll go through this with an example: 99 / 9. Spoiler alert: the answer will be 11.

To start with we put 99 and 9 on opposite edges of the counting cloth:

Then we make as many copies of the denominator (9) as we can, doubling each time, without making it larger than the numerator (99), and start with an empty tally where we’ll keep track of successful subtractions:

I’ve labelled the copies with the multiple of the denominator that they represent. I’ll skip the details of the subtractions that follow, but go through each one at a time. 72 < 99, so we can subtract 72 from 99. This means we add 8 to our tally and the numerator is reduced to 99 – 72 = 27.

32 > 27 so we can’t subtract that, and instead just throw the 32 away.

18 < 27 so we can subtract 18 from 27. This means we add 2 to our tally and the numerator is reduced to 27 – 18 = 9.

9 = 9, so we can subtract 9 from itself. This means we add 1 to our tally and the numerator becomes 0. We’re finished.

There’s no remainder (the numerator is 0) and the answer is 8 + 2 + 1 = 11. If you look at how many lots of each copy of the denominator we used, and string those numbers together as digits of a bigger number you get 1011, which is the binary representation of 11.