Re: How to perform integer div with SIMD?

T.Kaz. wrote:
Hi,

is there a way to make use of MMX/SSE to do calculations like 'a mod b'
where 'a' and 'b' are integers?

I haven't found any useful instruction for such a task. Maybe this can be
done using floating point arithmetic. If yes - how?

Yes, it can:

First, use the approximate reciprocal lookup to generate a set of starting values, then one or two NR iterations (also in SIMD fp mode) to get a more precise value.

Do the divisions in SIMD fp by multiplication by the reciprocal, then do a parallel convert of these approximate/fp results to int.

Finally, you should multiply each of these results (which will either be correct or maximum one off) by the original divisors, subtract, and check the remainders:

If negative (assuming all values positive to start with), subtract one from the result, add divisor to remainder.

If >= divisor, add one to result, subtract divisor from remainder.

Both of these can of course also be done easily on SIMD values with parallel compares (which generate 0 or -1 masks), then using the mask to adjust the result, PAND in the divisor, and adjust the remainder!

This will give you both division result and remainder at the same time, and it should be significantly faster than a single integer MOD operation.

OK?

Terje
--
- <Terje.Mathisen@xxxxxxxxxxxxx>
"almost all programming can be viewed as an exercise in caching"

.

Relevant Pages

  • Re: Dividing 512 bit number by 128 bit number in C program
    ... calculating the quotient and the remainder before returning. ... In one of the inner loops, the divisor is positioned so that its most ... A bit-wise subtraction of divisor from dividend is performed ... bool borrow = false; ...
    (sci.crypt)
  • Re: Sign conventions for remainder
    ... What about if both the divisor and the dividend are negative? ... > If the divisor is positive, the remainder should still be in the range ... options in your package for the several possible sensible behaviours. ...
    (sci.math)
  • Re: fixed point division in 32 bits
    ... i got some clue from a code posted by you. ... uint64_t remainder; ... uint64_t divisor; ... is your input data limited in magnitude? ...
    (comp.dsp)
  • Re: division algorithm
    ... implement a shift and subtract loop, ... use the divide instruction to generate a trial divisor, ...
    (comp.programming)
  • Re: sin/sind
    ... > subtract off the nearest integer and take the sin of the remainder, ...
    (comp.lang.fortran)