integer multiplication

[Old Wolf]

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?

No, (-INT_MIN) causes an integer overflow. You have to use
INT_MIN and negate the divisor (and get the inequality
direction right).

I would eschew the differentiation between INT_MIN and INT_MAX,
unless the code really did need to use INT_MIN as a valid value:

(x == 0) || (INT_MAX / ABS(x) > ABS(y))

Is there any way to implement ABS without evaluating the argument
twice? If not then I would make this an inline function.

Here's another way:
STATIC_ASSERT( sizeof(long long) >= 2 * sizeof(int) )

( 1LL * x * y <= INT_MAX && 1LL * x * y >= INT_MIN )

I wonder if any compiler would optimize:
if ( 1LL * ........ )
x *= y;
else
/* error handling */

to do a multiplication followed by an overflow check
(obv for CPUs which can overflow a multiplication and not trap).

 

[Nelu]

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?

If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 then
ABS(x) cannot be represented.

 

[Yevgen Muntyan]

No, (-INT_MIN) causes an integer overflow. You have to use
INT_MIN and negate the divisor (and get the inequality
direction right).

Good point. So it's even worse than what you said, since you
can't safely negate an operand here.

I would eschew the differentiation between INT_MIN and INT_MAX,
unless the code really did need to use INT_MIN as a valid value:

(x == 0) || (INT_MAX / ABS(x) > ABS(y))

Here you also ignore x*y == INT_MAX. I have no idea if one
ever needs this case, but I tried to make it correct, hence
the distinction between INT_MIN and INT_MAX.

Is there any way to implement ABS without evaluating the argument
twice? If not then I would make this an inline function.

This is not important, ABS may be a macro or a function,
I used it because (hopefully) everybody understands what it
means. Say, if I used some SIGN thing (which would be nicer
here, IMO), it'd immediately provoke a question about SIGN(0).

Here's another way:
STATIC_ASSERT( sizeof(long long) >= 2 * sizeof(int) )

( 1LL * x * y <= INT_MAX && 1LL * x * y >= INT_MIN )

Breaks on windows; and won't work if you want to detect overflow
in long long multiplication. I'd think a production macro/function
would likely use bit fiddling or something, i.e. be non-portable.
The point of my exercise was to make something portable and
correct. Another point was that it's not as simple as

if (INT_MAX / ABS(x) < ABS(y))
{
/* no overflow here */
}

I wonder if any compiler would optimize:
if ( 1LL * ........ )
x *= y;
else
/* error handling */

to do a multiplication followed by an overflow check
(obv for CPUs which can overflow a multiplication and not trap).

It would need to be a very smart compiler probably

Yevgen

 

[Yevgen Muntyan]

If x=INT_MIN and y=-1 with INT_MIN=-32768 and INT_MAX=32767 then
ABS(x) cannot be represented.

Yeah, as well as (-INT_MIN).

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

Yevgen

 

[Yevgen Muntyan]

Yeah, as well as (-INT_MIN).

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

This is broken too, for the same reasons. I can't get this thing though:
result of -a should be int if a is of type int. So how one can get
-a value if it overflows? In other words, how do you do

unsigned foo = -INT_MIN;

(or unsigned long long foo = -LLONG_MIN so we can't escape to bigger
type)?

Yevgen

 

[Nelu]

Yeah, as well as (-INT_MIN).

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

This is correct. Keith Thompson was right, as usual. It's not
trivial and it seems computationally expensive. Well, it seems
trivial once you know how to do it .

 

[Yevgen Muntyan]

unsigned abs (int x)
{
if (x >= 0)
return x;
else
return UINT_MAX - (unsigned)x;
}

int nooverflow (int x, int y)
{
unsigned ux = abs (x);
unsigned uy = abs (y);
return x == 0 ||
((x > 0 && y >= 0 || x < 0 && y <= 0) &&
(unsigned) INT_MAX / ux >= uy) ||
((x > 0 && y < 0 || x < 0 && y > 0) &&
abs(INT_MIN) / ux >= uy);
}

Can we assume INT_MAX and magnitude of INT_MIN are not greater than
UINT_MAX?

Yevgen

 

[Yevgen Muntyan]

This is correct.

Unfortunately no, division overflows

Yevgen

 

[Nelu]

Unfortunately no, division overflows

Oooops. My mistake. And this was the exact problem I was trying
to solve a few minutes ago ).

 

[user923005]

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

<OT>
Assuming Mingw, here are some unofficial 4.x builds (I use them and
they seem fine):
http://www.thisiscool.com/gcc_mingw.htm

 

[user923005]

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

<OT>
Assuming Mingw, here are some unofficial 4.x builds (I use them and
they seem fine):
http://www.thisiscool.com/gcc_mingw.htm

 

[CBFalconer]

<OT>
Assuming Mingw, here are some unofficial 4.x builds (I use them and
they seem fine):
http://www.thisiscool.com/gcc_mingw.htm
</OT>

I was referring to the effectiveness of -ftrapv.