Fast integer division via calculating and storing inverses?

Question

From what I understand, the current method of doing integer division is calculating the inverse in hardware and then performing a multiplication.

I have some C# code where a ton of time is being spent in integer division, with values that are changed rarely enough that their values can be cached.

I want to perform the hardware algorithm in software, i.e. calculate the inverse of the divisors and turn all these divisions into multiplication. Does anyone know the algorithm to perform this transformation, or even better, is there something in the CLR that can perform this automatically?

Answer 1

There is an excellent blog post series on the topic of integer division by multiplication. It really contains everything that is needed to implement the transformation yourself.