Let us consider short division, by which we mean a multiple-digit number divided by a single digit (see, e.g., post on number representation). We will assume , and .
We are interested in a quotient and a remainder such that with . Using that and we can deduce that which means that can be represented using or digits: (we may have in which case ).
We now have the following straightforward algorithm:
Algorithm S. Given and with and , this algorithm computes the quotient (we may have in which case if ) and the remainder such that , .
- S1. Set , .
- S2. Set , .
- S3. If then exit. Otherwise set and go to step S2.
By the definition of integer division and modulus, the quantities in step S2 imply for . Using this, we can show the correctness of the algorithm:
since . It is clear from the definition of that for . Considering now the definition of we see that since we will have for .
Note two important things: During the course of the algorithm, we only need to keep track of one -value, not one for each (it just made the analysis easier). Note also that each entry of can be overwritten with the coefficients/digits of , possibly saving some storage.