Wouldn’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.
The divisor is from 0 to 63. The dividend is a variable bit length integer, i.e. a bigint.
Bitwise Division
11–20 of 75 posts
Re: Bitwise Division
#12Horner’s method [0] is also commonly used on small microcontrollers without divide (or multiply) instructions.
Re: Bitwise Division
#13Nice, if a little bit hand wavy. Seems a little bit of a stretch to call an operation that still includes a multiply bitwise, though.
Re: Bitwise Division
#14I wonder whether the author ever ran a benchmark? Alas, the commenting system on their website seems broken, so can't ask there.
I hope this isn't considered doxing, but he has his name and location on the blurb on the side; you may be able to reach him through linkedin: https://www.linkedin.com/in/christianplesnerhansen/
Re: Bitwise Division
#15The 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.
> Keep in mind that this doesn't use the fact that we know that the input is between 0 to 63.
You can use __builtin_assume for this: https://godbolt.org/z/K4jKhxnTq
Re: Bitwise Division
#16Wouldn’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.
The divisor is from 0 to 63. The dividend is a variable bit length integer, i.e. a bigint.
Absolutely not, he needs to compute (63 - x) / 7, where x is computed from a 64-bit integers. There are no bigints involved.
Re: Bitwise Division
#17Don’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.
It's about variable-length encodings, not variable length integers.
Re: Bitwise Division
#18Earlier quoted context omitted.
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.
It's about variable-length encodings , not variable length integers.
Yeah. The (63-nlz)/7 is part of a piece of code implementing an encoding. nlz is an int.
Re: Bitwise Division
#19> And it happens to be the case that 7 × 9 = 63, which is almost 64, a power of 2
While the article goes down a different rabbit hole, this also happens to be a neat example of (n-1)(n+1) = n² - 1, where n = 8.
Which is one of those things I haven't managed to find an actual use for but feels like it should have since you can use it with 0xFF (15 × 17), 0xFFFF (255 × 257), and so on.
Re: Bitwise Division
#20Very cool and it must have been really satisfying to have figured it out.