undefined | Better HN

0 pointsdahart3y ago0 comments

Why’s that?

0 comments

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.

dahartOP3y 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

j / k navigate · click thread line to collapse

0 comments

jameshart3y ago

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.

dahartOP3y ago

j / k navigate · click thread line to collapse