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×(v<sub>1</sub> <sup>...</sup> v<sub>p</sub>) = (w<sub>0</sub>w<sub>1</sub> <sup>...</sup> w<sub>p</sub>). Actually we will need the more general ``linear form'' operation (we will assume that q $\geq$ p + 1 by padding t by zeros if necessary)

u×(v₁ ^... v_p) + (t₀ ^... t_q) = (w₀ ^... w_{q + 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

$$\tt mul$$ (x_p, y_p) =

$$\rho_{1}^{} \tt add$$ =

$$\mu_{1}^{} \tt add$$ =

$$\tt mul$$ (x_{p - i}, y_{p - i}) =

$$\rho_{i+1}^{} \tt add \rho_{i}^{}$$ =

$$\mu_{i+1}^{} \tt add \mu_{i}^{}$$ =

As before the first three steps are a special case of the latter three when we put $\rho_{0}^{}$ = 0 = $\mu_{0}^{}$ and z_p = t_p. There are q + 2 cycles. The $\tt mul$ operation actually takes place only in the first p cycles (in the remaining cases x_j and y_j are zero). The last $\tt add$ 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 $\geq$ p + q + 1)

(u₁ ^... u_p)×(v₁ ^... v_q) + (t₀ ^... t_{s - 1}) = (w₀ ^... w_s)

We see that this is achieved by intermediate computations of the form

u_p×(v₁ ^... v_q) + (t₀ ^... t_{s - 1}) = (z_{0, p} ^... z_{s, p})

u_{p - i}×(v₁ ^... v_q) + (z_{0, p - i + 1} ^... z_{s - i, p - i + 1}) = (z_{0, p - i} ^... z_{s - i, p - i})

Then w_{s - i} = z_{s - i, p - i} since the (s - i)-th ``digit'' z_{s - i, p - i} is not affected by subsequent computations. If we initialise (z_{0, p + 1} ^... z_{s, p + 1}) to be equal to (t₀, ^... t_{s - 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.