using mpn_preinv_divrem_1
Ashod Nakashian
saghmos at xter.net
Thu Sep 1 13:37:56 CEST 2005
Torbjorn Granlund wrote:
> Ashod Nakashian <saghmos at xter.net> 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).
>
Torbjorn,
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.
Thanks,
Ash
More information about the gmp-discuss
mailing list