Skip to content

Instantly share code, notes, and snippets.

@micycle1
Created December 27, 2022 13:34
Show Gist options
  • Save micycle1/3694f5a3a94be8a9532e64a4c601695b to your computer and use it in GitHub Desktop.
Save micycle1/3694f5a3a94be8a9532e64a4c601695b to your computer and use it in GitHub Desktop.
Java fast fixed-divisor integer division.
/**
* Computes a pair of magic numbers used to optimise integer division by a fixed
* divisor <code>d</code>.
* <p>
* The function is given the maximum value of the dividend <code>nmax</code> and
* the divisor <code>d</code>. It returns a pair of integers: the magic number
* <code>m</code> and a shift amount <code>p</code>.
* <p>
* To divide a dividend x by d, one multiplies x by m and then shifts the (full
* length) product right p bits: <code>x / d === ((x * m) >> p)</code>.
* <p>
* Described in 'Hacker's Delight' (chpt. 10).
* <p>
* x % d can be computed from z = (x * m) >> p with:
* <code>x % d === x - z * d</code>.
*
* @param nmax maximum value (dividend) that will be divided
* @param d constant for divisor value
* @return [m, p]
*/
private int[] magicDivision(final int nmax, final int d) {
final int nc = (nmax / d) * d - 1;
final int nbits = (FastMath.log2(nmax)) + 1;
int m = 0;
int p = 0;
for (; p < 2 * nbits + 1; p++) {
final int p2 = (int) FastMath.twoPow(p);
final int z = (d - 1 - (p2 - 1) % d);
if (p2 > nc * z) {
m = (p2 + z) / d;
}
}
return new int[] { m, p - 1 };
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment