using mpn_preinv_divrem_1

[Torbjorn Granlund]

Ashod Nakashian <saghmos at xter.net> writes:

  I understand that. What I was asking was why mpn_divrem_1 isn't 
  precomputing the inverse on-the-fly?

It sure does, look at the code, in mpn/generic/divrem_1.c.
DIVREM_1_NORM_THRESHOLD and DIVREM_1_UNNORM_THRESHOLD
controls this.

  Precomputing the inverse should pay off for a few limb's 
  long numbers and more, assuming a (mul + overhead) is faster on the 
  target CPU than a plain div.
  
That's the experience of the GMP hackers.

  Now, I'm willing to experiment with this on my AMD-64 3200+ to see how 
  far I can get. But my next question is how do you compute the inverse of 
  the divisor? As I stated in my previous mail, the traditional method, as 
  I understand it, doesn't work. There is some assumption that I'm missing.
  
All details are in the paper "Division by Invariant Integers using
Multiplication", <http://swox.com/~tege/divcnst-pldi94.pdf>.  I
think the source code for invert_limb might also give you a hint.

--
Torbjörn