Arithmetic for Computers PDF

190 Chapter 3 Arithmetic for Computers 3.1 Introduction Computer words are composed of bits; thus, words can be represented as binary numbers. Chapter 2 shows that integers can...

190 Chapter 3 Arithmetic for Computers 3.1 Introduction Computer words are composed of bits; thus, words can be represented as binary numbers. Chapter 2 shows that integers can be represented either in decimal or binary form, but what about the other numbers that commonly occur? For example: n What about fractions and other real numbers? n What happens if an operation creates a number bigger than can be represented? n And underlying these questions is a mystery: How does hardware really multiply or divide numbers? The goal of this chapter is to unravel these mysteries—including representation of real numbers, arithmetic algorithms, hardware that follows these algorithms— and the implications of all this for instruction sets. These insights may explain quirks that you have already encountered with computers. Moreover, we show how to use this knowledge to make arithmetic-intensive programs go much faster. Subtraction: Addition’s Tricky Pal 3.2 Addition and Subtraction No. 10, Top Ten Courses for Athletes at a Addition is just what you would expect in computers. Digits are added bit by bit Football Factory, David from right to left, with carries passed to the next digit to the left, just as you would Letterman et al., Book of do by hand. Subtraction uses addition: the appropriate operand is simply negated Top Ten Lists, 1990 before being added. Binary Addition and Subtraction Let’s try adding 6ten to 7ten in binary and then subtracting 6ten from 7ten in binary. EXAMPLE 00000000 00000000 00000000 00000111two = 7ten + 00000000 00000000 00000000 00000110two = 6ten = 00000000 00000000 00000000 00001101two = 13ten The 4 bits to the right have all the action; Figure 3.1 shows the sums and carries. Parentheses identify the carries, with the arrows illustrating how they are passed.  3.2 Addition and Subtraction 191 (0) (0) (1) (1) (0) (Carries)... 0 0 0 1 1 1... 0 0 0 1 1 0... (0) 0 (0) 0 (0) 1 (1) 1 (1) 0 (0) 1 FIGURE 3.1 Binary addition, showing carries from right to left. The rightmost bit adds 1 to 0, resulting in the sum of this bit being 1 and the carry out from this bit being 0. Hence, the operation for the second digit to the right is 0 + 1 + 1. This generates a 0 for this sum bit and a carry out of 1. The third digit is the sum of 1 + 1 + 1, resulting in a carry out of 1 and a sum bit of 1. The fourth bit is 1 + 0 + 0, yielding a 1 sum and no carry. Subtracting 6ten from 7ten can be done directly: ANSWER 00000000 00000000 00000000 00000111two = 7ten – 00000000 00000000 00000000 00000110two = 6ten = 00000000 00000000 00000000 00000001two = 1ten or via addition using the two’s complement representation of −6: 00000000 00000000 00000000 00000111two = 7ten _ + 11111111 11111111 11111111 11111010two = 6ten = 00000000 00000000 00000000 00000001two = 1ten Recall that overflow occurs when the result from an operation cannot be represented with the available hardware, in this case a 32-bit word. When can overflow occur in addition? When adding operands with different signs, overflow cannot occur. The reason is the sum must be no larger than one of the operands. For example, −10 + 4 = −6. Since the operands fit in 32 bits and the sum is no larger than an operand, the sum must fit in 32 bits as well. Therefore, no overflow can occur when adding positive and negative operands. There are similar restrictions to the occurrence of overflow during subtract, but it’s just the opposite principle: when the signs of the operands are the same, overflow cannot occur. To see this, remember that c − a = c + (−a) because we subtract by negating the second operand and then add. Therefore, when we subtract operands of the same sign we end up adding operands of different signs. From the prior paragraph, we know that overflow cannot occur in this case either. Knowing when an overflow cannot occur in addition and subtraction is all well and good, but how do we detect it when it does occur? Clearly, adding or subtracting two 32-bit numbers can yield a result that needs 33 bits to be fully expressed. 192 Chapter 3 Arithmetic for Computers FIGURE 3.2 Overflow conditions for addition and subtraction. The lack of a 33rd bit means that when an overflow occurs, the sign bit is set with the value of the result instead of the proper sign of the result. Since we need just one extra bit, only the sign bit can be wrong. Hence, overflow occurs when adding two positive numbers and the sum is negative, or vice versa. This spurious sum means a carry out occurred into the sign bit. Overflow occurs in subtraction when we subtract a negative number from a positive number and get a negative result, or when we subtract a positive number from a negative number and get a positive result. Such a ridiculous result means a borrow occurred from the sign bit. Figure 3.2 shows the combination of operations, operands, and results that indicate an overflow. We have just seen how to detect overflow for two’s complement numbers in a computer. What about overflow with unsigned integers? Unsigned integers are commonly used for memory addresses where overflows are ignored. Arithmetic Logic Fortunately, the compiler can easily check for unsigned overflow using a branch Unit (ALU) Hardware that performs addition, instruction. Addition has overflowed if the sum is less than either of the addends, subtraction, and usually whereas subtraction has overflowed if the difference is greater than the minuend. logical operations such as Appendix A describes the hardware that performs addition and subtraction, AND and OR. which is called an Arithmetic Logic Unit or ALU. Hardware/ The computer designer must decide how to handle arithmetic overflows. Although some languages like C and Java ignore integer overflow, languages like Ada and Software Fortran require that the program be notified. The programmer or the programming Interface environment must then decide what to do when an overflow occurs. Summary A major point of this section is that, independent of the representation, the finite word size of computers means that arithmetic operations can create results that are too large to fit in this fixed word size. It’s easy to detect overflow in unsigned numbers, although these are almost always ignored because programs don’t want to detect overflow for address arithmetic, the most common use of natural numbers. Two’s complement presents a greater challenge, yet some software systems require recognizing overflow, so today all computers have a way to detect it.  3.3 Multiplication 193 Some programming languages allow two’s complement integer arithmetic on Check variables declared byte and half, whereas RISC-V only has integer arithmetic Yourself operations on full words. As we recall from Chapter 2, RISC-V does have data transfer operations for bytes and halfwords. What RISC-V instructions should be generated for byte and halfword arithmetic operations? 1. Load with lb, lh; arithmetic with add, sub, mul, div, using and to mask result to 8 or 16 bits after each operation; then store using sb, sh. 2. Load with lb, lh; arithmetic with add, sub, mul, div; then store using sb, sh. Elaboration: One feature not generally found in general-purpose microprocessors is saturating operations. Saturation means that when a calculation overflows, the result is set to the largest positive number or the most negative number, rather than a modulo calculation as in two’s complement arithmetic. Saturation is likely what you want for media operations. For example, the volume knob on a radio set would be frustrating if, as you turned it, the volume would get continuously louder for a while and then immediately very soft. A knob with saturation would stop at the highest volume no matter how far you turned it. Multimedia extensions to standard instruction sets often offer saturating arithmetic. Elaboration: The speed of addition depends on how quickly the carry into the high- order bits is computed. There are a variety of schemes to anticipate the carry so that the worst-case scenario is a function of the log2 of the number of bits in the adder. These anticipatory signals are faster because they go through fewer gates in sequence, but it takes many more gates to anticipate the proper carry. The most popular is carry lookahead, which Section A.6 in Appendix A describes. 3.3 Multiplication Now that we have completed the explanation of addition and subtraction, we are ready to build the more vexing operation of multiplication. Multiplication is First, let’s review the multiplication of decimal numbers in longhand to remind vexation, Division is ourselves of the steps of multiplication and the names of the operands. For reasons as bad; The rule of that will become clear shortly, we limit this decimal example to using only the three doth puzzle me, digits 0 and 1. Multiplying 1000ten by 1001ten: And practice drives me mad. Anonymous, Elizabethan manuscript, 1570