A new faster algorithm to compute 64-bit signed floor division

Signed integer division usually rounds toward zero, but floor division rounds toward negative infinity, which gives the expected results for negative timestamps, tile coordinates, and repeating cycles. The distinction matters when converting Unix seconds to whole days: dividing a negative timestamp with ordinary C++ division gives the wrong day count unless the quotient is corrected. That correction commonly requires checking the remainder, while simply testing the quotient can be slower. Although compilers efficiently translate division by a fixed constant into multiplication and shifts, floor division is often handled with an extra correction; languages and libraries also frequently use this conventional approach.

The proposed method computes floor division directly using a precomputed multiplier selected according to the input’s sign, followed by a multiply and shift. It is designed to work across the full signed range and can be generated for 64-, 32-, 16-, and 8-bit integers, including for faster positive-modulus and Euclidean division. Benchmarks report 10-20% higher throughput than established methods on ARM for most 64-bit divisors, with equal or better latency. On x86, it is about 5-10% faster for many divisors, but slower for others and generally less favorable in latency. The discussion also reviews existing compiler techniques and prior algorithms, supplies code-generation and testing tools, and cautions that performance depends on the divisor and hardware.