Lab #3 - Overflow, C Programming and the time command.

2/9/2005

This lab involves creating and running C programs that determine the number of 8-bit signed addition and multiplication operations that result in incorrect results (the result won't fit in an 8 bit signed char).

8-bit Signed Additions

You need to write a program that will try all possible (signed) 8-bit additions, for each you need to check whether the result is correct or not. Your program should print out the number of incorrect additions found.

Consider the C expression (x,y and z are all signed char): z = x + y;. You need to create loops so that this statement is executed for all possible values of x and y. For each addition operation you should check to determine whether overflow has occurred. Recall that overflow has occurred (after an addition operation) whenever the sign of both operands is the same but the sign of the result is different.

Note: You should do all possible values for x and y, that is, you should do both 1 + 2 and 2 + 1 , so the total number of addition operations you check must be 256 * 256 = 65536.

Once your program is working correctly (printing out the right answer), you should establish how long it takes your program to determine the right answer. Use the Unix time command to run your program (the following example assumes that your program is named lab2):

> time ./lab2
Total wrong is 16384
 
real    0m0.024s
user    0m0.020s
sys     0m0.000s
>

The user time reflects the CPU time spent processing your code, the real time is the total elapsed time and will change depending on the load on the machine you are using. user time is the time of interest to us in this lab.

When using the time command, you need to keep in mind that you can't trust very small reported times (the timing is not that accurate). You should alter your program so that it repeats the total computation enough times to force the total user time to be at least 1 second. To determine the actual run time of your code divide your user time by the number of times you run the computations.

You may find the following code useful - this code will call a function named compute() however many times are specified on the command line.

#include <stdio.h>

/* compute determines the number of 8-bit additions that
   result in overflow
*/
int compute() {
  /* you need to write this */
}


/* main program that calls compute however many times are 
   specified on the command line
*/

int main(int argc,char **argv) {
  int i,n,result;

  if (argc<2) {
	printf("You need to supply a count\n");
  } else {
	/* convert command line arg to an integer */
	n = atoi(argv[1]);

	/* call compute n times */

	for (i=0;i<n;i++)
	  result=compute();

        /* print out the value returned by compute */
        printf("Total wrong is %d\n",result);
  }
  return(1);
}

Win a prize!

Best times will win a prize - the idea is that you need to play with how you determine whether or not overflow has occurred (this is the "expensive" code in the computation). Minimize the number of logic operations you do and you will minimize the time it takes.

Time to beat (on monte) for 10,000 iterations:
5.7 seconds (user time)

---

8-bit Signed Multiplication

Repeat the above execise, but this time use 8-bit signed chars and do multiplication. You need to develop your own rules for determining whether or not computer arithmetic produces the correct answer or not (simply looking at the sign bits is not applicable here).

---

Finishing

To get checked off: have your programs working (printing out the correct answer) and be able to time it using the time command. Your programs must actually do all 256*256 possible additions/multiplications and check the result of each! No shortcuts allowed!

---

Implementation Issues

There are some tricky implementation issues involved here! Using signed char variables, how do you create a loop that iterates over all possible legal values? This won't work:

  char x;

  for (x=-128;x<=127;x++) 

The comparison x<=127 is always true! There is no possible value for x that will make this comparison be false, since there are no 8-bit signed ints whose value is greater than 127. The compiler will actually tell you this (pay attention to what the compiler tells you!)

For multiplication you need to figure out how to determine whether z=x*y produces the correct answer, but using the rules we developed for detecting overflow of 8-bit addition is not usefule here. You need to figure out what conditions indicate that z z is not correct, and find a way to implement your ideas. You may use int arithmetic (with 32 bit signed ints) to verify the answer, there are other ways as well...

References

• Lecture notes covering C Logic operators and addition overflow