We consider the task of dividing a positive integer by another positive integer , thus obtaining a quotient and a remainder such that with .
The method presented here is based on The Classical Algorithms, Section 4.3.1, of The Art of Computer Programming, Volume 2, by Donald E. Knuth. The material is quite theory-heavy and if you are just looking for the main algorithm, you can skip to the bottom and Algorithm L.
We represent the numbers using radix and set
so is an -digit number and is an -digit number (see previous post for more details on representing multiple-precision numbers).
Two special cases are easily dealt with:
- If then and so and is the simple answer.
- If then is just a single digit and we use a short division algorithm instead.
So in the following we assume that .
We will approach the division algorithm from a top-level point of view. It is actually just a formalization of the well-known pencil-and-paper method:
Algorithm G. Given , and , , with , this algorithm outlines how to compute the quotient (we may have in which case if ) and the remainder such that , .
- G1. .
- G2. .
- G3. .
- G4. Set or, equivalently,
- G5. If then set and exit. Otherwise set and go to step G3.
An essential invariant of this algorithm is
This can be seen as follows. For the invariant is ensured by introducing a zero as the most significant digit of in step G1. For we see from steps G3 and G4 that and the inequality follows.
Note that the invariant implies that for . Furthermore we have that
from which we see that the quotients computed in step G3 are non-negative and smaller than , as they should be.
Finally, we can verify that the algorithm computes what we intended. We have
Now for some practical aspects. Note first that all of the variables can in fact be represented by a single variable and simply overwrite its digits along the way – thus ending up with the remainder. Note also that any of the remainder's digits may be zero.
Finally, how do we compute the quotient in step G3? That is in fact the central part of the division algorithm and is the subject of the rest of this post.
Let us now consider computing the quotient in step G3 in the case . We therefore assume , , and , , with and .
We wish to compute as fast as possible. How good is a 'first order' approximation, where we use just the two most-significant digits of and the most-significant digit of : ? First of all, if this quantity equals and we know that by assumption, so let us therefore study
This approximate quotient is never too small, as the following theorem states.
Theorem 1. With as defined above we have .
Assume then that . From the properties of the floor function we have and therefore . We then get
So and since we must have .
If and are scaled appropriately, will never be too large, either.
Theorem 2. With as defined above and , we have .
since . We cannot have since that would imply . The relation implies , from which we get
We then have
which implies .
We would expect to come even closer if we consider the 'second order' approximate quotient,
but how much closer? Given some approximate quotient , let us compute the corresponding second order residual
where is the first order residual,
By studying the sign of the second order residual we can now get closer to the true quotient.
Theorem 3. Let be any approximate quotient and the corresponding first order residual. Now if then .
So which implies .
Theorem 4. Let be any approximate quotient and the corresponding first order residual. Now if then .
This claims that , a contradiction, so our assumption must have been wrong.
We now have the following procedure for computing , a very close estimate to :
Algorithm Q. Let and , , with and (any digit of can be zero and note that the only digits accessed are , , , , and ). The algorithm computes an integer such that (Theorems 1 and 4).
- Q1. Set and . If (division overflow when ) set and (dealing with division overflow can be avoided by setting and if ).
- Q2. While and , set and (Theorem 2 assures that this while-loop is executed at most two times if . The check is not necessary but makes sure that we don't deal with numbers that are or larger in the subsequent comparison).
We can now combine Algorithm G with the just obtained knowledge of approximating the quotient in the following algorithm for long division:
Algorithm L. Given , and , , with , this algorithm computes the quotient (we may have in which case if ) and the remainder such that , .
- L1. Set such that (letting be a power of two is usually the best choice). Similarly, set (ensure gets digits, setting if necessary).
- L2. Set .
- L3. Find such that (use Algorithm Q described above).
- L4. Make the update .
- L5. If the subtraction of step L4 produces a borrow (the result is negative) do and .
- L6. Set .
- L7. If set and exit. Otherwise set and go to step L3.
The normalization in step L1 such that does two things. Firstly, it makes sure that the while-loop of the -computation executes at most two times. Secondly, the probability that the adding back in step L5 must be executed is of order (a proof can be found in Knuth's book).