math overflow error

tda · 04-03-2003, 05:28 AM

Hello ALL

I've a question. How to do detection of mathematical overflow error in C programs. Suppose a program has follofind code:

int a = 345335;
int b = 34543;
int c = a * b;

How to detect in independet platform/os/compiler form that result c is correct and not overfloved? Are there any standart methods in ANSI C?

Thenks for any propositions.

GtkUser · 04-03-2003, 07:07 AM

There is no overflow in unsigned arithmetic. If one operand is unsigned and the other is signed, than the signed is converted into unsigned. Overflow can occur if both operands are signed.

Code:

if ( (unsigned) a + (unsigned) b > INT_MAX )
  complain();

INT_MAX is defined in <limits.h>

see book: C Traps and Pitfalls

GtkUser · 04-03-2003, 07:12 AM

Also this:

Code:

if ( a > INT_MAX - b )
 complain();

Which doesn't involve using unsigned casts.

GtkUser · 04-03-2003, 07:30 AM

Well, at least that's what the book said.

tda · 04-03-2003, 07:40 AM

Quote:

Originally posted by GtkUser
[B]There is no overflow in unsigned arithmetic.[B]

Hmmm...
Suppose type int has 16 bit capacity. Therefore maximal unsigned int is 2^16 - 1 = 65535. Suppose have two vars:

unsigned int a = 60000;
unsigned int b = 40000;

and want to add a to b:

unsigned int c = a + b;

Correct result in this case is 100000 but var c due to 16 bit capacity will contain incorrect val 44465.

How to detect this situation???
In simplest cases when used only '+' and '-' operations I can try detect overflow with help of INT_MIN/MAX. But what about other mathematical operations '/', '*', '%' etc?

P.S. Thenks for reference to book. I try to find it.

GtkUser · 04-03-2003, 07:54 AM

What are the results of this program on your system?

Code:

#include<stdio.h>
#include<limits.h>
 
int main() {
 
  printf("%d\n", INT_MAX);
  return 0;
 
}

tda · 04-03-2003, 08:10 AM

Quote:

Originally posted by GtkUser
What are the results of this program on your system?

Code:

#include<stdio.h> #include<limits.h> int main() { printf("%d\n", INT_MAX); return 0; }

OK

I use x386 linux box and INT_MAX in limits.h defined as 2147483647.

GtkUser · 04-03-2003, 08:14 AM

My computer gives me: 2147483647
So that is the max.

Now I run this program:

Code:

#include<stdio.h>
#include<limits.h>
 
int main() {
 
  int i;
  int x = 2;
  int sum = 1;
 
  for ( i = 0; i < 32; ++i )
    {
      sum *= x;
      printf("%d\n", sum);
    }
  return 0;
 
}

And The output is:
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
-2147483648
0

So there is some overflow! The last couple of multiples of 2.

Now I revise the program by adding the overflow check:

Code:

#include<stdio.h>
#include<limits.h>
 
int main() {
 
  int i;
  int x = 2;
  int sum = 1;
 
  for ( i = 0; i < 32; ++i )
    {
      if (! ( (unsigned) sum * (unsigned) x > INT_MAX) )
        sum *= x;
      printf("%d\n", sum);
    }
  return 0;
 
}

And this output is:
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
1073741824
1073741824

So in other words, there was no buffer overflow.

tda · 04-03-2003, 08:36 AM

Quote:

Originally posted by GtkUser
My computer gives me: 2147483647
So that is the max.

Now I run this program:

Code:

#include<stdio.h> #include<limits.h> int main() { int i; int x = 2; int sum = 1; for ( i = 0; i < 32; ++i ) { sum *= x; printf("%d\n", sum); } return 0; }

And The output is:
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
-2147483648
0

So there is some overflow! The last couple of multiples of 2.

Now I revise the program by adding the overflow check:

Code:

#include<stdio.h> #include<limits.h> int main() { int i; int x = 2; int sum = 1; for ( i = 0; i < 32; ++i ) { if (! ( (unsigned) sum * (unsigned) x > INT_MAX) ) sum *= x; printf("%d\n", sum); } return 0; }

And this output is:
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
1073741824
1073741824

So in other words, there was no buffer overflow.

This is work

Many thanks. But is this approach correct???
I can guess that expression (unsigned) sum * (unsigned) x is calculated in FPU with 64/80 bit precise. But I think that on more weak hard (suppose 8088) this code will return incorrect result.
Moreover on your PC it can produce error result if result of expression will be more than 2^80.

GtkUser · 04-03-2003, 09:01 AM

It is supposed to be correct, for all implementations that define an INT_MAX in <limits.h>

The book says that all unsigned operations are done modulo 2^n, where n is the number of bits in the result. It says that there is no such thing as overflow in unsigned arithmetic.

If you can, test is out on other architectures before deploying. I don't know the mathematical details. I am just going by the book, and I only figured out this example to demonstrate it.

GtkUser · 04-03-2003, 09:02 AM

The book says that this is the WRONG approach:

Code:

if (a + b < 0 )
  complain();

GtkUser · 04-03-2003, 10:29 AM

If you want definitive answers than go here: < http://groups.google.com/groups?group=comp.lang.c >.

wapcaplet · 04-03-2003, 10:43 AM

One method I've used to check in advance whether overflow will occur is:

Code:

int x;
int y;

// other stuff, assigns some values to x and y

if ( x < INT_MAX - y )
  z = x + y;
else
  complain();

or:

Code:

// ...
if ( x < INT_MAX / y )
  z = x * y;
else
  complain();

Granted, in a way this involves doing the computation twice, but this will at least make sure x+y (or x*y in the second example) is less than INT_MAX before doing the calculation. (Hope this makes sense... if you know your algebra, it will

)