TECH Signal 375
Moving integer division to floating-point is trivial
↗
Illustration only Photo by Drew Beamer on Unsplash
Integer division and remainder can be computed via floating-point division for integers that fit within the floating-point mantissa.
Floating-point division units on modern CPUs typically have lower latency and higher throughput than integer division hardware, so moving the operation can speed up hot code paths. The technique requires only a truncation and a fused-multiply-add, which are cheap once the values are in floating point, but it adds conversion and rounding-mode overhead that must be managed. It is only applicable to integers up to the precision limit of the chosen floating-point format, so larger values still need the traditional integer path.
Written by elseif from the cluster below · every claim links back to a sourceThe three things worth knowing
Promoting integers to floating point, truncating the quotient, and using an FMA yields the same integer division and remainder for values that fit within the mantissa.
Floating-point division often has shorter latency and more execution units, making the approach attractive especially in SIMD code.
The method incurs conversion costs, requires careful handling of rounding mode or hardware support, and is limited to integers no wider than 53 bits for double precision or 24 bits for single precision.
THE READ
What the cluster adds up to.
Current integer division hardware on x86 and similar architectures suffers from high latency and limited throughput, while floating-point division units are generally faster and more plentiful. This performance gap motivates exploring alternative ways to compute integer quotients and remainders. The proposal leverages the fact that floating-point division already provides a close approximation to the exact rational result.
The core algorithm converts the two operands to floating point, computes the floating-point quotient, and then truncates it toward zero to obtain the integer quotient. The remainder is derived with a fused multiply-add that multiplies the truncated quotient by the divisor and subtracts the product from the dividend, all in floating point. The approach assumes the standard round-to-nearest, ties-to-even mode, which guarantees no tie cases for division results.
A critical limitation is the size of the integer operands: they must fit within the mantissa of the floating-point format used, which means up to 53 bits for double precision and 24 bits for single precision. Signed integers are easier because their magnitude is smaller, but the method still works for unsigned values by treating them as signed magnitudes. Conversions between integer and floating point can be costly, and many x64 CPUs lack a direct unsigned-to-float instruction, requiring extra handling.
In practice the technique shines when applied in SIMD loops where many divisions share the same overhead, allowing the conversion and rounding-mode changes to be amortized across many elements. Compilers can eliminate the conversion entirely for compile-time constant divisors, and for runtime constants reused a few times, software libraries like libdivide may be preferable. Nevertheless, the method provides a viable path to replace a slow integer division with a faster floating-point sequence when the operand size constraints are satisfied.
Adopting this approach means adding code to set the rounding mode toward zero before the division and restoring it afterward, unless the hardware supports per-instruction rounding control. It also requires ensuring that the target platform provides an FMA instruction and that the conversion path does not become the bottleneck. When these conditions are met, developers can achieve lower latency division without sacrificing correctness for the supported integer range.
Written by elseif from the cluster below · checked for specifics the sources never containedTHE CLUSTER