Exercise 3.1 The book shows how to add and subtract binary and decimal numbers. However, other numbering systems are also very popular when dealing with computers. The octal (base 8) numbering system is one of these. The following table shows pairs of octal numbers.
3.1.1 [5] <3.2> What is the sum of A and B if they represent unsigned 12-bit octal numbers? The result should be written in octal. Show your work.
3.1.2 [5] <3.2> What is the sum of A and B if they represent signed 12-bit octal numbers stored in sign-magnitude format? The result should be written in octal. Show your work.
3.1.3 [10] <3.2> Convert A into a decimal number, assuming it is unsigned. Repeat assuming it stored in sign-magnitude format. Show your work.
The following table also shows pairs of octal numbers.
3.1.4 [5] <3.2> What is A – B if they represent unsigned 12-bit octal numbers? The result should be written in octal. Show your work.
3.1.5 [5] <3.2> What is A – B if they represent signed 12-bit octal numbers stored in sign-magnitude format? The result should be written in octal. Show your work.
3.1.6 [10] <3.2> Convert A into a binary number. What makes base 8 (octal) an attractive numbering system for representing values in computers?
Exercise 3.2
Hexadecimal (base 16) is also a commonly used numbering system for representing values in computers. In fact, it has become much more popular than octal. The following table shows pairs of hexadecimal numbers.
3.2.1 [5] <3.2> What is the sum of A and B if they represent unsigned 16-bit hexadecimal numbers? The result should be written in hexadecimal. Show your work.
3.2.2 [5] <3.2> What is the sum of A and B if they represent signed 16-bit hexadecimal numbers stored in sign-magnitude format? The result should be written in hexadecimal. Show your work.
3.2.3 [10] <3.2> Convert A into a decimal number, assuming it is unsigned. Repeat assuming it stored in sign-magnitude format. Show your work.
The following table also shows pairs of hexadecimal numbers.
Get 3.2.3 exercise solution
3.2.4 [5] <3.2> What is A – B if they represent unsigned 16-bit hexadecimal numbers? The result should be written in hexadecimal. Show your work.
3.2.5 [5] <3.2> What is A – B if they represent signed 16-bit hexadecimal numbers stored in sign-magnitude format? The result should be written in hexadecimal. Show your work.
3.2.6 [10] <3.2> Convert A into a binary number. What makes base 16 (hexadecimal) an attractive numbering system for representing values in computers?
Exercise 3.3
Overflow occurs when a result is too large to be represented accurately given a finite word size. Underflow occurs when a number is too small to be represented correctly—a negative result when doing unsigned arithmetic, for example. (The case when a positive result is generated by the addition of two negative integers is also referred to as underflow by many, but in this textbook, that is considered an overflow.) The following table shows pairs of decimal numbers.
3.3.1 [5] <3.2> Assume A and B are unsigned 8-bit decimal integers. Calculate A – B. Is there overflow, underflow, or neither?
3.3.2 [5] <3.2> Assume A and B are signed 8-bit decimal integers stored in signmagnitude format. Calculate A + B. Is there overflow, underflow, or neither?
3.3.3 [5] <3.2> Assume A and B are signed 8-bit decimal integers stored in signmagnitude format. Calculate A – B. Is there overflow, underflow, or neither? The following table also shows pairs of decimal numbers.
Get 3.3.3 exercise solution
3.3.5 [10] <3.2> Assume A and B are signed 8-bit decimal integers stored in two’s complement format. Calculate A – B using saturating arithmetic. The result should be written in decimal. Show your work.
3.3.6 [10] <3.2> Assume A and B are unsigned 8-bit integers. Calculate A + B using saturating arithmetic. The result should be written in decimal. Show your work.
Exercise 3.4
Let’s look in more detail at multiplication. We will use the numbers in the following table.
3.4.1 [20] <3.3> Using a table similar to that shown in Figure 3.7, calculate the product of the octal unsigned 6-bit integers A and B using the hardware described in Figure 3.4. You should show the contents of each register on each step.
Get 3.4.1 exercise solution
3.4.2 [20] <3.3> Using a table similar to that shown in Figure 3.7, calculate the product of the hexadecimal unsigned 8-bit integers A and B using the hardware described in Figure 3.6. You should show the contents of each register on each step.
3.4.3 [60] <3.3> Write an MIPS assembly language program to calculate the product of unsigned integers A and B, using the approach described in Figure 3.4.
The following table shows pairs of octal numbers.
Get 3.4.3 exercise solution
3.4.4 [30] <3.3> When multiplying signed numbers, one way to get the correct answer is to convert the multiplier and multiplicand to positive numbers, save the original signs, and then adjust the final value accordingly. Using a table similar to that shown in Figure 3.7, calculate the product of A and B using the hardware described in Figure 3.4. You should show the contents of each register on each step, and include the step necessary to produce the correctly signed result. Assume A and B are stored in 6-bit sign-magnitude format.
3.4.5 [30] <3.3> When shifting a register one bit to the right, there are several ways to decide what the new entering bit should be. It can always be a zero, or always a one, or the incoming bit could be the one that is being pushed out of theright side (turning a shift into a rotate), or the value that is already in the leftmost bit can simply be retained (called an arithmetic shift right, because it preserves the sign of the number that is being shift). Using a table similar to that shown in Figure 3.7, calculate the product of the 6-bit two’s complement numbers A and B using the hardware described in Figure
3.6. The right shifts should be done using an arithmetic shift right. Note that the algorithm described in the text will need to be modified slightly to make this work—in particular, things must be done differently if the multiplier is negative. You can find details by searching the web. Show the contents of each register on each step.
3.4.6 [60] <3.3> Write an MIPS assembly language program to calculate the product of the signed integers A and B. State if you are using the approach given in 3.4.4 or 3.4.5.
Exercise 3.5
For many reasons, we would like to design multipliers that require less time. Many different approaches have been taken to accomplish this goal. In the following table, A represents the bit width of an integer, and B represents the number of time units (tu) taken to perform a step of an operation.
3.5.1 [10] <3.3> Calculate the time necessary to perform a multiply using the approach given in Figures 3.4 and 3.5 if an integer is A bits wide and each step of the operation takes B time units. Assume that in step 1a an addition is always performed—either the multiplicand will be added, or a zero will be. Also assume that the registers have already been initialized (you are just counting how long it takes to do the multiplication loop itself). If this is being done in hardware, the shifts of the multiplicand and multiplier can be done simultaneously. If this is being done in software, they will have to be done one after the other. Solve for each case.
3.5.2 [10] <3.3> Calculate the time necessary to perform a multiply using the approach described in the text (31 adders stacked vertically) if an integer is A bits wide and an adder takes B time units.
3.5.3 [20] <3.3> Calculate the time necessary to perform a multiply using the approach given in Figure 3.8 if an integer is A bits wide and an adder takes B time units.
Exercise 3.6
In this exercise we will look at a couple of other ways to improve the performance of multiplication, based primarily on doing more shifts and fewer arithmetic operations. The following table shows pairs of hexadecimal numbers.
3.6.1 [20] <3.3> As discussed in the text, one possible performance enhancement is to do a shift and add instead of an actual multiplication. Since 9 × 6, for example, can be written (2 × 2 × 2 + 1) × 6, we can calculate 9 × 6 by shifting 6 to the left 3 times and then adding 6 to that result. Show the best way to calculate A × B using shifts and adds/subtracts. Assume that A and B are 8-bit unsigned integers.
3.6.2 [20] <3.3> Show the best way to calculate A × B using shifts and add, if A and B are 8-bit signed integers stored in sign-magnitude format.
3.6.3 [60] <3.3> Write an MIPS assembly language program that performs a multiplication on signed integers using shifts and adds, using the approach described in 3.6.1.
The following table shows further pairs of hexadecimal numbers.
Get 3.6.3 exercise solution
3.6.4 [30] <3.3> Booth’s algorithm is another approach to reducing the number of arithmetic operations necessary to perform a multiplication. This algorithm has been around for years and involves identifying runs of ones and zeros and performing only shifts instead of shifts and adds during the runs. Find a description of the algorithm on the web and explain in detail how it works.
3.6.5 [30] <3.3> Show the step-by-step result of multiplying A and B, using Booth’s algorithm. Assume A and B are 8-bit two’s complement integers, stored in hexadecimal format.
3.6.6 [60] <3.3> Write an MIPS assembly language program to perform the multiplication of A and B using Booth’s algorithm.
Exercise 3.7
Let’s look in more detail at division. We will use the octal numbers in the following table.
3.7.1 [20] <3.4> Using a table similar to that shown in Figure 3.11, calculate A divided by B using the hardware described in Figure 3.9. You should show the contents of each register on each step. Assume A and B are unsigned 6-bit integers.
3.7.2 [30] <3.4> Using a table similar to that shown in Figure 3.11, calculate A divided by B using the hardware described in Figure 3.12. You should show the contents of each register on each step. Assume A and B are unsigned 6-bit integers. This algorithm requires a slightly different approach than that shown in Figure 3.10. You will want to think hard about this, do an experiment or two, or else go to the web to figure out how to make this work correctly. (Hint: one possible solution involves using the fact that Figure 3.12 implies the remainder register can be shifted either direction.)
3.7.3 [60] <3.4> Write an MIPS assembly language program to calculate A divided by B, using the approach described in Figure 3.9. Assume A and B are unsigned 6-bit integers.
The following table shows further pairs of octal numbers.
Get 3.7.3 exercise solution
3.7.4 [30] <3.4> Using a table similar to that shown in Figure 3.11, calculate A divided by B using the hardware described in Figure 3.9. You should show the contents of each register on each step. Assume A and B are 6-bit signed integers in sign-magnitude format. Be sure to include how you are calculating the signs of the quotient and remainder.
3.7.5 [30] <3.4> Using a table similar to that shown in Figure 3.11, calculate A divided by B using the hardware described in Figure 3.12. You should show the contents of each register on each step. Assume A and B are 6-bit signed integers in sign-magnitude format. Be sure to include how you are calculating the signs of the quotient and remainder.
3.7.6 [60] <3.4> Write an MIPS assembly language program to calculate A divided by B, using the approach described in Figure 3.12. Assume A and B are signed integers.
Exercise 3.8
Figure 3.10 describes a restoring division algorithm, because when subtracting the divisor from the remainder produces a negative result, the divisor is added back to the remainder (thus restoring the value). However, there are other algorithms that have been developed that eliminate the extra addition. Many references to these algorithms are easily found on the web. We will explore these algorithms using the pairs of octal numbers in the following table.
3.8.1 [30] <3.4> Using a table similar to that shown in Figure 3.11, calculate A divided by B using non-restoring division. You should show the contents of each register on each step. Assume A and B are 6-bit unsigned integers.
3.8.2 [60] <3.4> Write an MIPS assembly language program to calculate A divided by B using non-restoring division. Assume A and B are 6-bit signed (two’s complement) integers.
3.8.3 [60] <3.4> How does the performance of restoring and non-restoring division compare? Demonstrate by showing the number of steps necessary to calculate A divided by B using each method. Assume A and B are 6-bit signed (sign- magnitude) integers. Writing a program to perform the restoring and non- restoring divisions is acceptable.
The following table shows further pairs of octal numbers.
3.8.4 [30] <3.4> Using a table similar to that shown in Figure 3.11, calculate A divided by B using non-performing division. You should show the contents of each register on each step. Assume A and B are 6-bit unsigned integers.
3.8.5 [60] <3.4> Write an MIPS assembly language program to calculate A divided by B using nonperforming division. Assume A and B are 6-bit two’s complement signed integers.
3.8.6 [60] <3.4> How does the performance of non-restoring and nonperforming division compare? Demonstrate by showing the number of steps necessary to calculate A divided by B using each method. Assume A and B are signed 6-bit integers, stored in sign-magnitude format. Writing a program to perform the nonperforming and non-restoring divisions is acceptable.
Exercise 3.9
Division is so time-consuming and difficult that the CRAY T3E Fortran Optimization guide states, “The best strategy for division is to avoid it whenever possible.” This exercise looks at the following different strategies for performing divisions.
a. non-restoring division
b. division by reciprocal multiplication
3.9.1 [30] <3.4> Describe the algorithm in detail.
3.9.2 [60] <3.4> Use a flow chart (or a high-level code snippet) to describe how the algorithm works.
3.9.3 [60] <3.4> Write an MIPS assembly language program to perform division using the algorithm.
Exercise 3.10
In a Von Neumann architecture, groups of bits have no intrinsic meanings by themselves. What a bit pattern represents depends entirely on how it is used. The following table shows bit patterns expressed in hexademical notation.
a. 0x0C000000
b. 0xC4630000
3.10.1 [5] <3.5> What decimal number does the bit pattern represent if it is a two’s complement integer? An unsigned integer?
3.10.2 [10] <3.5> If this bit pattern is placed into the Instruction Register, what MIPS instruction will be executed?
3.10.3 [10] <3.5> What decimal number does the bit pattern represent if it is a floating point number? Use the IEEE 754 standard.
The following table shows decimal numbers.
a. 63.25 b. 146987.40625
3.10.4 [10] <3.5> Write down the binary representation of the decimal number, assuming the IEEE 754 single precision format.
3.10.6 [10] <3.5> Write down the binary representation of the decimal number assuming it was stored using the single precision IBM format (base 16, instead of base 2, with 7 bits of exponent).
Exercise 3.11
In the IEEE 754 floating point standard the exponent is stored in “bias” (also known as “Excess-N”) format. This approach was selected because we want an all-zero pattern to be as close to zero as possible. Because of the use of a hidden 1, if we were to represent the exponent in two’s complement format an all-zero pattern would actually be the number 1! (Remember, anything raised to the zeroth power is 1, so 1.00 = 1.) There are many other aspects of the IEEE 754 standard that exist in order to help hardware floating point units work more quickly. However, in many older machines floating point calculations were handled in software, and therefore other formats were used. The following table shows decimal numbers.
a. –1.5625 × 10–1
b. 9.356875 × 102
3.11.1 [20] <3.5> Write down the binary bit pattern assuming a format similar to that employed by the DEC PDP-8 (the leftmost 12 bits are the exponent stored as a two’s complement number, and the rightmost 24 bits are the mantissa stored as a two’s complement number ). No hidden 1 is used. Comment on how the range and accuracy of this 36-bit pattern compares to the single and double precision IEEE 754 standards.
3.11.2 [20] <3.5> NVIDIA has a “half” format, which is similar to IEEE 754 except that it is only 16 bits wide. The leftmost bit is still the sign bit, the exponent is 5 bits wide and stored in excess-56 format, and the mantissa is 10 bits long.
A hidden 1 is assumed. Write down the bit pattern assuming a modified version of this format, which uses an excess-16 format to store the exponent. Comment on how the range and accuracy of this 16-bit floating point format compares to the single precision IEEE 754 standard.
3.11.3 [20] <3.5> The Hewlett-Packard 2114, 2115, and 2116 used a format with the leftmost 16 bits being the mantissa stored in two’s complement format, followed by another 16-bit field which had the leftmost 8 bits as an extension of the mantissa (making the mantissa 24 bits long), and the rightmost 8 bits representing the exponent. However, in an interesting twist, the exponent was stored in sign-magnitude format with the sign bit on the far right! Write down the bit pattern assuming this format. No hidden 1 is used. Comment on how the range and accuracy of this 32-bit pattern compares to the single precision IEEE 754 standard.
The following table shows pairs of decimal numbers.
3.11.4 [20] <3.5> Calculate the sum of A and B by hand, assuming A and B are stored in the modified 16-bit NVIDIA format described in 3.11.2. Assume 1 guard, 1 round bit, and 1 sticky bit, and round to the nearest even. Show all the steps.
3.11.5 [60] <3.5> Write an MIPS assembly language program to calculate the sum of A and B, assuming they are stored in the modified 16-bit NVIDIA format described in 3.11.2. Assume 1 guard, 1 round bit, and 1 sticky bit, and round to the nearest even.
3.11.6 [60] <3.5> Write an MIPS assembly language program to calculate the sum of A and B, assuming they are stored using the format described in 3.11.1. Now modify the program to calculate the sum assuming the format described in 3.11.3. Which format is easier for a programmer to deal with? How do they each compare to the IEEE 754 format? (Do not worry about sticky bits for this question.)
Exercise 3.12
Floating point multiplication is even more complicated and challenging than floating point addition, and both pale in comparison to floating point division. The following table shows pairs of decimal numbers.
3.12.1 [30] <3.5> Calculate the product of A and B by hand, assuming A and B are stored in the modified 16-bit NVIDIA format described in 3.11.2. Assume 1 guard, 1 round bit, and 1 sticky bit, and round to the nearest even. Show all the steps; however, as is done in the example in the text, you can do the multiplication in human-readable format instead of using the techniques described in Exercises 3.4 through 3.6. Indicate if there is overflow or underflow. Write your answer as a 16-bit pattern, and also as a decimal number. How accurate is your result? How does it compare to the number you get if you do the multiplication on a calculator?
3.12.2 [60] <3.5> Write an MIPS assembly language program to calculate the product of A and B, assuming they are stored in IEEE 754 format. Indicate if there is overflow or underflow. (Remember, IEEE 754 assumes 1 guard, 1 round bit, and 1 sticky bit, and rounds to the nearest even.)
3.12.3 [60] <3.5> Write an MIPS assembly language program to calculate the product of A and B, assuming they are stored using the format described in 3.11.1. Now modify the program to calculate the sum assuming the format described in 3.11.3. Which format is easier for a programmer to deal with? How do they each compare to the IEEE 754 format? (Do not worry about sticky bits for this question.)
The following table shows further pairs of decimal numbers.
3.12.4 [30] <3.5> Calculate by hand A divided by B. Show all the steps necessary to achieve your answer. Assume there is a guard, a round bit, and a sticky bit, and use them if necessary. Write the final answer in both the 16-bit floating point format described in 3.11.2 and in decimal and compare the decimal result to that which you get if you use a calculator.
The Livermore Loops are a set of floating point–intensive kernels taken from scientific programs run at Lawrence Livermore Laboratory. The following table identifies individual kernels from the set.
a. Livermore Loop 3 b. Livermore Loop 9
3.12.5 [60] <3.5> Write the loop in MIPS assembly language.
3.12.6 [60] <3.5> Describe in detail one technique for performing floating point division in a digital computer. Be sure to include references to the sources you used.
Exercise 3.13
Operations performed on fixed-point integers behave the way one expects—the commutative, associative, and distributive laws all hold. This is not always the case when working with floating point numbers, however. Let’s first look at the associative law. The following table shows sets of decimal numbers.
3.13.1 [20] <3.2, 3.5, 3.6> Calculate (A + B) + C by hand, assuming A, B, and C are stored in the modified 16-bit NVIDIA format described in 3.11.2 (and also described in the text). Assume 1 guard, 1 round bit, and 1 sticky bit, and round to the nearest even. Show all the steps, and write your answer in both the 16-bit floating point format and in decimal.
3.13.2 [20] <3.2, 3.5, 3.6> Calculate A + (B + C) by hand, assuming A, B, and C are stored in the modified 16-bit NVIDIA format described in 3.11.2 (and also described in the text). Assume 1 guard, 1 round bit, and 1 sticky bit, and round to the nearest even. Show all the steps, and write your answer in both the 16-bit floating point format and in decimal.
3.13.3 [10] <3.2, 3.5, 3.6> Based on your answers to 3.13.1 and 3.13.2, does (A + B) + C = A + (B + C)?
The following table shows further sets of decimal numbers.
3.13.5 [30] <3.3, 3.5, 3.6> Calculate A × (B × C) by hand, assuming A, B, and C are stored in the modified 16-bit NVIDIA format described in 3.11.2 (and also described in the text). Assume 1 guard, 1 round bit, and 1 sticky bit, and round to the nearest even. Show all the steps, and write your answer in both the 16-bit floating point format and in decimal.
3.13.6 [10] <3.3, 3.5, 3.6> Based on your answers to 3.13.4 and 3.13.5, does (A × B) × C = A × (B × C)?
Exercise 3.14
The Associative law is not the only one that does not always hold in dealing with floating point numbers. There are other oddities that occur as well. The following table shows sets of decimal numbers.
3.14.1 [30] <3.2, 3.3, 3.5, 3.6> Calculate A × (B + C) by hand, assuming A, B, and C are stored in the modified 16-bit NVIDIA format described in 3.11.2 (and also described in the text). Assume 1 guard, 1 round bit, and 1 sticky bit, and round to the nearest even. Show all the steps, and write your answer in both the 16-bit floating point format and in decimal.
3.14.2 [30] <3.2, 3.3, 3.5, 3.6> Calculate (A × B) + (A × C) by hand, assuming A, B, and C are stored in the modified 16-bit NVIDIA format described in 3.11.2 (and also described in the text). Assume 1 guard, 1 round bit, and 1 sticky bit, and round to the nearest even. Show all the steps, and write your answer in both the 16-bit floating point format and in decimal.
3.14.3 [10] <3.2, 3.3, 3.5, 3.6> Based on your answers to 3.14.1. and 3.14.2, does (A × B) + (A × C) = A × (B + C)?
The following table shows pairs, each consisting of a fraction and an integer.
3.14.4 [10] <3.5> Using the IEEE 754 floating point format, write down the bit pattern that would represent A. Can you represent A exactly?
3.14.5 [10] <3.2, 3.3, 3.5, 3.6> What do you get if you add A to itself B times? What is A × B? Are they the same? What should they be?
3.14.6 [60] <3.2, 3.3, 3.4, 3.5, 3.6> What do you get if you take the square root of B and then multiply that value by itself? What should you get? Do for both single and double precision floating point numbers. (Write a program to do these calculations.)
Exercise 3.15
Binary numbers are used in the mantissa field, but they do not have to be. IBM used base 16 numbers, for example, in some of their floating point formats. There are other approaches that are possible as well, each with their own particular advantages and disadvantages. The following table shows fractions to be represented in various floating point formats.
a. 1/3
b. 1/10
3.15.1 [10] <3.5, 3.6> Write down the bit pattern in the mantissa assuming a floating point format that uses binary numbers in the mantissa (essentially what you have been doing in this chapter). Assume there are 24 bits, and you do not need to normalize. Is this representation exact?
3.15.2 [10] <3.5, 3.6> Write down the bit pattern in the mantissa assuming a floating point format that uses Binary Coded Decimal (base 10) numbers in the mantissa instead of base 2. Assume there are 24 bits, and you do not need to normalize. Is this representation exact?
3.15.3 [10] <3.5, 3.6> Write down the bit pattern assuming that we are using base 15 numbers in the mantissa instead of base 2. (Base 16 numbers use the symbols 0–9 and A–F. Base 15 numbers would use 0–9 and A–E.) Assume there are 24 bits, and you do not need to normalize. Is this representation exact?
3.15.4 [20] <3.5, 3.6> Write down the bit pattern assuming that we are using base 30 numbers in the mantissa instead of base 2. (Base 16 numbers use the symbols 0–9 and A–F. Base 30 numbers would use 0–9 and A–T.) Assume there are 20 bits, and you do not need to normalize. Is this representation exact? Do you see any advantage to using this approach?
