mpn_invert implementing ApproximateReciprocal.

bodrato at bodrato at
Tue Dec 15 19:52:44 CET 2009


> "Exact approximation" is a bit odd.  The value computed is an
> approximation (B^{2n}-1)/D, but is exactly floor((B^{2n}-1)/D).
> I.e. no approximation compared to the ideal value.

Does "Exact truncation" sound better?

>   The measured BINV_NEWTON_THRESHOLD is probably too high because of this.
> You're right.  Swapping the measurement order is also not right, as the
> code is written.  I don't see how to do this easily, unless we assume
> mpn_mul will never be relevant here.  I think I'll do that for now.
> For mpn_binvert's usage if mul vs mulmod_bmn1 I think we could actually
> use a more generally aiming parameter MUL_TO_MULMOD_BNM1_2NXN_THRESHOLD.
> (The sub_1 used in binvert will not matter.)  I'll leave that for later.

I guess MUL_TO_MULMOD_BNM1_2NXN_THRESHOLD will have a value similar to
On all machines running daily test we have

Probably mpn_binvert does not actually need a threshold for mulmod_bnm1.



More information about the gmp-devel mailing list