Division using Long Division

As I’ve been building a decimal number implementation in Rust I’ve needed to think about some numerical algorithms from a binary level - some which can initially seem non trivial. One situation falling into this category is division. Before going into the specifics of the Rust implementation I thought I’d cover the different ways to perform division using binary numbers. Consequently I’ve broken this topic into many parts:

• Part 1 - Division using Long Division
• Part 2 - Division using Two’s Complement
• Part 3 - A simple implementation of division in Rust

Now to get stuck into it!

A refresher on long division in base10

If you’re like me, it’s been a long time since you’ve had to perform long division. In fact, I’d personally “moved” that knowledge aside in lieu of short division techniques. Accordingly, it’s worthwhile refreshing our long division knowledge. We’ll practice long division on $\dfrac{294}{7} = 42$. Before diving into this, let’s cover some terminology:

• Dividend - the number that is being divided. In our example: $294$.
• Divisor - the number that another number, the dividend, is to be divided. In our example: $7$.
• Quotient - the number obtained by dividing one quantity by another. In our example: $42$.

Or to simplify: $\dfrac{Dividend}{Divisor} = Quotient$

Ok, now we’ve got the definitions out of the way let’s cover the generic steps we need to follow:

1. Compare the divisor to the first digit of the dividend. If the divisor is bigger than the first digit then keep “adding numbers” until the divisor is less than or equal to the number.
2. Divide the subsequent number and use the result as the first digit of the quotient.
3. Multiply the quotient digit with the divisor and write the result underneath the number.
4. Subtract the multiplied result from the dividend’s digits to find the remainder.
5. Repeat

With anything, an example is easier. Using our earlier example we start by writing the equation as:

Comparing the divisor with the first digit we find that $7 \gt 2$. Consequently, we keep “adding” numbers until the divisor is less than the comparison. In this case, if we take the next digit we can see that $7 \le 29$. Success!

Moving onto step two, we now divide $29$ by $7$ and use the result as the first number of the quotient. Of course, $7$ goes into $29$ four times with a remainder of one. Consequently, we write this into our equation:

We then continue and multiple the digit with the divisor (i.e. $7 \times 4$) and write the result underneath:

Moving to step four we subtract the multiplied result from the dividend’s digits to find the remainder. We also carry down the next digit, in this case $4$:

We now do the same operations on the new remainder. In this case we will do $\dfrac{14}{7}$ and put the result in the next position:

To round off, we multiply the new digit ($2$) with the divisor and subtract from the existing remainder:

We’ve got no remainder so we’re done - and we have our result of $42$. If we had to keep going we’d need to introduce a decimal point since we’re shifting past the integral section. This isn’t relevant at present so we’ll skip that part and move onto binary.

Long division in binary

Long division in binary is actually very similar, albeit much simpler! For the binary division example we’ll use something which fits into a byte for simplicity: $\dfrac{147}{7} = 21$ or better represented as $\dfrac{10010011}{00000111} = 00010101$.

Firstly, let’s set up the problem the same way (leading zeroes omitted):

Now we compare the divisor with the first digit as we did in base10. In this case $111$ can’t go into $1$ so we put a $0$ in the first place and keep searching. In this example, we keep searching until we get to $1001$ in which $111$ can be divided into exactly once. This is actually fairly typical in binary long division - it either goes into the number or doesn’t:

The next step of multiplication is relatively trivial since we’re working with zeroes or ones! So we put the divisor underneath, subtract to get the remainder and carry down the next digit:

Now, $111$ doesn’t go into $100$ so we put a $0$ within the next position of the quotient and carry down the next number:

$111$ does go into $1000$ so we add a one to the quotient and work out the remainder (plus carry down the next digit):

We carry on repeating this pattern: $111$ doesn’t go into $11$ so we put a zero in the quotient and carry down the next number:

$111$ goes into $111$ exactly once so we place a $1$ in the final position and round off the remainder:

If we change our binary number to decimal, as expected, we get $21$.

What about fractional numbers?

What if we didn’t have a clean division at the end? For the purposes of simplicity, for now we’ll just treat the remainder as exactly that, the remainder:

In this example, we have $\dfrac{10}{8}$ which will result in $1$ with a remainder of $2$. We’ll dig into how to represent fractional numbers in computer memory in a future post.

That’s it!

Hopefully you found this post useful. I’ll be following up with the two’s complement method of division in a couple of weeks.