Compare two integer products without overflow

Question

I need to find whether a*b >= c*d where a,b,c,d are signed 32-bit integers ('int' on my machine).

Is it possible to compare those products using only 32-bit signed integers without overflow so that result is correct for all possible values?

I thought about a/d >= c/b.

However it fails on '2*7 >= 3*5' (false) because '2/5 >= 3/7' ('0 >= 0') is true.

Answer 1

For the moment, I'm going to assume the inputs are signed integers.

This being the case, we want to start by checking the signs. If one side is negative and the other positive, that's enough to tell us the result (negative is obviously smaller than positive) so we're done.

If both sides of the equality will be positive or both negative, we cache the sign for the result, then get rid of the signs so we can deal with unsigned numbers for the multiplication itself.

Once we have unsigned numbers, we can do the multiplication by treating each 32-bit integer as the sum of two different numbers, one representing the lower bits and one the upper bits of the input number. So, you'd convert each of a, b, c and d to two numbers with only 16 significant bits. So, for the left side, we'd have:

al = a & 0xffff;
au = a >> 16;

bl = b & 0xffff;
bu = b >> 16;

So:

a * b 

...is the same as:

(al + au << 16) * (bl + bu << 16)

and using the distributive property, we can turn that into:

al * bl + au<<16 * bl + al * bu<<16 + au<<16 * bu<<16

Since a * (b * c) = (a * b) * c, we can do all the bit-shifts after we do the other multiplications, so this turns into:

al * bl +            // we'll call this intermediate result "lower"
(au * bl) << 16 +
(al * bu) << 16 +    // we'll call the sum of these two "mid" 
(au * bu) << 32      // we'll call this one "upper"

Now the important point: our bit-masking ensures that each multiplication step has inputs that only have 16 significant bits apiece, so each intermediate result will only have 32 significant bits, so each will fit into a single 32-bit integer without overflowing.

From there, we have to sum the terms. This is slightly non-trivial, but still fairly tractable. First, we have to figure out whether the sum of a term will create a carry. One way to do this is like this:

bool carry(unsigned a, unsigned b) { 
    return a > (std::number_limits<unsigned>::max() - b);
}

Then our result is lower + mid<<16 + upper << 32. Since we're dealing in 32-bit integers, it's probably easiest to take mid and split it into an upper and a lower half. Its lower half will be added to lower, and its upper half to upper. Our result will then be spread across two (unsigned) 32-bit integers, one containing lower + mid_lower, the other containing upper + mid_upper + carries.

From there it's a simple matter of recovering the signs we stored at the beginning, then comparing the upper halves and if and only if they're equal, comparing the lower halves.

If your numbers start out unsigned, then you can just kind of skip lightly over the parts that involve signs.