Binary division and modulo from first principles

hippy

Technical Support
Staff member
#1
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 ..
Code:
top 01111100      div 00000000
bot 00000101      pos 00000001
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'.
Code:
bot 00000101      pos 00000001
bot 00001010      pos 00000010
bot 00010100      pos 00000100
bot 00101000      pos 00001000
bot 01010000      pos 00010000
bot 10100000      pos 00100000
Now we go back to our original scheme, albeit with 'bot' and 'pos' shifted -
Code:
top 01111100      div 00000000
bot 10100000      pos 00100000
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 -
Code:
top 01111100      div 00000000
bot 01010000      pos 00010000
Now 'bot <= top', so we add the 'pos' into 'div', and also subtract 'bot' from 'top', which leaves us with -
Code:
top 00101100      div 00010000
bot 01010000      pos 00010000
We then shift both 'bot' and 'pos' right -
Code:
top 00101100      div 00010000
bot 00101000      pos 00001000
Again 'bot <= top' so we add the 'pos' into 'div', and also subtract 'bot' from 'top', which leaves -
Code:
top 00000100      div 00011000
bot 00101000      pos 00001000
We then shift both 'bot' and 'pos' right.
Code:
top 00000100      div 00011000
bot 00010100      pos 00000100
This time 'bot <= top' is false so we shift both 'bot' and 'pos' right.
Code:
top 00000100      div 00011000
bot 00001010      pos 00000010
Again 'bot <= top' is false so we shift both 'bot' and 'pos' right.
Code:
top 00000100      div 00011000
bot 00000101      pos 00000001
Again 'bot <= top' is false so we shift both 'bot' and 'pos' right.
Code:
top 00000100      div 00011000
bot 00000010      pos 00000000
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 -
Code:
Symbol top = w1
Symbol bot = w2
Symbol div = w3
Symbol pos = w4

top = 124
bot = 5

SerTxd( #top, " / ", #bot, " = " )
div = 0
pos = 1
If bot <> 0 Then
  Do Until bot >= $8000 Or bot >= top
    bot = bot * 2
    pos = pos * 2
  Loop
  Do
    If bot <= top Then
      div = div + pos
      top = top - bot
    End If
    bot = bot / 2
    pos = pos / 2
  Loop Until pos = 0 Or top = 0
End If
SerTxd( #div, ", remainder ", #top, CR, LF )
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.
 
Last edited:

hippy

Technical Support
Staff member
#3
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.
 

hippy

Technical Support
Staff member
#4
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 -
Code:
0      00101
1     001010
0    0010100
1   00101000
1  001010000
We remove every entry where our left bit is a 0, leaving only those which are a 1 -
Code:
1     001010
1   00101000
1  001010000
Then we simply add-up the numbers on the right -
Code:
   010000010
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 -

Code:
Symbol reserveW0 = w0 ; b1:b0
Symbol lhs       = w1
Symbol rhs       = w2
Symbol result    = w3

lhs = 26
rhs = 5

SerTxd( #lhs, " * ", #rhs, " = " )
result = 0
Do While lhs <> 0 And rhs <> 0
  w0 = lhs & 1
  If w0 = 1 Then
    result = result + rhs
  End If
  lhs = lhs / 2
  rhs = rhs * 2
Loop
SerTxd( #result, CR, LF )
 
#5
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! :LOL::D
 
Top