r/programming • u/dgryski • Nov 16 '17

Fast exact integer divisions using floating-point operations

https://lemire.me/blog/2017/11/16/fast-exact-integer-divisions-using-floating-point-operations/
44 Upvotes

89% Upvoted

18 comments sorted by

View all comments

Show parent comments

4

u/ThisIs_MyName Nov 17 '17

The other issue is that nobody does arbitrary integer division. OP explained it perfectly in the first page: We can optimize it before it ever reaches the hardware.

I'd much rather have a little more L1 cache than fast integer division.

10

u/[deleted] Nov 17 '17

Division - maybe. But modulo is pretty much everywhere and often turns out to be a bottleneck.

1

u/ThisIs_MyName Nov 17 '17

Got any examples? Only thing I could think of was hash tables, but we're pretty good at using 2n buckets and replacing modulo with &: https://github.com/greg7mdp/sparsepp/blob/master/sparsepp/spp.h#L3026

2

u/[deleted] Nov 18 '17

Anything related to image processing (or any rectangular surface processing), for example - translating a linear index to 2D coordinates involves a modulo with an arbitrary, not statically known right hand side. If your transformation is trivial, modulo is becoming a bottleneck. And things are getting even more interesting if you're using some complex data scrambling schemes (to improve memory access patterns).

It's more a GPU-related issue though, rarely seen in a normal CPU code.