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.
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
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
Code:
top 01111100 div 00000000
bot 10100000 pos 00100000
Code:
top 01111100 div 00000000
bot 01010000 pos 00010000
Code:
top 00101100 div 00010000
bot 01010000 pos 00010000
Code:
top 00101100 div 00010000
bot 00101000 pos 00001000
Code:
top 00000100 div 00011000
bot 00101000 pos 00001000
Code:
top 00000100 div 00011000
bot 00010100 pos 00000100
Code:
top 00000100 div 00011000
bot 00001010 pos 00000010
Code:
top 00000100 div 00011000
bot 00000101 pos 00000001
Code:
top 00000100 div 00011000
bot 00000010 pos 00000000
'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 )
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: