# 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 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*10`^{1} + 8*10^{0} ÷ 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*10`^{1} + 2*10^{0} ÷ 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*10`^{1} + 2*10^{0} ÷ 13 = 4 rem 0

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

`5*10`^{1} + 2*10^{0} - 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

## 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 ; 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.

## Conclusion

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