Hacker News new | ask | show | jobs
by dahart 1204 days ago
Naw, it’s standard to call such tricks “bitwise” even when including a multiply. Remember you’re multiplying into a specific bit range and then shifting down (dividing by a power of 2) to capture the bits you want, it’s bitwise in a very literal sense. Probably quite fair to call any expression “bitwise” if any single operation in the expression is bitwise, regardless of the other operators & functions, no? What part is hand-wavy? Variations of this technique are in standard widespread usage in the compilers we use.
1 comments
jameshart 1204 days ago
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).
link
dahart 1204 days ago
Why’s that?
link
jameshart 1202 days ago
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.

link
dahart 1202 days ago
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

link