There is one oft-forgotten case that neither compilers nor (seemingly) libdivide seem to handle: when we know that an integer is a multiple of some constant, and we just want to get the result of the exact division.
This case allows for a simpler method, exemplified here (it also works for signed integers, but more care is needed with the shifting): http://goo.gl/D5q9IO
EDIT: On second thought, compilers are also not doing their best job on that example. f1 could be simplified to
mov rax, 4865095698
add edi, 1
imul rdi
shrd rax, rdx, 39
ret
Re:Three Optimization Tips for C++
by kazagistar on Thursday May 08, 2014 @12:48PM
(#7716239)
> when we know that an integer is a multiple of some constant
How is a compiler supposed to track that information? That requires some serious dependent typing.
It's not (by itself, at least). But you can give it hints, as in my example above (with __builtin_unreachable; other compilers have similar facilities, like __assume in MSVC). The compiler should, in theory, be able to deduce that x % 113 is always 0, and therefore must be a multiple of 113.
A deep understanding of the algorithm took me a long time, I think a few months. That was mainly due a lack of information describing the technique. The paper that Andrei linked to (Granlund-Montgomery) is dense and contains a significant error, which I was never able to get resolved. Henry Warren's celebrated Hacker's Delight is more accessible, but is also more of a proof-of-correctness than a learning resource. So my intuitive understanding came from my own investigating and playing around, which is what lead me to find an improvement on the algorithm.
Implementing libdivide took me maybe six months of my hobby time. It's not just the core algorithm - there's a lot of auxiliary functions, for example to compute the high half of a 64 bit multiply in SSE. But working at that level is tons of fun.
Incidentally, I wrote up what I hope to be the most accessible (yet still rigorous) description of the algorithm at http://ridiculousfish.com/blog/posts/labor-of-division-episo... . I advise anyone interested in learning more to start there, instead of the Granlund paper.