Dealing with possible overflows

[MWB]

Hi CLC,
Suppose I want to evaluate (x*y)/z where x,y,z are unsigned int's.
In some cases, though (x*y) might overflow the (xy)/z (the actual
product) might be representable as an unsigned int, I was wondering
how to get the correct answer in such a case.
In one specific case the answer is easy to see : x is the only "large"
number among the three- y and z are small.
Then calculate the answer as (x/z)*y + ((x -(x/z)*z)*y)/z
The following program illustrates my point:
#include <stdio.h>
#include <limits.h>

typedef unsigned int uint;

int
main(void)
{
uint x=(UINT_MAX-1)/2,y=4,z=5,w;
w=(x*y)/z;
printf("x=%u y=%u z=%u w=%u\n",x,y,z,w);
w= (x/z)*y + (x - (x/z)*z )*y/z;
printf("x=%u y=%u z=%u w=%u\n",x,y,z,w);
return 0;
}
I was wondering, if the above trick can be extended. Are there some
other ways to deal with such overflows?

TIA,

[Allan Bruce]

"MWB" <ma********************@yahoo.com> wrote in message
news:f4**************************@posting.google.c om...

Hi CLC,
Suppose I want to evaluate (x*y)/z where x,y,z are unsigned int's.
In some cases, though (x*y) might overflow the (xy)/z (the actual
product) might be representable as an unsigned int, I was wondering
how to get the correct answer in such a case.
In one specific case the answer is easy to see : x is the only "large"
number among the three- y and z are small.
Then calculate the answer as (x/z)*y + ((x -(x/z)*z)*y)/z

I would cast to a double for the calculation, and then back to unsigned int.
This is likely to be faster, and easier to understand.
Allan

[Michael Mair]

Hiho,

Suppose I want to evaluate (x*y)/z where x,y,z are unsigned int's.
In some cases, though (x*y) might overflow the (xy)/z (the actual
product) might be representable as an unsigned int, I was wondering
how to get the correct answer in such a case.
1) How to arrive at optimal x,y,z:

If you want to do it "right" without subdividing into special cases, you
calculate the greatest common divisor a of x and z and reduce the
fraction (x*y)/z to (x1*y)/z1 where x1 = x/a, z1 = z/a and repeat that
arriving at x1*y1/z2, where y1 = y/b, z2 = z1/b and b is gcd(y, z1).
The greatest common divisor can be calculated by using the Euclidean
algorithm. In your case, you can do without some of the tests but
the algo looks like that in C for ints (the while loop is the algorithm
itself:

int gcd (int a, int b)
{
int r;

/* get nonnegative numbers: Works only for a,b>=-INT_MAX */
if (a < 0)
a = -a;
if (b < 0)
b = -b;

// force a >= b
if (b > a) {
r = a; a = b; b = r;
}

// exclude special case
if (b == 0) {
if (a)
return(a);
else // gcd(0, 0) ist unendlich gross...
return(-1);
}

// Euclidean algorithm without saving the coefficients
while ( (r = a % b) ) {
a = b;
b = r;
}

return(b);
}

If you really want to apply tricks, then sort x1, y1 in a way you need
them.

In one specific case the answer is easy to see : x is the only "large"
number among the three- y and z are small.
Then calculate the answer as (x/z)*y + ((x -(x/z)*z)*y)/z
The following program illustrates my point:
#include <stdio.h>
#include <limits.h>

typedef unsigned int uint;

int
main(void)
{
uint x=(UINT_MAX-1)/2,y=4,z=5,w;
w=(x*y)/z;
printf("x=%u y=%u z=%u w=%u\n",x,y,z,w);
w= (x/z)*y + (x - (x/z)*z )*y/z;
printf("x=%u y=%u z=%u w=%u\n",x,y,z,w);
return 0;
}
I was wondering, if the above trick can be extended. Are there some
other ways to deal with such overflows?

TIA,

2) "Tricks"

After having reduced the fraction, you can do as suggested and go
to types which can hold the product.
C99:
If ULLONG_MAX >= UINT_MAX*UINT_MAX, then I would use unsigned long long
for the actual computation. This has the advantage of yielding the
correct result which can be tested against UINT_MAX.
C89:
If you won't go up to UINT_MAX but only to some value MAX and this
value can be represented by less than or equal to half the bits of your
double mantissa, that is for n mantissa bits MAX*MAX<=pow(2,n)-1 holds,
then you can use double. Even if that is not true, you can at least
make some predictions about the quality of your computations and have
the advantage of readable code.
long double is of course also an option :-)

If the range of values you need is too large for both of these
ways, then use two unsigneds to store the result of x*y, one high
and one low "word". Just have a look around on the web.
Cheers
Michael