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:

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.

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 0

Let'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 13

In 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 2

Since 13 goes into 1 less than one time, we have to pull another digit from the dividend:

18 ÷ 13 = 1 rem 5

Another 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 5

We make a note of the result 1 by placing it above the second digit of the dividend.

        0 1
        ------
13      1 8 2

Now 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 0

We'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 2

And 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 0

can be calculated by subtracting the result multiplied by the divisor from the dividend, i.e.

5*101 + 2*100 - 4*13 = 5

This 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

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	; remainder

Looking 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
	       -00001101

Since 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        10110110

Then 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
	       -00001101

The result of subtraction is negative, so we note another zero in our quotient

		00
                --------
00001101        10110110

then shift another digit from the dividend and try again

		00000101 ← 1 10110
	       -00001101

which yields

		000
                --------
00001101        10110110

And again

		00001011 ← 1 0110
	       -00001101

Keeping track of our quotient

		0000
                --------
00001101        10110110

And finally, we've pulled enough digits from our dividend that the result of subtraction is non-negative

		00010110 ← 0 110
	       -00001101
		--------
		00001001

We place a 1 in our quotient

		00001
                --------
00001101        10110110

Now we shift another digit from our dividend into the remainder

		00010011 ← 1 10
	       -00001101
		--------
		00000110

Since the result of subtraction is positive, We place a 1 in our quotient

		000011
                --------
00001101        10110110

Another shift and subtract

		00001101 ← 00
	       -00001101
		--------
		00000000

And we place another 1 in our quotient

		0000111
                --------
00001101        10110110

Now our last shift

		00000000 ← 0
	       -00001101

With the negative result we place a 0 in our quotient and we're done!

		00001110
                --------
00001101        10110110

There you have it, the result 00000110 is equal to 14, the same as before.

Now that you understand how binary division works, it's time to take a look at how to implement it in AVR.