1.1 Addition and Subtraction Algorithm

We now write the addition recipe using the usual method

	u1	u2	...	up
	v1	v2	...	vp
$$\rho$$	w1	w2	...	wp

Or more concisely

(u₁ ^... u_p) + (v₁ ^... v_p) = (w₁ ^... w_p) + $$\rho$$M^p = ($$\rho$$w₁ ^... w_p)

The identities that are satisfied are

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

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

We can clearly write these identities quite concisely by defining $\rho_{-1}^{}$ = 0. It is thus clear how to calculate this inductively for all i upto i = p. At the last stage the carry over is the extra $\rho$ = $\rho_{p}^{}$ in the answer.

A similar technique applies to the subtraction method. We write the identity

(u₁ ^... u_p) - (v₁ ^... v_p) = (w₁ ^... w_p) - $$\rho$$M^p

And find the identities

$$\rho_{0}^{} \tt sub$$ =

$$\rho_{i}^{} \tt sub \rho_{i-1}^{}$$ =

Again, putting $\rho_{-1}^{}$ = 0 combines the identities and we can easily compute these inductively. Note that $\rho$ = $\rho_{p}^{}$ is the ``extra'' borrow element and so if this is non-zero then (v₁ ^... v_p) is in fact more than (u₁ ^... u_p). We will see that this calculation is useful even in this case.

We note that the number of steps taken by both methods is equal to p.