1.3 Long Division Algorithm

This is by far the most complicated procedure. The first point to note is that the school method for long division involves a ``guess''. We need to ensure that this guess is replaced a multiple-choice procedure (also characterised by a ``case'' statement). Moreover, the number of choices should be very small and not of the same size as the base M.

As for the case of multiplication we can understand some aspects of the relevant book-keeping by performing the ``short'' division

(v₁ ^... v_q) = u×(w₁ ^... w_q) + t

where t < u. We first compute $\tt div$ (u, 0, v₁) = (w₁, t₁). From then on we have the inductive approach $\tt div$ (u, t_i, v_{i + 1}) = (w_{i + 1}, t_{i + 1}). Clearly, the first step is a special case of the second by putting v₀ = 0. At the end t = t_q. Moreover, there are exactly q steps.

There are two procedures for long division, each with its own level of complexity. We note that in the division

(v₀ ^... v_q) = (u₁ ^... u_q)×w + (t₁ ^... t_q)

where v₀ < u₁ and (t₁ ^... t_q) < (u₁ ^... u_q), a ``good guess'' for w is provided by x which is obtained by $\tt div$ (u₁, v₀, v₁) = (x, y) (so that y < u₁). The following lemma tells us just how good the guess is

Lemma 1   If 2 ^. u₁ + 1 $\geq$ M then we have x - 2 $\leq$ w $\leq$ x.

Proof. Using (u₂ ^... u_q) $\leq$ M^{q - 1} - 1 and (v₂ ^... v_q) $\leq$ M^{q - 1} we obtain the following inequalities

$$\leq \leq$$ u₁ ^. M^{q - 1} u₁M^{q - 1} + M^{q - 1} - 1

$$\leq \leq$$ (v₀ ^. M + v₁) ^. M^{q - 1} (v₀ ^. M + v₁) ^. M^{q - 1} + M^{q - 1} - 1

which we can combine with the Euclidean inequalities

$$\leq \leq$$ u₁ ^. x u₁ ^. (x + 1) - 1

$$\leq \leq$$ (u₁ ^... u_q)×w (u₁ ^... u_q)×(w + 1) - 1

We then obtain

As a consequence w < (x + 1) or equivalently (since these are integers) w $\leq$ x. The reverse comparison is provided by

It follows that u₁ ^. x < (u₁ + 1) ^. (w + 1) or (since we have integers on both sides) u₁ ^. x $\leq$ u₁ ^. (w + 1) + w. Now the condition v₀ < u₁ implies that x $\leq$ (M - 1). So if w $\geq$ M - 1, then we certainly have the inequality x $\leq$ w + 2 as required. Thus we may assume that w < M - 1. From the assumption 2 ^. u₁ $\geq$ M - 1 we obtain w < u₁ ^. 2. Combining this with the above we see that

u₁ ^. x $$\leq$$ u₁ ^. (w + 1) + w < u₁ ^. (w + 3)

or equivalently x $\leq$ w + 2 as required. $\qedsymbol$

Using this lemma, we see that we can give an algorithm for the long division

(v₁ ^... v_p) = (u₁ ^... u_q)×(w₀ ^... w_r) + (t₁ ^... t_s)

that involves making one out of three choices. In order to apply the lemma we must first normalise the divisor (u₁ ^... u_q). So as a first step we compute $\tt add$ (u₁, 1, 0) = (t,$\rho$). If $\rho$ = 1, then we take d = 1, other wise we compute $\tt div$ (t, 1, 0) = (d, r). Thus in every case we have d is the integer part of M/(u₁ + 1). We now take

(x₁ ^... x_q) = d×(u₁ ^... u_q)

(y₀ ^... y_p) = d×(v₁ ^... v_p)

Here we take y₀ = 0 if necessary. We check easily that this step also ensures that y₀ < x₁. Next we initialise (t_{0, 0} ^... t_{0, q - 1}) = (y₀ ^... y_{q - 1}). We can then perform the long division by induction as follows. Let $\tt div$ (x₁, t_{i, 0}, t_{i, 1}) = (g_i, r); then g_i is our guess. We compute (and note that the z sequence cannot be longer than q due to the choice of g_i)

