update on mulmid-based inversion

bodrato at mail.dm.unipi.it bodrato at mail.dm.unipi.it
Sat Jan 9 11:45:00 CET 2010


> 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_
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

With this kind of integration I'd expect two effects.
- on one side I'd expect to have an MP_TO_NI_THRESHOLD smaller than 2000.
- on the other side I'd expect to see a measurable speed-up, thanks to _mp
integration, far above 2000 limbs.
I.e. the range of direct applicability will be smaller, but the range with
a consistent speed-up will be wider.



More information about the gmp-devel mailing list