janmr blog

Basic Multiple-Precision Short Division

Let us consider short division, by which we mean a multiple-digit number u=(um1u1u0)bu = (u_{m-1} \ldots u_1 u_0)_b divided by a single digit vv (see, e.g., post on number representation). We will assume m1m \geq 1, um10u_{m-1} \neq 0 and 0<v<b0 < v < b.

We are interested in a quotient q=u/vq = \lfloor u/v \rfloor and a remainder rr such that u=qv+ru = q v + r with 0r<v0 \leq r < v. Using that bm1u<bmb^{m-1} \leq u < b^m and 0<v<b0 < v < b we can deduce that bm2<q<bmb^{m-2} < q < b^m which means that qq can be represented using m1m-1 or mm digits: q=(qm1q1q0)bq = (q_{m-1} \ldots q_1 q_0)_b (we may have qm1=0q_{m-1} = 0 in which case qm20q_{m-2} \neq 0).

We now have the following straightforward algorithm:

Algorithm S. Given u=(um1u1u0)bu = (u_{m-1} \ldots u_1 u_0)_b and 0<v<b0 < v < b with m1m \geq 1 and um10u_{m-1} \neq 0, this algorithm computes the quotient q=(qm1q1q0)b=u/vq = (q_{m-1} \ldots q_1 q_0)_b = \lfloor u/v \rfloor (we may have qm1=0q_{m-1} = 0 in which case qm20q_{m-2} \neq 0 if m>1m > 1) and the remainder r0r_0 such that u=qv+r0u = q v + r_0, 0r0<v0 \leq r_0 < v.

  • S1. Set rm0r_m \leftarrow 0, km1k \leftarrow m-1.
  • S2. Set qk(rk+1b+uk)/vq_k \leftarrow \lfloor (r_{k+1} b + u_k)/v \rfloor, rk(rk+1b+uk) mod vr_k \leftarrow (r_{k+1} b + u_k) \text{ mod } v.
  • S3. If k=0k=0 then exit. Otherwise set kk1k \leftarrow k-1 and go to step S2.

By the definition of integer division and modulus, the quantities in step S2 imply rk+1b+uk=qkv+rkr_{k+1} b + u_k = q_k v + r_k for k=0,1,,m1k = 0, 1, \ldots, m-1. Using this, we can show the correctness of the algorithm:

u=k=0m1ukbk=k=0m1(qkv+rkrk+1b)bk=k=0m1qkbkv+k=0m1rkbkk=1mrkbk=qv+r0rmbm=qv+r0\begin{aligned} u &= \sum_{k=0}^{m-1} u_k b^k = \sum_{k=0}^{m-1} (q_k v + r_k - r_{k+1} b) b^k \\ &= \sum_{k=0}^{m-1} q_k b^k v + \sum_{k=0}^{m-1} r_k b^k - \sum_{k=1}^m r_k b^k \\ &= q v + r_0 - r_m b^m = q v + r_0 \end{aligned}

since rm=0r_m = 0. It is clear from the definition of rkr_k that 0rk<v0 \leq r_k < v for k=0,1,,mk = 0, 1, \ldots, m. Considering now the definition of qkq_k we see that since rk+1b+uk(v1)b+b1=bv1r_{k+1} b + u_k \leq (v-1) b + b-1 = b v - 1 we will have 0qk<b0 \leq q_k < b for k=0,1,,m1k = 0, 1, \ldots, m-1.

Note two important things: During the course of the algorithm, we only need to keep track of one rr-value, not one for each kk (it just made the analysis easier). Note also that each entry of uu can be overwritten with the coefficients/digits of qq, possibly saving some storage.