Performance of signed vs unsigned types

[madamemandm]

On Apr 26, 7:59 pm, (e-mail address removed) (Gordon Burditt) wrote:
[snip]

The code I'm including here is for signed multiplication only.
Someone might find it useful.  Ok, try to break it.

Sure thing.

 I'm not sure
I have properly accounted for all the possible wierdities on a
non-2's-complement machine, and I don't have one to test on.

The main source file is pretty simple, for making the code type-generic:
______________________________________________________
#include <limits.h>

#define VALUE_T                 signed long
#define VALUE_MIN               LONG_MIN
#define VALUE_MAX               LONG_MAX

#define mul_will_overflow       sl_mul_will_overflow

#include "smul.inc"
______________________________________________________

and it included the appropriate code, here for signed multiply:

______________________________________________________
#include "libovflo.h" /* contains function prototypes for the library */

int
mul_will_overflow(VALUE_T a, VALUE_T b, VALUE_T * c)
{
    if (a == 0 || a == 1 || b == 0 || b == 1)
    {
        /* cannot overflow */
    }
    else
    {
        if (VALUE_MAX - 1 < -1 - VALUE_MIN)
        {
            /* -VALUE_MIN overflows */
            if (a == VALUE_MIN || b == VALUE_MIN)
            {
                /* -1 * VALUE_MIN overflows */
                /* 0 * VALUE_MIN and 1 * VALUE_MIN handled above */
                /* anything else overflows */
                return 1;
            }
        }
        if (a > 0)
        {
            if (b > 0)
            {
                /* a, b positive */
                if (VALUE_MAX / b < a)
                {
                    return 1;
                }
            }
            else
            {
                /* a positive, b negative */
                if ((((-b) - VALUE_MIN) / (-b)) - 1 < a)
                {
                    return 1;
                }
            }
        }
        else
        {
            if (b > 0)
            {
                /* a negative, b positive */
                if (((b - VALUE_MIN) / b) - 1 < (-a))
                {
                    return 1;
                }
            }
            else
            {
                /* a, b negative */
                if (VALUE_MAX / (-b) < (-a))
                {
                    return 1;
                }
            }
        }
    }
    if (c)
    {
        *c = a * b;
    }

    return 0;}

The mixed sign tests look wrong to me. In both of them you are
subtracting VALUE_MIN from a postitive number. This is gaurenteed to
produce a value greater than VALUE_MAX and is therefore undefined.
E.g. let a = 15, b = -2, VALUE_MIN = -2147483648, VALUE_MAX =
2147483647 then the test selected is

(((-b) - VALUE_MIN) / (-b)) - 1 < a

Substituting the values gets.

(((-(-2)) - (-2147483648)) / (-(-2))) - 1 < 15

Simplifying a bit.

((2 - (-2147483648)) / 2) < 15
(2147483650 / 2) < 15

And 2147483650 > 2147483647.


Even if it was correct, it would still be illustrative of the value of
adding the ability to check for overflow to the core language.
Overflow on multiplication can be detected in just a few assembly
instruction on quite a few processors. I'd be impressed if a compiler
managed to convert that source into those instructions.

Martin Shobe

 

[Malcolm McLean]

How about

if(fabs((double)x * double(y)) > INT_MAX)
return 1;

It's a one-liner. You need a two liner to handle the special case of
INT_MIN, which probably isn't worth it.

 

[Ben Bacarisse]

if(fabs((double)x * double(y)) > INT_MAX)
return 1;

Typo: double(y) should be (double)y

It's a one-liner. You need a two liner to handle the special case of
INT_MIN, which probably isn't worth it.

Unless the campaign for 64-bit ints also demands more bits for double
this is likely to run into trouble.

 

[James Kuyper]

How about

if(fabs((double)x * double(y)) > INT_MAX)
return 1;

It's a one-liner. You need a two liner to handle the special case of
INT_MIN, which probably isn't worth it.

That is a conceptually simple solution, which is a real advantage.

However, it assumes that DBL_MAX > INT_MAX, which is an extremely
plausible assumption, but technically not guaranteed. It's more
plausible for larger integer types, especially intmax_t.

With 64-bit integers, there's another potential problem that's much more
likely to occur: most 64-bit integer values cannot be converted to a
64-bit double type without change of value. As a result, the calculated
product might not be correct. In many cases where the product is
sufficiently close to INT64_MAX, the calculated product will be larger
than the limit, even though the mathematical product is not (and
vice-versa).

Finally, I'd expect the conversions to double, the double precision
multiplication, and the fabs() call to collectively take much longer to
execute than appropriately written code relying solely on integer
operations. This is less important than the correctness issues, but
still can be important.

 

[Seebs]

How about

if(fabs((double)x * double(y)) > INT_MAX)
return 1;

It's a one-liner. You need a two liner to handle the special case of
INT_MIN, which probably isn't worth it.

On at least some systems, double does not have enough bits to accurately
represent all possible values of int; in particular, past a certain point,
you stop having odd numbers. About twice that point, you stop having numbers
which are not multiples of 4...

One can conceive of a pair of numbers which have the interesting property
that x * y is an overflow operation on int, but that this calculation
does not detect it. (Well, assuming we fix the typo on the second cast.)

-s