4 ms·
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, an
by pbsd 12y ago
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 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
which has a shorter critical path.
- kazagistar 12y ago> 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.
- pbsd 12y agoIt'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.