## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 4.1 ADDITION OF NATURAL NUMBERS

### 4.1.1 Basic Algorithm

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 + cin where cin is an initial carry equal to 0 or 1.

```q(0): =c_in;
for i in 0..n-1 loop
if x(i)+y(i)+q(i)>B-1 then q(i+1):=1; else q(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 qi+1 can be calculated as follows:

```if p(x(i), y(i))=1 then q(i+1):=q(i); else q(i+1):=g(x(i),
y(i)); end if;```

The corresponding modified algorithm is the following one.

```--computation of the generation and propagation conditions:
for i in 0..n-1 loop g(i):=g(x(i),y(i)); p(i):=p(x(i),y(i));
end loop;
--carry computation:
q(0):=c_in;
for i in 0..n-1 loop
if p(i)=1 then q(i+1):=q(i); else q(i+1):=g(i); end if;
end loop;
-sum computation
for i in 0..n-1 loop z(i):=(x(i)+y(i)+q(i)) mod B; end loop; z(n):=q(n); ...```

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required