New algorithm speeds up 64-bit signed floor division by constants on ARM and x86

A post published on benjoffe.com on 27 October 2026 and surfaced on Hacker News two days later introduces a new algorithm for signed 64-bit floor division when the divisor is known at compile time. According to the author's benchmarks, it delivers 10-20% higher throughput than the best existing algorithms on ARM chips and roughly 5-10% on x86 for the majority of divisors, a concrete win in a corner of integer arithmetic that has seen little movement since the mid-1990s.

The problem floor division solves

Floor division rounds toward negative infinity, while the truncated division built into C, C++ and many other languages rounds toward zero. The difference matters as soon as dividends can be negative: dividing a Unix timestamp in seconds by 86400 to get a day count works fine with truncated division until someone supplies a date before 1970, the post explains. Floor semantics are what calendar math, tile coordinates and angle tracking generally need.

Yet the ecosystem around it is, in the author's words, in poor shape. Mainstream compilers and languages such as C, C++, Go and Swift do not provide floor division natively. Implementations that do exist almost never use the fastest known algorithms, and at least one prominent software library shipped an overflowing, buggy version for more than four years. Typical web searches and LLM prompts surface only the slow approaches, and Hacker's Delight, the standard reference for low-level arithmetic, devotes almost no space to the topic.

How compilers divide by constants today

When a divisor is fixed at compile time, compilers skip the CPU's divide instruction and instead emit a multiply-shift sequence: multiply the dividend by a precomputed magic constant in a wider register, shift, and, for signed division, apply a final correction based on the sign bit so negative results round toward zero. Some divisors, 100 among them, are what the post calls uncooperative: their magic constant needs all 64 bits, which forces an extra fix-up step. Overall, the author puts ordinary constant division at roughly the cost of one multiplication plus 2-3 cycles.

The new trick

The novelty is folding the floor adjustment into the multiplier itself. Rather than multiplying by a fixed constant and patching the result afterwards, the algorithm adds the dividend's sign bit, cheaply extracted by shifting the value right by 63, to the magic constant before a single 128-bit multiply. The high part of the product, shifted appropriately, is the floored quotient in one pass. In the worked example for 86400, the constant is derived from 2^79 divided by the divisor and the product is shifted right by 79. The author concedes the idea is simple enough that prior art may exist, but reports finding no documentation of it anywhere, and offers the page partly to make the technique discoverable.

What the benchmarks show

Under ideal compilation, the post reports:

On ARM, tested on an Apple M4 Pro and a Snapdragon X1-26-100, throughput is 10-20% faster than existing algorithms for most 64-bit divisors, occasionally tied, with equal or better latency.

On x86, tested on an AMD Ryzen 9 9950X3D and an Intel Core i7, throughput improves about 5-10% for roughly 80% of positive divisors and 60% of negative divisors; the remaining cases are slower, with latency usually somewhat worse but competitive.

For context, the post's snapshot benchmark for division by 86400 shows built-in approaches in languages such as Rust and Zig running about twice as slow as the 1994 Granlund-Montgomery technique. Rust's div_euclid matches floor division only for positive divisors. The new method also works at 8-, 16- and 32-bit widths, may suit 32-bit or SIMD use cases, and yields faster positive-modulus and Euclidean division as by-products. The full benchmark section covers more than 40 divisors across platforms.

Ready-to-use code and testing

The post ships a generator that produces a self-contained C++ file exercising 65,535 divisors from -32768 to 32777, including boundary tests, plus a builder that emits ready-to-paste functions for any bit-width and divisor and a reusable C++ template with microarchitectural tuning. The stated license applies only to verbatim copies; re-implementing the same logic requires none. The author's other blunt piece of advice: never hand-roll your own fast floor division, use tested code.

Why it matters

Division by constants is everywhere in systems programming: 86400 for time math, fixed-point scaling, calendar loops, spatial indexing. The floor variant is the one with correct behavior for negative operands, yet mainstream languages either omit it or ship slow, occasionally buggy versions. A documented, boundary-tested algorithm that measurably beats techniques dating to 1994 gives compiler and standard-library authors a concrete upgrade path, and the accompanying test harness targets exactly the overflow bugs that have already bitten a prominent library. For performance-sensitive code, it is a drop-in micro-optimization with numbers to back it up.