--- title: A new faster algorithm to compute 64-bit signed floor... description: A new technique computes signed 64-bit floor division by a compile-time constant faster than existing known methods. Benchmarked against division by 86400... canonical: https://daily.dev/posts/a-new-faster-algorithm-to-compute-64-bit-signed-floor-division-76nsrtnuq twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: A new faster algorithm to compute 64-bit signed floor division | daily.dev og:description: A new technique computes signed 64-bit floor division by a compile-time constant faster than existing known methods. Benchmarked against division by 86400... og:url: https://daily.dev/posts/a-new-faster-algorithm-to-compute-64-bit-signed-floor-division-76nsrtnuq og:image: https://api.daily.dev/og/posts/76nSrtNuQ.png og:image:alt: A new faster algorithm to compute 64-bit signed floor division og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # A new faster algorithm to compute 64-bit signed floor division **[Hacker News](https://daily.dev/sources/hn)** · 37 min read · 1 upvotes · 0 comments ## Summary A new technique computes signed 64-bit floor division by a compile-time constant faster than existing known methods. Benchmarked against division by 86400 (seconds per day), it beats built-in compiler division and prior fast approaches like the Granlund-Montgomery and Robison multiply-shift algorithms on most ARM chips and mixed x86 chips. On Clang, the new algorithm has the highest throughput for all tested divisors, tied with 'gm-v2' in some cases. A simpler branchless trick from a 2017 Stack Overflow answer by user ufoguy already gave about 50% more throughput on most devices. The piece also traces a TensorFlow floor-division bug that persisted from 2017 to 2021. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### How do I implement fast signed 64-bit floor division by a compile-time constant in C++? Use a sign-selected multiplier: precompute M = (2^(S) / divisor + 1) for a chosen shift S, adjust the multiplier by x >> 63 to pick between round-up and round-down variants, then compute (x as 128-bit * m) >> S. This technique, demonstrated for division by 86400, avoids the extra cycles of modulus-based corrections and compiles to a single shift-add plus mul-shift on ARM64. _Developers optimizing numeric hot paths can track techniques like this sign-selected floor division trick on daily.dev._ ### Why does x/86400 give wrong results for negative Unix timestamps in C++? Standard C++ division truncates toward zero instead of flooring toward negative infinity, so negative timestamps before 1970 divided by 86400 produce an off-by-one day count whenever there is a nonzero remainder. The fix is to use floor division, which can be implemented as (x + (x<0))/86400 - (x<0), correctly rounding toward negative infinity for all inputs. _Anyone converting timestamps to day counts can check correctness patterns like this before shipping on daily.dev._ ### What was the floor division bug in TensorFlow's cwise_ops.h? TensorFlow's floordiv implementation computed -(abs_x + abs_y - 1) / abs_y for mixed-sign operands, which overflows the signed 64-bit range for extreme input values, and its branching also prevented compilers from generating branchless code per divisor sign. The buggy version shipped in the 1.0 release in February 2017 and was not fixed until May 2021, over four years later. _Teams hardening numeric libraries can watch for long-lived overflow bugs like this via daily.dev._ ## Community take How the wider developer community reacted, aggregated from 4 discussions and 12 comments across hackernews (as of 2026-10-29). **TL;DR:** The writeup is well received as a neat, well-documented optimization, though several commenters note the underlying mul-shift trick is decades old and the real novelty is the range-splitting for floor division with negative inputs. **Sentiment:** 55% positive · 40% mixed · 5% skeptical **The case for** - The range-splitting technique for handling negative inputs in floor division is seen as the genuinely new contribution. - Several found the writeup clear and said they'd consider adopting the technique in their own compilers. - One pointed to hardware progress (fast native integer division on recent CPUs) making some of these tricks less necessary, which is itself seen as a positive development. **The pushback** - Multiple commenters note the core mul-shift-for-constant-divisor trick is a well-known compiler optimization dating back to the 90s. - Robison-style division is argued to still be preferable in cases with non-compile-time or many varying divisors since it SIMDifies more easily. - On some recent hardware (e.g. Ryzen 7000), plain integer division is now fast enough that these specialized algorithms are becoming obsolete. **By community** - hackernews (positive): Commenters praised the writeup while clarifying which parts are genuinely novel versus long-known compiler tricks, and shared related work and alternative approaches. **Hottest debate:** Whether the core technique is truly novel or just a repackaging of the decades-old mul-shift optimization, with the real contribution being the floor-division range-splitting for negative numbers. **Open questions** - How does the new algorithm compare against Daniel Lemire's fast division techniques? - Will the author formalize this into a published paper with help from established researchers in the space? **Highlights** > Hello, you are correct that part of it is done to death for standard integer division. The `new` thing is the range-splitting which achieves the floor division for negative inputs (eg. sign-selected for 60% of divisors, and the negative/positive bump for the remaining 20%/20% of cases each). > — [benjoffe on hackernews · 1 comments](https://news.ycombinator.com/item?id=50285413) > I love to see this kind of optimization, of course, but there are other cases where Robison division is great, just because it has basically the same form for every divisor: 1. The divisor is not actually a compile-time constant, but comes from a small set. You can compute a table of corresponding constants and use the same code for every divisor. 2. You want to do many divisions by many different divisors (whether known at compile-time or drawn from a small set, like above, or pre-computable and applied many times... think of something like a quantization matrix for image coding, for example). Here Robison easily SIMDifies, whereas an algorithm that needs different code paths for every divisor is going to be much more difficult. Regarding the lack of native signed-unsigned multiplies, as someone who does a lot of multimedia processing, I find the set of available multiplication instructions on x86 and ARM to be rather shamefully limited (especially x86). I recall a colleague who used to optimize for VideoCore (the GPU in a Raspberry Pi) saying that when he first started he was astounded that it had 80 different multiply instructions, but within a year or two he had used basically all of them. > — [derf\_ on hackernews](https://news.ycombinator.com/item?id=50285708) > For SWAR algorithms, calculating floor(64/n) for 0 < n < 65 has always been crucial, so I spent a lot of time developing fast division algorithms. But since the Ryzen 7000 series, the fastest approach has been to simply cast 64/n to an integer. I'm kind of sad that all those algorithms have become obsolete, but at the same time, I'm happy that integer division has finally become fast enough in hardware. > — [bugake on hackernews](https://news.ycombinator.com/item?id=50287976) > Neat result, and good writeup! I don't have time to compare them, but another resource you might look at is Daniel Lemire's "Fast Division": https://github.com/lemire/fast_division If you've come up with something better, I'd encourage you to contact Daniel and see if he's interested in helping you write it up into a paper. He's friendly, and may be better positioned to get the optimizations into mainstream compilers. > — [nkurz on hackernews](https://news.ycombinator.com/item?id=50288528) > The mul-shift part is what any optimizing compiler does for known divisors and has done since the 90s, if anything it was more vital back then when the gap between div and mul was wider than today. > — [Sharlin on hackernews](https://news.ycombinator.com/item?id=50287888) **Source threads** - [hackernews](https://news.ycombinator.com/item?id=50256409) · 112 points · 12 comments - [hackernews](https://news.ycombinator.com/item?id=50250218) · 5 points · 0 comments - [hackernews](https://news.ycombinator.com/item?id=50264835) · 3 points · 0 comments - [hackernews](https://news.ycombinator.com/item?id=50272258) · 2 points · 0 comments ## Similar posts on daily.dev - [\[2604.07902\] Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets](https://daily.dev/posts/2604-07902-optimization-of-32-bit-unsigned-division-by-constants-on-64-bit-targets-uy09tvu32) · Hacker News · 0 upvotes · 0 comments - [Moving integer division to floating-point is trivial](https://daily.dev/posts/moving-integer-division-to-floating-point-is-trivial-7s6ttpx3b) · MBR · 1 upvotes · 2 comments - [Novak Kaluđerović - Kolja](https://daily.dev/posts/novak-kalu-erovi---kolja-4ccsvuutc) · Lobsters · 0 upvotes · 0 comments --- Tags: [#performance](https://daily.dev/tags/performance), [#c++](https://daily.dev/tags/c++), [#compiler-optimization](https://daily.dev/tags/compiler-optimization) [View this post on daily.dev](https://daily.dev/posts/a-new-faster-algorithm-to-compute-64-bit-signed-floor-division-76nsrtnuq) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"A new faster algorithm to compute 64-bit signed floor division","url":"https://daily.dev/posts/a-new-faster-algorithm-to-compute-64-bit-signed-floor-division-76nsrtnuq","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/a-new-faster-algorithm-to-compute-64-bit-signed-floor-division-76nsrtnuq"},"datePublished":"2026-10-29T10:09:22.654Z","dateModified":"2026-10-29T14:10:17.438Z","description":"A new technique computes signed 64-bit floor division by a compile-time constant faster than existing known methods. Benchmarked against division by 86400...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/fc7f79c35c2d2afa9409c55e58ad2790?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/fc7f79c35c2d2afa9409c55e58ad2790?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Hacker News","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Hacker News","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/hn","url":"https://daily.dev/sources/hn"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/a-new-faster-algorithm-to-compute-64-bit-signed-floor-division-76nsrtnuq","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":1},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"performance,c++,compiler-optimization","timeRequired":"PT37M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Hacker News","item":"https://daily.dev/sources/hn"},{"@type":"ListItem","position":3,"name":"A new faster algorithm to compute 64-bit signed floor division"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/a-new-faster-algorithm-to-compute-64-bit-signed-floor-division-76nsrtnuq#faq","mainEntity":[{"@type":"Question","name":"How do I implement fast signed 64-bit floor division by a compile-time constant in C++?","acceptedAnswer":{"@type":"Answer","text":"Use a sign-selected multiplier: precompute M = (2^(S) / divisor + 1) for a chosen shift S, adjust the multiplier by x \u003e\u003e 63 to pick between round-up and round-down variants, then compute (x as 128-bit * m) \u003e\u003e S. This technique, demonstrated for division by 86400, avoids the extra cycles of modulus-based corrections and compiles to a single shift-add plus mul-shift on ARM64. Developers optimizing numeric hot paths can track techniques like this sign-selected floor division trick on daily.dev."}},{"@type":"Question","name":"Why does x/86400 give wrong results for negative Unix timestamps in C++?","acceptedAnswer":{"@type":"Answer","text":"Standard C++ division truncates toward zero instead of flooring toward negative infinity, so negative timestamps before 1970 divided by 86400 produce an off-by-one day count whenever there is a nonzero remainder. The fix is to use floor division, which can be implemented as (x + (x\u003c0))/86400 - (x\u003c0), correctly rounding toward negative infinity for all inputs. Anyone converting timestamps to day counts can check correctness patterns like this before shipping on daily.dev."}},{"@type":"Question","name":"What was the floor division bug in TensorFlow's cwise_ops.h?","acceptedAnswer":{"@type":"Answer","text":"TensorFlow's floordiv implementation computed -(abs_x + abs_y - 1) / abs_y for mixed-sign operands, which overflows the signed 64-bit range for extreme input values, and its branching also prevented compilers from generating branchless code per divisor sign. The buggy version shipped in the 1.0 release in February 2017 and was not fixed until May 2021, over four years later. Teams hardening numeric libraries can watch for long-lived overflow bugs like this via daily.dev."}}]} ```