Bitwise Division
h14s.p5r.org
Bitwise Division
1–10 of 75 posts
Re: Bitwise Division
#2Just precompute a list of values?
Re: Bitwise Division
#3Don’t modern compilers do this automatically (and aggressively) for almost any division by a constant?
Re: Bitwise Division
#4The compiler is already reducing integer division by a constant into these things.
Those algorithms become more important when you're dividing by a value known at runtime but which remains the same during parts of the program. That's where libdivide comes in.
Re: Bitwise Division
#5Wouldn’t a lookup table be a whole lot easier? I’d think a 64 entry table of integers would be fast to access once cached.
Re: Bitwise Division
#6My goto would have been multiplication by (1/7)*2^16 followed by a right shift. You still need to verify the constant (or can add another after the multiply) to get it to work in every case. Used this once to extract digits of a 16bit integer from left to right.
Re: Bitwise Division
#7The compiler is already reducing integer division by a constant into these things. Those algorithms become more important when you're dividing by a value known at runtime but which remains the same during parts of the program. That's where libdivide comes in.
See https://godbolt.org/z/3Yqbceaza for what godbolt says clang produces.
Keep in mind that this doesn't use the fact that we know that the input is between 0 to 63.
Re: Bitwise Division
#8I wonder whether the author ever ran a benchmark?
Alas, the commenting system on their website seems broken, so can't ask there.
Re: Bitwise Division
#9My goto would have been multiplication by (1/7)*2^16 followed by a right shift. You still need to verify the constant (or can add another after the multiply) to get it to work in every case. Used this once to extract digits of a 16bit integer from left to right.
Your C compiler will do this for you automatically. See eg https://godbolt.org/z/3Yqbceaza
(I don't know what language is used here. I'm just assuming something like C.)
Re: Bitwise Division
#10Don’t modern compilers do this automatically (and aggressively) for almost any division by a constant?
The author mentions that this is for a variable length (i.e. bigint) format. Sure, I bet mature bigint libraries do stuff like this automatically when sensible, but I still think it's interesting to read about someone figuring out such things on their own.