janmr blog

Basic Multiple-Precision Short Division

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.