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