Next: 1.3 Long Division Algorithm Up: 1 Multiple Precision Arithmetic Previous: 1.1 Addition and Subtraction

## 1.2 Multiplication Algorithm

As is to be expected, multiplication is more complicated. The usual method of multiplication requires simultaneous summation of multiple rows of decimal numbers. The carry over from addition thus becomes quite large, whereas our basic routines can only handle a carry of 0 or 1. It is best to proceed slowly!

First of all we look at a procedure to multiply by a single digit'' u and perform the calculation, u×(v1 ... vp) = (w0w1 ... wp). Actually we will need the more general linear form'' operation (we will assume that q p + 1 by padding t by zeros if necessary)

u×(v1 ... vp) + (t0 ... tq) = (w0 ... wq + 1)

More diagrammatically,

 v1 v2 ... vp - 1 vp × u + t0 t1 t2 t3 ... tq - 1 tq x1 x2 x3 ... xp y1 y2 ... yp - 1 yp z0 z1 z2 z3 ... zq - 1 zq zq + 1 w0 w1 w1 w2 ... wq - 1 wq wq + 1

The usual multiplication procedures leads to certain intermediate digits which we denote by x, y, z as above. We obtain the identities
 (xp, yp) = (u, vp) (wq + 1,) = (tp, y0, 0) (zq,) = (tq - 1, xp, 0) (xp - i, yp - i) = (u, vp - i) (wq + 1 - i,) = (zq + 1 - i, yp - i,) (zq - i,) = (tq - i - 1, xp - i,)

As before the first three steps are a special case of the latter three when we put = 0 = and zp = tp. There are q + 2 cycles. The operation actually takes place only in the first p cycles (in the remaining cases xj and yj are zero). The last operation does not take place on the last cycle. Thus, are at most p + 2q + 3 steps.

Now we use the above routine repeatedly to obtain the general linear form, (where as before we assume that s p + q + 1)

(u1 ... up)×(v1 ... vq) + (t0 ... ts - 1) = (w0 ... ws)

We see that this is achieved by intermediate computations of the form
 up×(v1 ... vq) + (t0 ... ts - 1) = (z0, p ... zs, p) up - i×(v1 ... vq) + (z0, p - i + 1 ... zs - i, p - i + 1) = (z0, p - i ... zs - i, p - i)

Then ws - i = zs - i, p - i since the (s - i)-th digit'' zs - i, p - i is not affected by subsequent computations. If we initialise (z0, p + 1 ... zs, p + 1) to be equal to (t0, ... ts - 1), then first computation is a special case of the second. We will perform p cycles, each a linear form as above of the length q + 2s + 3. Thus the number of steps is order of pq + 2ps + 3p steps.

While this looks a bit complex, it is still not the most efficient when the p and q are large enough to allow us to use more (order linear in p and q) book-keeping'' steps in exchange for efficiency.

Next: 1.3 Long Division Algorithm Up: 1 Multiple Precision Arithmetic Previous: 1.1 Addition and Subtraction
Kapil Hari Paranjape 2002-10-20