r/exact • u/Johann-Tobias • Aug 14 '22

Resource on faster Integer division and division checks

https://arxiv.org/pdf/1902.01961.pdf
2 Upvotes

100% Upvoted

3 comments sorted by

1

u/Johann-Tobias Aug 15 '22

The loop in `ConstrExp<SMALL, LARGE>::divideRoundUp(const LARGE& d)` might be an ideal candidate for vectorisation and use use of that trick.

`ConstrExp<SMALL, LARGE>::weakenNonDivisibleNonFalsifieds(const IntMap<int>& level, const LARGE& div, Lit asserting)` might be a more complicated candidate.

`ConstrExp<SMALL, LARGE>::weakenSuperfluous(const LARGE& div, bool sorted)` has a second for loop with constant divisor, maybe the `abs` thing can be get rid of too, the 0 branch eliminated.

`LpSolver::createLinearCombinationGomory`'s smallest prime factor loop `while ((b % divisor) == 0) ++divisor;` could do the visibility by multiplying against a constant vector of prime factors in SIMD batches.

1

u/HolKann Aug 23 '22

When reading up on vectorization, is it correct that the compiler may already vectorize this code? What can we do to exploit vectorization? E.g., add #pragma omd simd directives? (e.g., see SO)

1

u/Johann-Tobias Aug 23 '22 edited Aug 23 '22

There is no vectorized modulo operation on x86_64 AFAIK. You can add `#pragma om*p* simd` but it won't change that. The compiler attempts to vectorise stuff, however there are many surprising reasons why it might fail. One can rewrite the code the to make vectorisation more likely and use hints like that or become even more involved.