Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bitwise Division

h14s.p5r.org

Post reply on HN
Print view View original

71–75 of 75 posts

Re: Bitwise Division

#71

Post by vanderZwan »

cornholio wrote: post #70
vanderZwan wrote: post #51

Earlier quoted context omitted.

The method in the blog post uses two bit shifts and two additions. I don't really see how to beat that with this. You can fit twenty-one 3-bit entries in a 64 bit int, with one bit to spare. So naively you get: table[nlz / 21] >> (nlz % 21) Which involves a division and a modulo. And that's assuming 63 entries in total, I'm not even trying to handle fitting the 64th entry in those three leftover bits somehow, or spre…

> ((table[0] >> nlz) > nlz) > nlz) > Which is five shifts and two additions, so more work plus lookup. Something like that, perhaps with more bitmasking and less addition. There is no lookup, just three constants loaded into different registers and handled by different out of order execution units, then combined in a final addition / or-ing. So what you will "see" on the critical path is two bitshifts and three bitwi…

Ah, right, I forgot the &1 masks. And I guess that with three literals and OOOE it might be faster, yes.

But yes, extremely unlikely to be a hot path in most situations.

Re: Bitwise Division

#72

Post by kjs3 »

roger10-4 wrote: post #12

Horner’s method [0] is also commonly used on small microcontrollers without divide (or multiply) instructions. [0] https://www.ti.com/lit/an/slaa329a/slaa329a.pdf

Look out. Any time someone brings up microcontroller multiply, there's a someone who is compelled to chime in with "Well I've never needed to multiply on a microcontroller, so why do you need to!".

Re: Bitwise Division

#73

Post by smallpipe »

cryptonector wrote: post #47
resource0x wrote: post #31

Earlier quoted context omitted.

Maybe nicer, but slower. And I'm not even sure about the former.

Lookup tables can be slower. Do not assume that memory is fast. Even if the table is small and fits in cache, it will still be displacing other useful things from the cache. If you can have a small sequence of fast instructions using only registers and no branches, that's very likely to be faster -if not much faster- than lookup tables. Just one L1 cache miss could take much longer to resolve than computing this part…

The example is literally one cache line, which probably won't affect the rest of the program too much. But given the average L1 throughput, I'd bet the bitwise version is faster

Re: Bitwise Division

#74

Post by jameshart »

dahart wrote: post #56
jameshart wrote: post #48

Earlier quoted context omitted.

But that requires turning ‘multiplication by a constant’ into a bitwise trick in exactly the same way that this is doing for division by a constant (albeit without the fuzziness about rounding).

Why’s that?

Because ‘multiplication by n’ requires some sort of iterative process. Or, at least, multiplying by a k-bit number requires cascading through k repeats of a word-level bitwise operation (a shift, an add, an AND, etc)

Which is precisely the kind of process that we’re trying to come up with a shortcut to avoid in the case of this division we’re trying to produce.

Whereas multiplying by a specific number can be reduced to a concrete, limited number of shifts and adds, like this process is deriving for a specific division.

Re: Bitwise Division

#75

Post by dahart »

jameshart wrote: post #74
dahart wrote: post #56

Earlier quoted context omitted.

Why’s that?

Because ‘multiplication by n’ requires some sort of iterative process. Or, at least, multiplying by a k-bit number requires cascading through k repeats of a word-level bitwise operation (a shift, an add, an AND, etc) Which is precisely the kind of process that we’re trying to come up with a shortcut to avoid in the case of this division we’re trying to produce. Whereas multiplying by a specific number can be reduced…

So? Why are you assuming you have to carry the bitwise operation through the multiplication? You don’t have to. You can if you want, but it would be academic and impractical. Using a multiply inside of the bitwise div operation makes the divide much faster. Deconstructing a multiply into bitwise operations makes the multiply much slower, so there’s no reason to do that, and there is no such requirement that we do before we can call the div trick a bitwise algorithm.

That said, if you want a bitwise multiply algorithm, I have written one. It’s slow, but enables 64 and 128 bit multiplies in glsl, which has no 64 or 128 bit multiply or add intrinsic. See add() and mult() in the “common” buffer. https://www.shadertoy.com/view/7dfyRM

Post reply on HN