Binary Division
The AVR architecture does not include hardware division so it must be done in software. Even simple division routines are very costly in terms of execution time and code size, so here are a few things to think about when considering doing it in your program:
- Don't if you can help it
- Always use shifts if you are dividing by powers of 2
- Use an approximation if you don't need perfect accuracy
- Seriously, don't if you can help it
Unfortunately, there are somtimes no acceptable alternatives and software division must be done. Here we will look at how to implement division routines in assembly.
Decimal Division
Writing a division routine for your microcontroller requires an understanding of binary division. And the best way to learn starts with reviewing regular decimal division
Consider dividing 182 by 13. Here 182 is referred to as the dividend, while 13 is the divisor. An example of this worked with long division is shown below:
014
---
13 182 ; divide 13 into 182
↓ ; bring down first digit from dividend
*0 1 ; 13 goes into 1 zero times
↓ ; bring down another digit from dividend
18
*1 -13 ; 13 goes into 18 one time, subtract 13*1 from remainder
---
05 ; remainder is 5
↓ ; bring down another digit from dividend
052
*4 -052 ; 13 goes into 52 four times, subtract 4*13 from remainder
---
000 ; remainder is 0Let's take a look at this step by step.
To begin with, we attempt to divide the first digit of the divisor with the dividend
1 ÷ 13 = 0 rem 13In decimal notation we normally don't include leading zeros, but for clarity (and for the sake of the following examples) we will make a note if this division by placing the result 0 above the first digit in the dividend.
0
------
13 1 8 2Since 13 goes into 1 less than one time, we have to pull another digit from the dividend:
18 ÷ 13 = 1 rem 5Another way to think of this is that we shift 1 to the next power of 10 and we shift 8 into the lowest power of 10
1*101 + 8*100 ÷ 13 = 1 rem 5We make a note of the result 1 by placing it above the second digit of the dividend.
0 1
------
13 1 8 2Now we need to figure out how many times 13 goes into the remainder 5. If we've done the previous steps correctly, the remainder will be less than our divisor, so, like before, we must shift another digit from our divisor like so
5*101 + 2*100 ÷ 13 = 4 rem 0We've divided the remainder and obtained a result 4 so we make a note by placing it above the third digit of the dividend
0 1 4
------
13 1 8 2And we're done. We've determined that 13 goes into 182 14 times with a remainder of 0.
Binary division can be done in the exact same way, except that every digit can only take one of two values, as opposed to the nine possible in decimal. This means that unlike in decimal where we must decide how many times the divisor can go into the remainder each step, in binary it either divides in or it doesn't (0 or 1!).
Note that the remainder of a division step like
5*101 + 2*100 ÷ 13 = 4 rem 0can be calculated by subtracting the result multiplied by the divisor from the dividend, i.e.
5*101 + 2*100 - 4*13 = 5This only works if we know the how many times our divisor goes into the remainder. But since in binary the result can only be a 1 or 0, we just need to compare the divisor and the remainder. If the divisor is less it will go in once, otherwise its zero
Binary Division
The exact same division of 182 by 13 is shown below in 8-bit binary
00001110
--------
00001101 10110110 ; divide 13 into 182
↓
00000001 ; bring down digit from dividend
-00001101 ; subtract 13 from it
---------
- ; result is negative, place 0 above digit 1
↓
00000010 ; bring down digit from dividend
-00001101 ; result is negative, place 0 above digit 2
↓
00000101 ; bring down digit from dividend
-00001101 ; result is negative, place 0 above digit 3
↓
00001011 ; bring down digit from dividend
-00001101 ; result is negative, place 0 above digit 4
↓
00010110 ; bring down digit from dividend
-00001101 ; result is positive, place 1 above digit 5
---------
00001001 ; remainder
↓
00010011 ; bring down digit from dividend
-00001101 ; result is positive, place 1 above digit 6
---------
00000110 ; remainder
↓
00001101 ; bring down digit from dividend
-00001101 ; result is positive, place 1 above digit 7
---------
00000000 ; remainder
↓
00000000 ; bring down digit from dividend
-00001101 ; result is negative, place 0 above digit 8
---------
00000000 ; remainderLooking at this step by step, we take the first digit of the dividend, shift it into the LSB and subtract our divisor from it.
00000001 ← 1 0110110
-00001101Since the result of the subtraction is a negative number, we know our divisor will go into it less than one time. So we put a 0 above the first digit of our dividend
0
--------
00001101 10110110Then we pull another digit from our divisor, shift our first digit up and place the new one in the LSB, and try again
00000010 ← 0 110110
-00001101The result of subtraction is negative, so we note another zero in our quotient
00
--------
00001101 10110110then shift another digit from the dividend and try again
00000101 ← 1 10110
-00001101which yields
000
--------
00001101 10110110And again
00001011 ← 1 0110
-00001101Keeping track of our quotient
0000
--------
00001101 10110110And finally, we've pulled enough digits from our dividend that the result of subtraction is non-negative
00010110 ← 0 110
-00001101
--------
00001001We place a 1 in our quotient
00001
--------
00001101 10110110Now we shift another digit from our dividend into the remainder
00010011 ← 1 10
-00001101
--------
00000110Since the result of subtraction is positive, We place a 1 in our quotient
000011
--------
00001101 10110110Another shift and subtract
00001101 ← 00
-00001101
--------
00000000And we place another 1 in our quotient
0000111
--------
00001101 10110110Now our last shift
00000000 ← 0
-00001101With the negative result we place a 0 in our quotient and we're done!
00001110
--------
00001101 10110110There you have it, the result 00000110 is equal to 14, the same as before.
Conclusion
Now that you understand how binary division works, it's time to take a look at how to implement it in AVR.
Post a Comment