mpn_invert implementing ApproximateReciprocal.

[bodrato at mail.dm.unipi.it]

Ciao,

> "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
INV_MULMOD_BNM1_THRESHOLD.
On all machines running daily test we have
INV_MULMOD_BNM1_THRESHOLD < BINV_NEWTON_THRESHOLD.

Probably mpn_binvert does not actually need a threshold for mulmod_bnm1.

Regards,
Marco

-- 
http://bodrato.it/papers/