using mpn_preinv_divrem_1

Ashod Nakashian saghmos at
Thu Sep 1 13:37:56 CEST 2005

Torbjorn Granlund wrote:
> Ashod Nakashian <saghmos at> writes:
>   I've been reading the mpf_div_ui() code and was surprised to find out 
>   that even though tune was enabling preinv division, the code was NOT 
>   using the mpn_preinv_divrem_1 function.
> It doesn't, since a precomputed value is not available.
> In mpn_get_str, the divisors are invariant, which allows us to
> table preinverted divisors.  That is what mpn_preinv_divrem_1 is
> designed for.
> In other cases, mpn_divrem_1 computes the inverse on-the-fly (for
> machines where that helps).


I understand that. What I was asking was why mpn_divrem_1 isn't 
precomputing the inverse on-the-fly? (That's the case in v4.1.4, as far 
as I can tell.) 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 is not the case currently as far as I can tell.

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.

If the math should be obvious, please forgive my ignorance, I'm no math wiz.


More information about the gmp-discuss mailing list