2. Arithmetic
Algorithms for doing elementary arithmetic operations such as addition,
multiplication, and division have a. very long history, dating back to
the origins of algorithm studies in the work of the Arabic mathematician
al-Khowdrizmi, with roots going even further back to the Greeks and the
Babylonians.
Though the situation is beginning to change, the of many
computer systems is their capability for doing fast, accurate numerical cal-
culations. Computers have built-in capabilities to perform arithmetic on in-
tegers and floating-point representations of real numbers; for example, Pascal
allows numbers to be of type integer or with all of the normal arithmetic
operations defined on both types. Algorithms come into play when the opera-
tions must be performed on more complicated mathematical objects, such as
polynomials or matrices.
In this section, we’ll look at Pascal implementations of some simple
algorithms for addition and multiplication of polynomials and matrices. The
algorithms themselves are well-known and straightforward; we’ll be examining
sophisticated algorithms for these problems in Chapter 4. Our main purpose
in this section is to get used to treating mathematical objects as objects
for manipulation by Pascal programs. This translation from abstract data to
something which can be processed by a computer is fundamental in algorithm
design. We’ll see many examples throughout this book in which a proper
representation can lead to an efficient algorithm and vice versa. In this
chapter, we’ll use two fundamental ways of structuring data, the array and
the linked list. These data structures are used by many of the algorithms in
this book; in later sections we’ll study some more advanced data structures.
Polynomials
Suppose that we wish to write a program that adds two polynomials: we would
23
24
2

for i:=O to do :=O;
for i:=O to N-l do
for to N-l do
ARITHMETIC
Also, the declaration of has to be changed to twice as
many coefficients for the product. Each of the N coefficients of p is multiplied
by each of the N coefficients of so this is clearly a quadratic algorithm.
An advantage of representing a polynomial by an array containing its
coefficients is that it’s easy to reference any coefficient directly; a disadvantage
is that space may have to be saved for more numbers than necessary. For
example, the program above couldn’t reasonably be used to multiply

even though the input involves only four and the output only three.
An alternate way to represent a is to use a linked list. This
involves storing items in noncontiguous memory locations, with each item
containing the address of the next. The Pascal mechanisms for linked lists are
somewhat more complicated than for arrays. For example, the following pro-
gram computes the sum of two polynomials using a linked list representation
(the bodies of the and add functions and the writelist procedure are
given in the text following):
program output);
type link q =
node = record c: real; next: link end ;
integer; a: link;
function integer) : link;
procedure link);
function q: link) : link;
begin
new(z);


as before, and constructs the linked list which represents the corresponding
polynomial:
function (N: integer) : link;
var i: integer; link;
begin
for i:=O N-l do
begin end;

end
The dummy node z is used here to hold the link which points to the first node
on the list while the list is being constructed. After this list is built, is set
to link to itself. This ensures that once we reach the end of a list, we stay
there. Another convention which is sometimes convenient, would be to leave z
pointing to the beginning, to provide a way to get from the back to the front.
Finally, the program which adds two polynomials constructs a new list
in a manner similar to readlist, calculating the coefficients for the result
by stepping through the argument lists and adding together corresponding
coefficients:
27
function q: link): link;
var : link ;
begin
repeatuntil and

end ;
Employing linked lists in this way, we use only as many nodes as are
required by our program. As gets larger, we simply make more calls on new.