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