Consider the base-*B* representations of two *n*-digit numbers:

The following (pencil and paper) algorithm computes the (*n* + 1)-digit representation of *z* = *x* + *y* + *c*_{in} where *c*_{in} is an initial carry equal to 0 or 1.

**Algorithm 4.1 Classic Addition**

q(0): =c_in;foriin0..n-1loopifx(i)+y(i)+q(i)>B-1thenq(i+1):=1;elseq(i+1):=0;end if; z(i):=(x(i)+y(i)+q(i)) mod B;end loop;z(n):=q(n);

As *q*(*i* + 1) is a function of *q*(*i*) the execution time of Algorithm 4.1 is proportional to *n*. In order to reduce the execution time of each iteration step, Algorithm 4.1 can be modified. First, define two binary functions of two *B*-valued variables, namely, the propagate (*p*) and generate (*g*) functions:

The next carry *q*_{i+1} can be calculated as follows:

ifp(x(i), y(i))=1thenq(i+1):=q(i);elseq(i+1):=g(x(i), y(i));end if;

The corresponding modified algorithm is the following one.

**Algorithm 4.2 Carry-Chain Addition**

--computation of the generation and propagation conditions:foriin0..n-1loopg(i):=g(x(i),y(i)); p(i):=p(x(i),y(i));end loop;--carry computation: q(0):=c_in;foriin0..n-1loopifp(i)=1thenq(i+1):=q(i);elseq(i+1):=g(i);end if;end loop;-sum computationforiin0..n-1loopz(i):=(x(i)+y(i)+q(i)) mod B;end loop;z(n):=q(n); ...

Start Free Trial

No credit card required