Integer Processing

Goals:

This laboratory exercise provides practice with

• experimenting with the representation of integers, using both fixed-size storage and variable-size storage,
• comparing capabilities of 16-bit signed integers and 32-bit signed integers, and
• determining what happens when the maximum size of integers is obtained.

Preliminaries

This lab utilizes a program and a script for processing integer values:

• integer-rep.c is written in the C programming language and utilizes fixed-size-storage (both short and long integers).
• integer-rep.scm is a script that utilizes the Scheme programming language and variable-size-storage.

Positive 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 positive integers, as observed on a computer.

The Fixed-Size-Storage Approach for Positive Integers

1. Copy integer-rep.c to your account and compile it. Run integer-rep, which initially shows the binary representation of the number 1. Use the operation "A" to add 1 to the values. Then use "A" again, and again, and again. (When starting with the value 1, the integers will become 2, 3, 4, and 5.)

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

2. Use the "I" option to set the value to 12. Then use the "M" option 5 times, each time multiplying the values by 2 to obtain 24, 48, 96, 192, and 384. Explain why the binary representation of each integer looks as it does, including how the pattern of 0's and 1's obtained changes as you go from one of these numbers to the next.
3. Try to use the "I" option to set the integer to a 5-digit positive integer (e.g., 10000), a 10-digit positive integer (e.g., 2000000000), a 15-digit positive integer, and a 20-digit positive integer. Explain what happens in each case.

The Variable-Size-Storage Approach for Positive Integers

While integer-rep.c 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. Our experiments will use the program integer-rep.scm

4. Copy integer-rep.scm to your account. Run integer-rep.scm in a Scheme interpreter by typing the following line into a terminal window:

   scheme -q integer-rep.scm

   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:

5. Following the same approach as Step 1, determine the binary representations for the positive integers 1, 2, 3, 4, and 5. To what extent are these the same or different from the fixed-size-storage approach?
6. Repeat Step 3 with this Scheme-based script.

Negative Integers and Their Representations

Now that we have some experience with non-negative integers, we look at a few negative numbers.

The Fixed-Size-Storage Approach for Negative Integers

7. As in Steps 1-3, use the C program integer-rep.c and the "I" option to set the program's values to -1, -2, -3, and -5. Review the 0's and 1's to determine whether the computer uses sign-magnitude notation, ones complement notation, or twos complement notation. Write a paragraph to justify your conclusion.
8. Use the "I" option to enter -32766. Then use the "S" option four times to subtract 1 from -32766 . What results do you get with the 16-bit integer form and with the 32-bit integer? Explain why you get each result.
9. Use the "A" option several times to add 1 to your result of step 8. 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)?
10. 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.
11. 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 confirmed that this problem was due 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. From what you know about the fixed-storage-approach for storing integers, identify one or two ways this problem could have been avoided.
3. More recently, in December 2014 a similar issue with less social significance but (arguably) more cultural impact arose due to a certain popular YouTube video.

The Variable-Size-Storage Approach for Negative Integers

12. Using integer-rep.scm as before, enter very large negative numbers (e.g., over 20 digits). Explain what happens.

Summary

13. Review your experiments with both the fixed-size-approach and the variable-size-approach for storing integers, and summarize the observations you have made.