Hacker News Reader

Comment by Iulioh | Hacker News Reader

Can you explain what do you mean with:

>It's worth noting that you can generally divide much faster if you know the divisor ahead of time

Division is just multiplication with 1/x so i don't understand

For flooring integer division with a bounded dividend and known constant, the idea is to multiply by a scaled reciprocal. For example with 32 bit division by 3, you might precompute 2^32 / 3, multiply by that, and then flooring-divide by 2*32 (right shift).

It gets tricky because 2^32/3 is not an integer, so you must round it. This introduces error; the idea is to show that the error is wiped out by the flooring divide. I did the monster math here:

https://ridiculousfish.com/blog/posts/labor-of-division-epis...

Exactly. If you know you’re going to later be dividing by 23.7, you can precompute 1/23.7 and store that as a constant. Then you can later multiply by it.

Yes but 1/x is just another division, so it only helps to speed up the final division of you're able to calculate 1/x beforehand.

For integer division, you may find that rounding is not identical after multiplying by the reciprocal.

Doesn't the risk of lack of precision apply to both floating point and fixed-point? I'd think the reciprocal would need to be exactly represented in the type, or to have more bits than the original type to produce a correct result in the last bit (or two bits?).

Also, with integers, a signed right shift is rounding down (towards negative infinity), whereas the division operator/instruction in many languages/hardware is rounding towards 0.

To adjust the rounding, you'd add the sign-bit to the first fractional bit before shifting the last step. Let's say that 'x' is a signed long, and a signed long has 64 bits, then:

result = ((x >> amount-1) + ((unsigned long)x >> 63)) >> 1;

> Doesn't the risk of lack of precision apply to both floating point and fixed-point? I'd think the reciprocal would need to be exactly represented in the type, or to have more bits than the original type to produce a correct result in the last bit (or two bits?).

Yes, but this was historically okay on an x87 FPU which had more precise representation than the common external formats.

He is talking about the fact that compilers can turn division by a constant into multiplications and bit shifts which are much faster.

Here's an example: https://godbolt.org/z/8vG637fb5

It compiles x/6 to some mad multiplication, bitshift and add.

How do you calculate 1/x without using division?

Not being snarky, at the simplest level by knowing x ahead of time you can change your code from y = n/2 into y = n * 0.5. Not wildly important by itself, but in a loop - maybe… I suspect compilers optimize for that already.

I still don't get it. How do you know that 1/x = 0.abc... without performing the division? I mean in general case, not in something matching binary tricks. Such as 1/3 for example. Unless you mean you somehow know the value of 1/x ahead of time. But where does it come from?

If you know the divisor x ahead of time you can pre-compute 1/x at compile time, so that your actual compiled code never does the division--only your compiler does. Your actual compiled code just does the multiplication by a pre-computed constant (and the compiled code doesn't have to know that that constant was pre-computed as the reciprocal of x).

Ah, thanks for clarifying.

Often, you can amortize a division or reciprocal by calculating it once and then reusing it. Frequently the divisor is dynamic, but reused locally.

For example, if you want to normalize a 3D vector you could do:

    mag = sqrt(x*x + y*y + z*z)
    x /= mag
    y /= mag
    z /= mag

That's three divisions with the same divisor. But you could instead do:

    invMag = 1.0 / sqrt(x*x + y*y + z*z)
    x *= invMag
    y *= invMag
    z *= invMag

There's still a single division (or reciprocal) done here. But you've eliminated at least the other two. (And it's even better if you have an rsqrt function.)

so basically just precompute all the answers you will need and then just look up the values later?

There’s no lookup needed if the value is constant

Reply on news.ycombinator.com