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:
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.
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:
> 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.
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).
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.)
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...