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

9/14/2005

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

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 comand 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.

To get checked off: have your program working (printing out the correct answer) and be able to time it using the time command. You program must actually do all 256*256 possible additions and check the result of each. You can't simply skip the additions you know are correct/incorrect.

References

• Lecture notes covering C Logic operators and addition overflow