Page 271 - Discrete Mathematics and Its Applications

250 4 / Number Theory and Cryptography
EXAMPLE 8
Algorithms for Integer Operations
The algorithms for performing operations with integers using their binary expansions are ex-
tremely important in computer arithmetic. We will describe algorithms for the addition and the
multiplication of two integers expressed in binary notation. We will also analyze the compu-
tational complexity of these algorithms, in terms of the actual number of bit operations used.
Throughout this discussion, suppose that the binary expansions of a and b are
a = (a n−1 a n−2 ...a 1 a 0 ) 2 ,b = (b n−1 b n−2 ...b 1 b 0 ) 2 ,
so that a and b each have n bits (putting bits equal to 0 at the beginning of one of these expansions
if necessary).
We will measure the complexity of algorithms for integer arithmetic in terms of the number
of bits in these numbers.
ADDITION ALGORITHM Consider the problem of adding two integers in binary notation.
A procedure to perform addition can be based on the usual method for adding numbers with
pencil and paper. This method proceeds by adding pairs of binary digits together with carries,
when they occur, to compute the sum of two integers. This procedure will now be specified
in detail.
To add a and b, first add their rightmost bits. This gives
a 0 + b 0 = c 0 · 2 + s 0 ,
where s 0 is the rightmost bit in the binary expansion of a + b and c 0 is the carry, which is either
0 or 1. Then add the next pair of bits and the carry,
a 1 + b 1 + c 0 = c 1 · 2 + s 1 ,
where s 1 is the next bit (from the right) in the binary expansion of a + b, and c 1 is the carry.
Continue this process, adding the corresponding bits in the two binary expansions and the carry,
to determine the next bit from the right in the binary expansion of a + b. At the last stage, add
a n−1 ,b n−1 , and c n−2 to obtain c n−1 · 2 + s n−1 . The leading bit of the sum is s n = c n−1 . This
procedure produces the binary expansion of the sum, namely, a + b = (s n s n−1 s n−2 ...s 1 s 0 ) 2 .
Add a = (1110) 2 and b = (1011) 2 .
Solution: Following the procedure specified in the algorithm, first note that
a 0 + b 0 = 0 + 1 = 0 · 2 + 1,
so that c 0 = 0 and s 0 = 1. Then, because
a 1 + b 1 + c 0 = 1 + 1 + 0 = 1 · 2 + 0,
it follows that c 1 = 1 and s 1 = 0. Continuing,
a 2 + b 2 + c 1 = 1 + 0 + 1 = 1 · 2 + 0,