search

ridiculousfish / libdivide

Official git repository for libdivide: optimized integer division
http://libdivide.com
Other
1.09k stars 77 forks source link

Modulo support #9

Open sesse opened 8 years ago

sesse commented 8 years ago

Hi,

Is there a chance to get support for the modulo operation in libdivide, without having to do x - (x / d) * d manually? Ideally, of course, in the same operation as div if it's possible to get it cheap.

On a quick test, it looks like GCC can generate code with only one mul for div+mod of the same divisor, so it should. be possible. (I tested with the rather arbitrary value of 17; div-only was six instructions including a mul, and div+mod was twelve in total, with no additional mul.)

sesse commented 8 years ago

Oh doh, of course this is because 17 can be done as a LEA instruction instead of a mul. So perhaps this was too optimistic?

ridiculousfish commented 8 years ago

Yeah, to my knowledge, there is no way to compute mod faster than dividing, multiplying, and subtracting. Maybe someone will find a way some day.

pcbeard commented 7 years ago

Perhaps at least a convenience function that works like std::div() could be provided, so we don't all have to roll our own. I know it's not a lot of code, but it might help.

bmkessler commented 5 years ago

For 32-bit mod on x64 there is a new mod method that involves two multiplications https://arxiv.org/abs/1902.01961 and is benchmarked faster than the current divide, multiply, and subtract implementation in libdivide. The author's implementation is here: https://github.com/lemire/fastmod

KingDuckZ commented 5 years ago

+1 I came here after finding the same project, specifically this post. I hope it's useful.

DonaldTsang commented 5 years ago

Maybe adding the post's solution to libdivide would be the right thing to do? What do you think @ridiculousfish ?

colinb2r commented 4 years ago

To ridiculousfish: you may or may not recall that a few years ago we had an email exchange on faster integer division by constant divisors.

"Maybe someone will find a way some day." - Others have already mentioned the recent Lemire-Kaser-Kurz paper, which I only discovered yesterday. What they haven't said is that libdivide is mentioned in their paper, and that in their paper one of their benchmarks for their direct computation of remainders - compared with first calculating the quotient, and secondly the remainder with r = n - q*d - is with libdivide. I'd say that counts as a citation!

ridiculousfish commented 4 years ago

Yep, I think we should implement their remainder algorithm in libdivide too!