I would like to know the fastest way to do proportion calculation, that is y = x * a / b, where all values are 32 bit, unsigned, and a and b are fixed (initialized once, and then don't change) but not known at compile time. The result is guaranteed not to overflow (even thought the intermediate multiplication might need 64 bit). The programming language doesn't matter much, but Java would be best for my case. It needs to be as fast as possible (nanoseconds matter). I currently use:
int result = (int) ((long) x * a / b);
But division is slow. I know about Perform integer division using multiplication, so best would be a formula of type:
int result = (int) (((long) x * factor) >>> shift);
where factor and shift can be calculated from a and b (that calculation can be slow).
I tried to simply replace the division part of the original formula, but it doesn't work because the result of the two multiplications don't fit in 64 bit:
// init
int shift = 63 - Integer.numberOfLeadingZeros(b);
int factor = ((1L << shift) / b) + 1;
...
// actual calculation
int result = (int) ((long) x * a * factor) >>> shift);
The result doesn't actually have to be fully accurate in my case (off by one would be OK).
What about
long a2 = a & 0xFFFFFFFFL;
long b2 = b & 0xFFFFFFFFL;
checkArgument(b2 > 0);
double dFactor = (double) a2 / b2;
shift = 0;
while (dFactor < 1L<<32) {
dFactor *= 2;
shift++;
}
factor = (long) dFactor;
for the preparation and
int result = (int) (((x & 0xFFFFFFFFL) * factor) >>> shift);
for the fast part? Now we have 2**32 <= factor < 2**33 and for any int x >= 0, the product x * factor < 2**31 * 2**33 = 2**64 just fits in an unsigned long. No bits get wasted. The conversion of dFactor to long rounds down, which may be suboptimal.
The preparation could surely be sped up, especially the loop can be eliminated by looking at the leading zeros first. I wouldn't bother with eliminating the double as it makes things simple.