Faster integer division when denominator is known?

a/b=a*(1/b)
x=(1<<16)/b
a/b=(a*x)>>16

can you build a lookup table for the denominators? since you said 15 bit numerators, you could use 17 for the shifts if everything is unsigned 32 bit:

a/b=a*((1<<17)/b)>>17

The larger the shift the less the rounding error. You can do a brute force check to see how many times, if any, this is actually wrong.

The standard embedded systems hack for this is to convert an integer division by N into a fixed-point multiplication by 1/N.

Assuming 16 bits, 0.33333 can be represented as 21845 (decimal). Multiply, giving a 32-bit integer product, and shift down 16 bits.

You will almost certainly encounter some roundoff (truncation) error. This may or may not be something you can live with.

It MIGHT be worthwhile to look hard at your GPU and see if you can hand-code a faster integer division routine, taking advantage of your knowledge of the restricted range of the numerator.

The book, "Hacker's Delight" by Henry Warren, has a whole chapter devoted to integer division by constants, including techniques that transform an integer division to a multiply/shift/add series of operations.

This page calculates the magic numbers for the multiply/shift/add operations:

• http://www.hackersdelight.org/magic.htm