(t_{i, 0} ^... t_{i, q - 1}y_{q + i}) - g_i×(x₁ ^... x_q) = (z_{i, 0} ^... z_{i, q - 1}) - $$\rho$$ ^. M^q

If $\rho$ = 0 then we take (t_{i + 1, 0} ^... t_{i + 1, q - 1}) = (z_{i, 0} ^... z_{i, q - 1}) and w_i = g_i. Otherwise (we have $\rho$ = 1 and) we compute

(z_{i, 0} ^... z_{i, q - 1}) + (x₁ ^... x_q) = ($$\tilde{z}_{i,0}^{}$$ ^... $$\tilde{z}_{i,q-1}^{}$$) + $$\mu$$ ^. M^q

Now, if $\mu$ = 1 then we take (t_{i + 1, 0} ^... t_{i + 1, q - 1}) = ($\tilde{z}_{i,0}^{}$ ^... $\tilde{z}_{i,q-1}^{}$) and $\tt add$ (g_i, 1, 0) = (w_i, 0). Finally, if we have $\mu$ = 0, then we put

($$\tilde{z}_{i,0}^{}$$ ^... $$\tilde{z}_{i,q-1}^{}$$) + (x₁ ^... x_q) = (t_{i + 1, 0} ^... t_{i + 1, q - 1}) + $$\mu{^\prime}$$ ^. M^q

We note that $\mu{^\prime}$ = 1 is ensured by the lemma above. We put $\tt add$ (g_i, 2, 0) = (w_i, 0) in this case. After r = p - q steps we obtain the identity

(y₀ ^... y_p) = (x₁ ^... x_q)×(w₀ ^... w_r) + (t_{r + 1, 0} ^... t_{r + 1, q - 1})

From the choices for x's and y's we see that d exactly divides the remainder, so we perform short division to obtain

(t_{r + 1, 0} ^... t_{r + 1, q - 1}) = d×(t₁ ^... t_q)

This completes the long division which takes about 3rq steps upto terms linear in p and q (such as additions and subtractions).

Another way to simplify the guessing process is to take (u₀u₁ ^... u_q) of the form (10u₂ ^... u_q). In this case, the division of (v₀ ^... v_q) always yields one of v₀ or v₀ - 1 as the quotient. The main question is then how to perform the necessary normalisation (to bring the u into this form). Starting with (u₁ ^... u_q) we first compute $\tt add$ (u₁, 1, 0) = (t,$\rho$) and if $\rho$ = 1 we put d = 1. Otherwise, we compute $\tt div$ (t, 1, 1) = (d, r). Thus, in every case d is the integer part of (M + 1)/(u₁ + 1). As before, we multiply by d

(x_{1, 0} ^... x_{1, q}) = d×(u₁ ^... u_q)

(y_{1, 0} ^... y_{1, p}) = d×(v₁ ^... v_p)

Where we put x_{1, 0} = 0 and y_{1, 0} = 0 if there is no carry over. Now, if x_{i, 1} = 0 (then x_{i, 0} = 1 is forced) we stop. Otherwise, we perform the following steps

$$\tt sub \tt add \rho$$ = (c_i, 1)

$$\rho \tt div$$ = (d_i, r)

$$\rho$$ d_i = c_i

Thus in every case, we have d_i is the integer part of M(M - x_{1, 1})/(x_{i, i} + 1). Now, we multiply by (1.d_i)

(x_{i + 1, 0} ^... x_{i + 1, q}.x_{i + 1, q + 1} ^... ) = (1.d_i)×(x_{i, 0} ^... x_{i, q}.x_{i, q + 1} ^... )

(y_{i + 1, 0} ^... y_{i + 1, p}.y_{i + 1, q + 1} ^... ) = (1.d_i)×(y_{i, 0} ^... y_{i, q}.y_{i, q + 1} ^... )

where we use the (.) to keep the notation simple and note that there are only finitely many terms after it. We now iterate over i.

Lemma 2   For some i $\leq$ 3 we obtain (x_{i, 0}x_{i, 1}x_{i, 2} ^... ) = (10x_{i, 2} ^... ) as required.

Assuming this for the moment we see that have removed all $\tt div$ operations in the iterative part of the long division process. We leave it to the reader to make an algorithm out of this procedure. The proof of the lemma is a somewhat complicated exercise which we skip as well.