The Tao of Computing:
A Down-to-Earth Approach to Computer Fluency
 
by Henry M. Walker Jones and Bartlett Publishers
 

Laboratory Exercise on Integer Processing

Goals:

This laboratory exercise provides practice with

Preliminaries

This lab utilizes two programs for processing integer values:

Your instructor will tell you how to access these programs on your system.

Reading

You should read Chapter 2 of Walker, Henry M., The Tao of Computing: A Down-to-earth Approach to Computer Fluency, Jones and Bartlett, 2005, before working on this laboratory exercise.

Integers and Their Representation

Your reading described how positive integers are stored within a computer. This part of the lab asks you to apply your understanding from this reading to both positive and negative integers, as observed on a computer.

The Fixed-Size-Storage Approach for Integers

The first several experiments in this lab utilize a program integer-rep. This program is written in the C programming language. In this language (and in most others), integers are stored using the fixed-size-storage approach discussed in the text.

  1. In a terminal/command window, run the program integer-rep.

This program keeps track of two integers −&minus one represented in 16 bits and one represented with 32 bits. At the start, each of these integers has the value 1, and integer-rep prints each out in both decimal and binary notation. The program then allows you to perform various operations on these numbers. After each operation, integer-rep prints the new values of these numbers.

  1. When running integer-rep, use the operation "A" to add 1 to the values. Then use "A" again, and again. (When starting with the value 1, the integers will become 2, 3, and 4.)

    Review the binary representation of each integer, and explain why it has the binary representation printed.

  2. Use the "M" option 3 times, each time multiplying the values by 2. The integers will become 8, 16, and 32. Explain why the binary representation of each integer looks as it does.

  3. Use the "I" option to set the values to 5. Explain the binary representation that results.

  4. Use the "I" option to set the values to 32. Then use the "M" option several times to multiply by 2 to obtain the values 64, 128, 256, 512, 1024, 2048, 4096, 8192, and 16384. Explain how the pattern of 0's and 1's obtained changes as you go from one of these numbers to the next.

Now that we have some experience with non-negative integers, we look at a few negative numbers. Details of the storage of these values is beyond the scope of this course. However, you can make some observations.

  1. Use the "I" option to set the program's values to -1, and describe the binary representation that you see.

  2. Use the "M" option to multiply the program's values by 2 several times to obtain the values -2, -4, -8, -16, ..., -8192, -16384, -32768. Can you describe a pattern in the 0's and 1's obtained for these numbers?

  3. Use the "I" option to enter several more negative integers and several more positive integers. Use your observations to form a hypothesis about the meaning of the initial (leading) bit in the fixed-size-storage approach for integers.

  4. Use the "I" option to enter -32768 again. Then use the "S" option to subtract 1 from -32768. What result do you get with the 16-bit integer form and with the 32-bit integer? Try to explain why you get each result.

  5. Use the "A" option to add 1 to your result of step 9. What can you conclude about the maximum integer that can be stored in 16 bits (assuming the processing is allowed to handle both negative and positive numbers)?

  6. Use a similar approach to find the maximum integer that can be stored in a 32-bit (signed) integer. Explain your result and how you got it.

  7. What happens if you try to use the "I" option to set integer values higher than this maximum for 32-bit (signed) integers? Describe what happens in at least a few test cases.

  8. Read the news account of the computer-related difficulties that grounded all of Comair's flights on December 25, 2004. The article states, the computer system for Comair "has a hard limit of 32,000 changes in a single month." Other articles related this problem to a field in a database that was designed as a 16-bit integer.

    1. What do you think was the real (not rounded) limit for changes to crews at Comair?

    2. Hypothesize what troubles might have occurred in the software when that limit was reached.

    3. From what you know about the fixed-storage-approach for storing integers, identify one or two ways this problem could have been avoided.

Variable-Size-Storage Approach

While the integer-rep illustrates how integers usually are stored in computers, a few environments utilize the variable-size-storage approach. The Scheme programming language and environment illustrates this alternative approach. With variable-size-storage, the binary representation does not have a 16-bit or 32-bit form; rather, the binary representation uses as many bits as needed.

  1. Run the Scheme version of integer-rep.
    This program has much the same interface as the C version you used above.
    Check that the operations for entering integers, addition, subtraction, multiplication, and division work as they did with the C version:

    1. Use the "I" option to set the internal integer to 5.
    2. Use the "A" and "S" options to add and subtract 1, respectively.
    3. Use the "M" and "D" options to multiply and divide by 2, respectively.
  2. Use the "I" option to enter very large positive or negative numbers (e.g., over 20 digits). For example, try the values that you used in step 12, and then try even larger numbers. Explain what happens.

  3. With your large integers from step 15, use the "A", "S", "M", and "D" options to determine if simple arithmetic still works for these large values, and describe your results.

Summary

  1. Review your experiments with both the fixed-size-approach and the variable-size-approach for storing integers, and write a paragraph summarizing the observations you have made.

Work To Be Turned In




This laboratory exercise coordinates with Chapter 2 of Walker, Henry M., The Tao of Computing: A Down-to-earth Approach to Computer Fluency, Jones and Bartlett, 2005.



This document is available on the World Wide Web as
http://www.cs.grinnell.edu/~walker/fluency-book/labs/integer-proc.shtml

created January 14, 2005
last revised October 8, 2008

Valid HTML 4.01! Valid CSS!