Sunday, March 6, 2011

Computer Architecture # 03 : Arithmetic

3.1 Overview
In the previous chapter we explored a few ways that numbers can be represented in a digital computer, but we only brieﬂy touched upon arithmetic operations that can be performed on those numbers. In this chapter we cover four basic arithmetic operations: addition, subtraction, multiplication, and division. We
begin by describing how these four operations can be performed on ﬁxed point numbers, and continue with a description of how these four operations can be performed on ﬂoating point numbers.
Some of the largest problems, such as weather calculations, quantum mechanical simulations, and land-use modeling, tax the abilities of even today’s largest computers. Thus the topic of high-performance arithmetic is also important. We conclude the chapter with an introduction to some of the algorithms and techniques used in speeding arithmetic operations.

3.2 Fixed Point Addition and Subtraction
The addition of binary numbers and the concept of overﬂow were brieﬂy discussed in Chapter 2. Here, we cover addition and subtraction of both signed and unsigned ﬁxed point numbers in detail. Since the two’s complement representation of integers is almost universal in today’s computers, we will focus primarily
on two’s complement operations. We will brieﬂy cover operations on 1’s complement and BCD numbers, which have a foundational signiﬁcance for other areas of computing, such as networking (for 1’s complement addition) and hand-held calculators (for BCD arithmetic.)

3.2.1 TWO’S COMPLEMENT ADDITION AND SUBTRACTION
In this section, we look at the addition of signed two’s complement numbers. As we explore the addition of signed numbers, we also implicitly cover subtraction as well, as a result of the arithmetic principle:
a - b = a + (−b).

We can negate a number by complementing it (and adding 1, for two’s complement), and so we can perform subtraction by complementing and adding. This results in a savings of hardware because it avoids the need for a hardware subtractor. We will cover this topic in more detail later.

We will need to modify the interpretation that we place on the results of addition when we add two’s complement numbers. To see why this is the case, consider Figure 3-1. With addition on the real number line, numbers can be as large or as small as desired—the number line goes to  ±∞, so the real number line can accommodate numbers of any size. On the other hand, as discussed in Chapter 2, computers represent data using a ﬁnite number of bits, and as a result can only store numbers within a certain range. For example, an examination of Table 2.1 shows that if we restrict the size of a number to, for example, 3 bits, there will only be eight possible two’s complement values that the number can assume. In Figure 3-1 these values are arranged in a circle beginning with 000 and proceeding around the circle to 111 and then back to 000. The ﬁgure also shows the decimal equivalents of these same numbers.

Some experimentation with the number circle shows that numbers can be added or subtracted by traversing the number circle clockwise for addition and counter clockwise for subtraction. Numbers can also be subtracted by two’s complementing the subtrahend and adding. Notice that overﬂow can only occur for addition when the operands (“addend” and “augend”) are of the same sign. Furthermore, overﬂow occurs if a transition is made from +3 to −4 while proceeding around the number circle when adding, or from −4 to +3 while subtracting. (Two’s com

plement overﬂow is discussed in more detail later in the chapter.)