integer multiplication

[Pesso]

What happens if you multiple two integers and the result overflows the
MAX_INT in C? Is there a way to trap the condition when it happens?

 

[santosh]

What happens if you multiple two integers and the result overflows the
MAX_INT in C?

Behaviour when signed integers overflow is implementation dependant.
Unsigned integers do not overflow, but exhibit "wrap-around" behaviour
according to modulo 2^n arithmetic.

Is there a way to trap the condition when it happens?

You'll have to see your implementation's documentation for this. The
Standard doesn't insist on a trap. Note though, that you can easily
check if a particular operation will cause overflow or wrap-around
before attempting it. It's tedious, but it can be done.

 

[santosh]

Behaviour when signed integers overflow is implementation dependant.

[ ... ]

Sorry, it's actually undefined behaviour, according to the Standard.

<snip>

 

[Richard Heathfield]

Pesso said:

What happens if you multiple two integers and the result overflows the
MAX_INT in C?

Assuming you mean ints and INT_MAX, the behaviour is undefined.

Is there a way to trap the condition when it happens?

Not portably, no. The proper technique is not to let it happen in the
first place. It's easy enough to avoid.

 

[Keith Thompson]

Pesso said:

Assuming you mean ints and INT_MAX, the behaviour is undefined.


Not portably, no. The proper technique is not to let it happen in the
first place. It's easy enough to avoid.

I wouldn't call it easy in general, unless you know some trick that
I'm not familiar with.

For example, it's certainly possible to implement a function like
this:

int safe_multiply(int x, int y, int *overflow)
{
if (/* multiplication would overflow */) {
*overflow = 1;
return INT_MAX; /* or whatever */
}
else {
*overflow = 0;
return x * y;
}
}

but the condition is non-trivial, it's likely to be more
computationally expensive than the multiplication itself, and using
this function in place of the "*" operator makes your code more
difficult to write and to read, especially if you're doing a lot of
multiplications.

You can *sometimes* write your code in a way that just avoids
multiplications that would overflow, but that's very
application-specific and not always feasible.

Many CPUs set a condition code on overflow, but C doesn't provide a
way to get at it.

 

[Malcolm McLean]

I wouldn't call it easy in general, unless you know some trick that
I'm not familiar with.

For example, it's certainly possible to implement a function like
this:

int safe_multiply(int x, int y, int *overflow)
{
if (/* multiplication would overflow */) {
*overflow = 1;
return INT_MAX; /* or whatever */
}
else {
*overflow = 0;
return x * y;
}
}

but the condition is non-trivial, it's likely to be more
computationally expensive than the multiplication itself, and using
this function in place of the "*" operator makes your code more
difficult to write and to read, especially if you're doing a lot of
multiplications.

The obvious strategy of

if(x * y < INT_MAX)

has a fatal flaw as far as C is concerned.
However you can cast to double
if ((double) x * y < INT_MAX)

that begs the question of why not use doubles for everything and solve the
problem that way.

You can *sometimes* write your code in a way that just avoids
multiplications that would overflow, but that's very
application-specific and not always feasible.

Many CPUs set a condition code on overflow, but C doesn't provide a
way to get at it.

The OPs question seemed to be whether it was possible to intecerpt the error
handler, for instance to print out a "hey man, these images are way too big.
On strike chum." message rather than just crash with a crytic compaint about
mathematical exceptions.
It is perfectly reasonable thing to ask, but in fact you can't, certainly
not in ANSI C. Even if you know your platform it is a difficult fiddly thing
to do - in DOS you used to be able to chain on to the interrupt handlers,
but those salad days are long gone.

Of course if ints are 64 bits then 99% of the time you can sanity check very
easily.

 

[Nelu]

The obvious strategy of

if(x * y < INT_MAX)

has a fatal flaw as far as C is concerned.
However you can cast to double
if ((double) x * y < INT_MAX)

that begs the question of why not use doubles for everything and solve
the problem that way.

I think that it's better to use integer types rather than doubles
if you care about precission.
You can use x<INT_MAX/y to find out if unsigned int values will
wrap around. For signed integeres you can have overflow both on
the negative and the positive sides. You will need to take into
consideration the sign of the operands and the resulting sign as
well to check for all possible cases. I think that taking care of
overflow is expensive.

The OPs question seemed to be whether it was possible to intecerpt the
error handler, for instance to print out a "hey man, these images are
way too big.

For image sizes you'd use unsigned integers which is easier and
faster to handle.

On strike chum." message rather than just crash with a
crytic compaint about mathematical exceptions.
It is perfectly reasonable thing to ask, but in fact you can't,
certainly not in ANSI C. Even if you know your platform it is a
difficult fiddly thing to do - in DOS you used to be able to chain on to
the interrupt handlers, but those salad days are long gone.

Of course if ints are 64 bits then 99% of the time you can sanity check
very easily.

What do you mean?

 

[CBFalconer]

.... snip ...

The obvious strategy of

if(x * y < INT_MAX)

has a fatal flaw as far as C is concerned.
However you can cast to double
if ((double) x * y < INT_MAX)

Just use:

if ((INT_MAX / x) < y) ans = x * y;
else overflow(__LINE__, __FILE__);

It is unfortunate that compilers don't normally implement a trap on
integer overflow, so without taking care you can get nonsense
results.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Ben Pfaff]

It is unfortunate that compilers don't normally implement a trap on
integer overflow, so without taking care you can get nonsense
results.

<off-topic>
With recent GCC versions you can use -ftrapv to get a trap on
integer overflow.
</off-topic>

 

