Next: 1.4 Using the shift
Up: 1 Multiple Precision Arithmetic
Previous: 1.2 Multiplication 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 multiplechoice 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 bookkeeping by performing the ``short'' division
(v_{1}^{ ... }v_{q}) = u×(w_{1}^{ ... }w_{q}) + t
where t < u. We first compute
(u, 0, v_{1}) = (w_{1}, t_{1}). From then on
we have the inductive approach
(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} = 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_{0}^{ ... }v_{q}) = (u_{1}^{ ... }u_{q})×w + (t_{1}^{ ... }t_{q})
where v_{0} < u_{1} and
(t_{1}^{ ... }t_{q}) < (u_{1}^{ ... }u_{q}), a ``good guess'' for w
is provided by x which is obtained by
(u_{1}, v_{0}, v_{1}) = (x, y)
(so that y < u_{1}). The following lemma tells us just
how good the guess is
Lemma 1
If
2
^{ . }u_{1} + 1
M then we have
x  2
w x.
Proof.
Using
(
u_{2}^{ ... }u_{q})
M^{q  1}  1 and
(
v_{2}^{ ... }v_{q})
M^{q  1} we obtain the
following inequalities
u_{1}^{ . }M^{q  1} 
(u_{1}^{ ... }u_{q}) 
u_{1}M^{q  1} + M^{q  1}  1 

(v_{0}^{ . }M + v_{1})^{ . }M^{q  1} 
(v_{0}^{ ... }v_{q}) 
(v_{0}^{ . }M + v_{1})^{ . }M^{q  1} + M^{q  1}  1 

which we can combine with the Euclidean inequalities
u_{1}^{ . }x 
v_{0}^{ . }M + v_{1} 
u_{1}^{ . }(x + 1)  1 

(u_{1}^{ ... }u_{q})×w 
(v_{0}^{ ... }v_{q}) 
(u_{1}^{ ... }u_{q})×(w + 1)  1 

We then obtain
As a consequence
w < (
x + 1) or equivalently (since these are
integers)
w x. The reverse comparison is provided by
It follows that
u_{1}^{ . }x < (
u_{1} + 1)
^{ . }(
w + 1) or (since we have
integers on both sides)
u_{1}^{ . }x u_{1}^{ . }(
w + 1) +
w. Now the
condition
v_{0} <
u_{1} implies that
x (
M  1). So if
w M  1,
then we certainly have the inequality
x w + 2 as required. Thus
we may assume that
w <
M  1. From the assumption
2
^{ . }u_{1} M  1
we obtain
w <
u_{1}^{ . }2. Combining this with the above we see
that
u_{1}^{ . }x u_{1}^{ . }(
w + 1) +
w <
u_{1}^{ . }(
w + 3)
or equivalently
x w + 2 as required.
Using this lemma, we see that we can give an algorithm for the long
division
(v_{1}^{ ... }v_{p}) = (u_{1}^{ ... }u_{q})×(w_{0}^{ ... }w_{r}) + (t_{1}^{ ... }t_{s})
that involves making one out of three choices. In order to apply the
lemma we must first normalise the divisor
(u_{1}^{ ... }u_{q}). So as a
first step we compute
(u_{1}, 1, 0) = (t,). If = 1, then we
take d = 1, other wise we compute
(t, 1, 0) = (d, r). Thus in every
case we have d is the integer part of M/(u_{1} + 1). We now take
(x_{1}^{ ... }x_{q}) 
= 
d×(u_{1}^{ ... }u_{q}) 

(y_{0}^{ ... }y_{p}) 
= 
d×(v_{1}^{ ... }v_{p}) 

Here we take y_{0} = 0 if necessary. We check easily that this step
also ensures that y_{0} < x_{1}. Next we initialise
(t_{0, 0}^{ ... }t_{0, q  1}) = (y_{0}^{ ... }y_{q  1}).
We can then perform the long division
by induction as follows. Let
(x_{1}, 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_{1}^{ ... }x_{q}) = (
z_{i, 0}^{ ... }z_{i, q  1}) 
^{ . }M^{q}
If = 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 = 1 and) we compute
(
z_{i, 0}^{ ... }z_{i, q  1}) + (
x_{1}^{ ... }x_{q}) = (
^{ ... }) +
^{ . }M^{q}
Now, if = 1 then we take
(t_{i + 1, 0}^{ ... }t_{i + 1, q  1}) = (^{ ... }) and
(g_{i}, 1, 0) = (w_{i}, 0). Finally, if we have = 0, then we put
(
^{ ... }) + (
x_{1}^{ ... }x_{q}) = (
t_{i + 1, 0}^{ ... }t_{i + 1, q  1}) +
^{ . }M^{q}
We note that = 1 is ensured by the lemma above. We put
(g_{i}, 2, 0) = (w_{i}, 0) in this case. After r = p  q steps we obtain the
identity
(y_{0}^{ ... }y_{p}) = (x_{1}^{ ... }x_{q})×(w_{0}^{ ... }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_{1}^{ ... }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_{0}u_{1}^{ ... }u_{q})
of the form
(10u_{2}^{ ... }u_{q}). In this case, the division of
(v_{0}^{ ... }v_{q}) always yields one of v_{0} or v_{0}  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_{1}^{ ... }u_{q}) we first compute
(u_{1}, 1, 0) = (t,) and if
= 1 we put d = 1. Otherwise, we compute
(t, 1, 1) = (d, r).
Thus, in every case d is the integer part of
(M + 1)/(u_{1} + 1). As
before, we multiply by d
(x_{1, 0}^{ ... }x_{1, q}) 
= 
d×(u_{1}^{ ... }u_{q}) 

(y_{1, 0}^{ ... }y_{1, p}) 
= 
d×(v_{1}^{ ... }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
(0, x_{1, 1}, 0) 
= (c_{i}, 1) 
(x_{1, 1}), 1, 0) 
= (t_{i},) 

if = 0 

(t_{i}, c_{i}, 0) 
= (d_{i}, r) 

if = 1 

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 3 we obtain
(
x_{i, 0}x_{i, 1}x_{i, 2}^{ ... }) = (10
x_{i, 2}^{ ... }) as required.
Assuming this for the moment we see that have removed all
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.
Next: 1.4 Using the shift
Up: 1 Multiple Precision Arithmetic
Previous: 1.2 Multiplication Algorithm
Kapil Hari Paranjape
20021020