update on mulmid-based inversion

[David Harvey]

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