Integer Division via Floating Point: A Surprisingly Simple Trick
Moving integer division to floating-point is trivial
Integer division and remainder operations are notoriously slow on modern CPUs, while floating-point division is much faster. This post shows that for integers fitting within the precision of double or single precision, you can replace integer division with floating-point division and a fused multiply-add, yielding the exact integer quotient and remainder under standard rounding. The math is straightforward, and the author walks through the proof, noting that ties in rounding are impossible for division in base 2. The technique is especially promising for SIMD and constant divisors, with caveats about conversion costs and precision limits.
My claim is: for two integers x & y (signed or unsigned) that fit in 53/24 bits for double/single precision respectively, with both promoted to floating point then: d = trunc(x/y); m = -fma(d,y,-x);
- taeric
I'm curious that the latency of these is actually worse than the latency of floating operations. Yes, they are worse than many integer instructions, but they seem to be on basically the same order as the equivalent float operations?
- juancn
I would love to have some benchmarks for this on some reasonably practical scenario.
In many common cases shift and masking can replace integer division (i.e. hash tables) and you avoid division altogether, and that probably has about the cost of converting an int to a float.
- RossBencina
x and y are integers represented as floating point
> d = trunc(x/y); // floor works for unsigned
>
> // NOTE: if only want 'd' and it's being converted to an
> // integer then the truncate or floor operation is
> // free in the float to integer conversion.
Please show me how to portably truncate or floor a floating point value to an int in C for "free".