Efficient 63-bit long computation of (a*b)/c in Java

Question

I would like to compute (a*b)/c in Java in the most efficient way where:

• a, b and c are unsigned long values (guaranteed to fit in 63 bits, i.e. with zero sign bit)
• The result is also guaranteed to fit in 63 bits
• The product (a*b) is likely to overflow with regular long multiplication

What is the most efficient way to calculate this? I have a working solution with BigInteger conversions but am looking for something faster (minimal clock cycles, preferably zero memory allocation)

I have heard about premature optimization, and I have determined that this optimization is worthwhile.

Answer 1

Mathematically, (a*b)/c is equal to both (a/c)*b and (b/c)*a. The most accurate result only using integer division will be dividing the larger of a and b by c, then multiplying by the other:

long result = a > b ? (a / c * b) : (b / c * a);

While this will be as fast as you can get it, its accuracy is limited by the truncation of the remainder of the division. You can simulate rounding, thus doubling the accuracy at only a tiny cost in performance, by adding half of c before the division:

long result = a > b ? ((a + c/2) / c * b) : ((b + c/2) / c * a);