Faster remainders when the divisor is a constant: beating compilers & libdivide
For this equation:<p><pre><code>    n/d = n * (2^N/d) / (2^N)
</code></pre>
What is "N"? They didn't seem to explain that, although they say "Yet for N large enough", and "drop the least significant N bits". Is it just a very large integer? Or maybe the maximum integer for a certain number of bytes?<p>EDIT: I'm reading this Wikipedia article: <a href="https://en.wikipedia.org/wiki/Division_algorithm#Division_by_a_constant" rel="nofollow">https://en.wikipedia.org/wiki/Division_algorithm#Division_by...</a><p>For a 32-bit unsigned integer, you would use N = 33 when dividing by 3? And N = 35 when dividing by 10? I'm struggling to see how this works.<p>EDIT 2: I think this post helped me understand it: <a href="https://forums.parallax.com/discussion/114807/fast-faster-fastest-code-integer-division" rel="nofollow">https://forums.parallax.com/discussion/114807/fast-faster-fa...</a><p>"The·basic idea is to approximate the ratio (1/constant) by another rational number (numerator/denominator) with a power of two as the denominator."<p>Their example:<p><pre><code>    (n/10) = (n*205) >> 11
</code></pre>
Maps to the original example:<p><pre><code>    n/10 = n * (2^11 / 10) / (2^11)
</code></pre>
2^11 / 10 = 2048 / 10 = 204.8, which rounds to 205.<p>So N would be 11 in this example, but I guess it could be any value.