Binary division and modulo from first principles

Looking at doing some multi-word maths I realized I had no idea how to actually do binary division, let alone modulo apart from the convoluted mechanism of using the result of the division multiplied then subtracted. That all sounded like a lot of complexity.

So I dived in to finally, after many years, discovering how binary division works. It is fairly simple but as I had to figure out how 'on paper' versions map to an actual program algorithm I thought I would share what I learned along the way. It may be useful, maybe enlightening for some. It was for me.

So; division and modulo from first principles.

Let's take two byte values 'top' 124, 01111100 and 'bot' 5, 00000101. We are going to divide 'top' by 'bot'. 124/5 = 24, remainder 4.

In the process We will have a 'div' result initially set to 0 and a 'pos' initially set to 1 which indicates how 'bot' is positioned. So to start with we have ..
The first thing we do is shift 'bot' to the left until the msb of 'bot' is set, and every time we shift 'bot' we also shift 'pos'.
Now we go back to our original scheme, albeit with 'bot' and 'pos' shifted -
We are looking for cases where 'bot <= top', where we can divide 'bot' into 'top', and currently it isn't so we shift 'bot' and 'pos' right, giving -
Now 'bot <= top', so we add the 'pos' into 'div', and also subtract 'bot' from 'top', which leaves us with -
We then shift both 'bot' and 'pos' right -
Again 'bot <= top' so we add the 'pos' into 'div', and also subtract 'bot' from 'top', which leaves -
We then shift both 'bot' and 'pos' right.
This time 'bot <= top' is false so we shift both 'bot' and 'pos' right.
Again 'bot <= top' is false so we shift both 'bot' and 'pos' right.
Again 'bot <= top' is false so we shift both 'bot' and 'pos' right.
And with 'pos' at zero we have reached the end of our excursion

'div' now contains our result = 00011000, 24
'top' now contains the modulo = 00000100, 4

And that's right, it's as expected.

There are a few tweaks we can do which aren't too complicated -

First we can change the initial shifting so 'bot' doesn't have to be shifted so its msb is set; Stopping when 'bot' >= 'top' is good enough. That saves a few pointless shifts left and then right again.

Likewise we can terminate when 'top' becomes zero, because there's nothing left to subtract from. Note we cannot terminate when 'top < bot' because it very well might be at some legitimate stages of the algorithm.

And finally we need to handle 'divide by zero', or our left shifting 'bot' to set the msb will never complete.

So our algorithm, implemented here for word variables, is -
And you can run that in the PE6 simulator or on a PICAXE chip.

So who said binary division and modulo were hard ?

It often pays to go back to first principles to find simple algorithms. There may be smarter ones but these work, we know they work, more importantly we can prove they work, and best of all we can even understand how they work..

This algorithm can of course be extended to use multi-word numbers. The algorithm remains the same though we have to tweak how the msb set is determined, how we do the comparisons, and the multiple and divide by two operations, which can be implemented as shifts. But that's all fairly simple.

hippy said:

best of all we can even understand how they work

Click to expand...

Yes! I got it! I got it! Great description of the process, too. Thanks, hippy!

Glad it was useful. I have made a couple of cosmetic changes to the text where I had used the names of variables actually used in my test program rather than the names I used in the example and corrected a couple of typos.

Binary multiplication

Just for completeness, here's the 'from first principles' means of doing binary multiplication,

We are going to multiply 26 by 5, in 5-bit binary, 11010 * 00101

we first create a list with all the bits of the left-most number in a left column, starting with the lsb first, along with the right-most number in the right column, shifted left for each successive bit -
We remove every entry where our left bit is a 0, leaving only those which are a 1 -
Then we simply add-up the numbers on the right -
And that's our answer; 130 in decimal.

Of course we can do the discarding of 0 bits in the left column, shifting the right column, and accumulating the result, as we go.

Here's the algorithm using word variables which can run in the PE6 simulator or on a real chip -

Thanks for supplying this - going to be very dangerous for me... I already find it difficult to use higher level languages, as I've got used to the bit-level mathematics of PICAXE and other microcontrollers, so this is just going to reinforce that!