Information Technology Reference
In-Depth Information
Figure 1.3.
Adding two multidigit numbers
Procedure PROC2:
You are given two multidigit numbers as input, each with the same number of
digits:
x
1
x
2
...
x
k
y
1
y
2
...
y
k
You will return a number with one additional digit as output:
z
0
z
1
z
2
...
z
k
1.
Start at the right-hand side of the inputs (looking at
x
k
and
y
k
).
Call PROC1 with
a
as
0
,
t
as
x
k
, and
b
as
y
k
.
Let
z
k
be the
s
returned. (Keep the
c
returned for the next step.)
2.
Move over one step to the left (looking at
x
k
−
1
and
y
k
−
1
).
Call PROC1 with
a
as the
c
from the previous step,
t
as
x
k
−
1
, and
b
as
y
k
−
1
.
Let
z
k
−
1
be the
s
returned. (Keep the
c
returned for the next step.)
3.
Continue in this way through all the digits, from right to left, filling out in turn,
z
k
−
2
,
z
k
−
3
, ...,
z
3
,
z
2
,
z
1
.
4.
Let
z
0
be the final
c
returned by PROC1 (with
x
1
and
y
1
).
If PROC1 is called on
8
,
9
, and
6
, it will return
23
:
u
and
v
will be
1
and
5
, and
u
and
v
will be
1
and
3
,so
c
will be
2
and
s
will be
3
.
Note that it is not the business of the procedure to explain
why
the operations are
done. It needs to make a decision about a final carry digit
c
. But as far as the procedure
is concerned, the only thing that matters is what the final answer should be.
PROC2
Now, building on the procedure PROC1, consider instructions for adding two multi-
digit numbers. In this case, you know that you have to go from right to left, keeping
track of the carry digits along the way. A procedure PROC2 for doing this is shown
in figure 1.3. Trace the behavior of this procedure when the inputs are
747
and
281
(so that
k
=
3
):
=
0
,
t
=
7
, and
b
=
1
.
1.
Starting at the right side, call PROC1 with
a
=
0
and
s
=
8
.So
z
3
will be
8
.
It will return
c
