update on mulmid-based inversion
David Harvey
dmharvey at cims.nyu.edu
Sat Jan 9 14:40:53 CET 2010
On Jan 9, 2010, at 5:45 AM, bodrato at mail.dm.unipi.it wrote:
> Ciao,
>
>> I updated my mulmid-based inversion code for GMP 5, using the new
>> mpn_invertappr for the base case. Results are still looking good.
>> Table below shows cycles for inversion for 6 <= n <= 5000 on K8.
>> Summary: new code starts to win at around n = 20, it's roughly 10-15%
>> faster than mpn_invertappr up to about n = 2000, then falls behind
>> again. I'll post the code on my website soon.
>
> The best should be, I think, to integrate mulmid-based inversion
> _inside_
> invertappr.
> There are currently two functions: mpn_bc_invertappr, and
> mpn_ni_invertappr (base case, and Newton iteration, respectively). It
> would be great to insert a third one in between: mpn_mp_invertappr, if
> possible.
I agree. The MP algorithm and newton algorithm are actually very
similar; the main difference is how to compute the middle portion of
T = A X_h (notation as in algorithm "ApproximateReciprocal", Modern
Computer Arithmetic version 0.4, Brent + Zimmermann). Actually I
often think of the MP algorithm as a form of newton iteration.
It might even be that the wraparound multiplication should be
incorporated into mulmid! i.e. invertappr should always use
mpn_mulmid, but the latter would use wraparound multiplication to
implement the middle product for sufficiently large input.
Also, both algorithms would benefit from a better mulhi.
david
More information about the gmp-devel
mailing list