[Yevgen Muntyan]

Just use:

if ((INT_MAX / x) < y) ans = x * y;
else overflow(__LINE__, __FILE__);

Won't work when x*y == INT_MAX (2^63-1 isn't prime, so it won't
work for long int on many popular implementations, not just on DS09876).

Yevgen

 

[Yevgen Muntyan]

Won't work when x*y == INT_MAX (2^63-1 isn't prime, so it won't
work for long int on many popular implementations, not just on DS09876).

For pedants: "won't work" is clearly false; it will work but will
falsely claim overflow for some pairs x,y if INT_MAX isn't a prime
integer.
Furthermore, if x and y are negative, then inequality should be
reversed, i.e. it should be something like

INT_MAX / ABS(x) < ABS(y) ||
(INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0)

to detect whether x*y <= INT_MAX in normal arithmetic (INT_MIN
would require one more thing like this). I wonder what I missed here.

Yevgen

 

[CBFalconer]

<off-topic>
With recent GCC versions you can use -ftrapv to get a trap on
integer overflow.
</off-topic>

I'm still using 3.2.1, but I might install 4.1 shortly. I thought
that didn't work for x86 code.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Yevgen Muntyan]

For pedants: "won't work" is clearly false; it will work but will
falsely claim overflow for some pairs x,y if INT_MAX isn't a prime
integer.

And of course 1 * INT_MAX == INT_MAX.

Yevgen

 

[CBFalconer]

For pedants: "won't work" is clearly false; it will work but will
falsely claim overflow for some pairs x,y if INT_MAX isn't a prime
integer.

Furthermore, if x and y are negative, then inequality should be
reversed, i.e. it should be something like

There are actually three cases to worry about. 0, 1, or 2 operands
negative. 0 is already handled, 1 requires use of INT_MIN, and 2
requires comparison reversal. All barring the equality condition
you brought up above.

 

[Yevgen Muntyan]

For pedants: "won't work" is clearly false;

It's actually clearly true. The inequality should be reversed.
Full version, to check both top and bottom:

x == 0 ||
((x > 0 && y >= 0 || x < 0 && y <= 0) &&
(INT_MAX / ABS(x) > ABS(y) ||
(INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) ||
((x > 0 && y < 0 || x < 0 && y > 0) &&
((-INT_MIN) / ABS(x) > ABS(y) ||
((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));

I wonder if there is simple portable one-expression form of it.

Yevgen

 

[Yevgen Muntyan]

There are actually three cases to worry about. 0, 1, or 2 operands
negative. 0 is already handled, 1 requires use of INT_MIN, and 2
requires comparison reversal. All barring the equality condition
you brought up above.

Well, I talked about checking whether x*y > INT_MAX (snipped text:
"to detect whether x*y <= INT_MAX in normal arithmetic"). Case of 1
negative operand is not interesting: product is always less than
INT_MAX. But there is fourth case: x == 0

Yevgen

 

[Malcolm McLean]

What do you mean?

Numbers represent something.
Let's say we want to multiply the number of employees by the number of
products we sell.
Both of these numbers are probably in the low thousands if not low hundreds.
However a big company might have more than 64,000 employees and a few
companies, like retailers, might offer more than 64,000 products. On the
other hand a supermarket, with lots of employees and lots of products,
probably wouldn't want to do the calculation if, for instance, we want to
create a matrix of each employee's contribution to each product. It simply
doesn't make sense in supermarket business model terms. So we know that 32
bits for the result is safe.

So we cannot quite sanity test by saying that if(employees > 64000 ||
products > 64000) bail();

However no company is going to have 4 billion employees, or offer 4 billion
different products. So we can easily sanity test, and know that the result
will never overflow 64 bits.

 

[santosh]

Numbers represent something.

However no company is going to have 4 billion employees, or offer 4 billion
different products. So we can easily sanity test, and know that the result
will never overflow 64 bits.

Yes, that's the real issue. If you've chosen the appropriate data type
beforehand, for a particular calculation, then overflow shouldn't
occur except as a result of a bug or bad input. The former can be
corrected by compile-time checking and debugging while the latter can
be avoided by validating all input before using them.

 

[Old Wolf]

x == 0 ||
((x > 0 && y >= 0 || x < 0 && y <= 0) &&
(INT_MAX / ABS(x) > ABS(y) ||
(INT_MAX / ABS(x) == ABS(y) && INT_MAX % ABS(x) == 0))) ||
((x > 0 && y < 0 || x < 0 && y > 0) &&
((-INT_MIN) / ABS(x) > ABS(y) ||
((-INT_MIN) / ABS(x) == ABS(y) && (-INT_MIN) % ABS(x) == 0)));

I wonder if there is simple portable one-expression form of it.

What is the purpose of the (INT_MAX % ABS(x) == 0) expression?
If INT_MAX / x == y (with x > 0) then x*y will be less than or
equal to INT_MAX so there is no overflow.

 

[Yevgen Muntyan]

What is the purpose of the (INT_MAX % ABS(x) == 0) expression?
If INT_MAX / x == y (with x > 0) then x*y will be less than or
equal to INT_MAX so there is no overflow.

No purpose, I was fooled by the initial wrong 'INT_MAX / x < y'
condition. So, it's gonna be

x == 0 ||
((x > 0 && y >= 0 || x < 0 && y <= 0) && INT_MAX / ABS(x) >= ABS(y)) ||
((x < 0 && y >= 0 || x > 0 && y <= 0) && (-INT_MIN) / ABS(x) >= ABS(y))

Is this one right?

Yevgen