Menu
I am working on GPU device which has very high division integer latency, several hundred cycles. I am looking to optimize divisions.
All divisions by denominator which is in a set { 1,3,6,10 }, however numerator is a runtime positive value, roughly 32000 or less. due to memory constraints, lookup table may not be a good option.
Can you think of alternatives? I have thought of computing float point inverses, and using those to multiply numerator.
Thanks
PS. thank you people. bit shift hack is a really cool. to recover from roundoff, I use following C segment:
// q = m/n
q += (n*(j +1)-1) < m;
822
libdivide allows you to replace expensive integer divides with comparatively cheap multiplication and bitshifts. Compilers usually do this, but only when the divisor is known at compile time. libdivide allows you to take advantage of it at runtime. The result is that integer division can become faster - a lot faster.
On current processors, integer division is slow. If you need to compute many quotients or remainders, you can be in trouble. You potentially need divisions when programming a circular buffer, a hash table, generating random numbers, shuffling data randomly, sampling from a set, and so forth.
In integer division and modulus, the dividend is divided by the divisor into an integer quotient and a remainder. The integer quotient operation is referred to as integer division, and the integer remainder operation is the modulus.
The truncating division operator (also known as floor division) truncates the result to an integer and works with both integers and floating-point numbers. As of this writing, the true division operator (/) also truncates the result to an integer if the operands are integers. Therefore, 7/4 is 1, not 1.75.
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.
200
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:
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
