sec_invert performance

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> All linear-time functions really take Bn+C time, and quadratic-time
> functions take An²+Bn+C, of course.  If the sec_invert function has
> small B and/or C while gcdext has larger B and/or C, then the observed
> pattern seem even more reasonable.  Do you agree?

Not sure. I had expected the quadratic terms to dominate (and hence the
ratio almost converging to the ratio between the n^2 coefficients), well
before we cross the GCDEXT_DC_THRESHOLD which is on the order of 500
limbs.

But I haven't had any deep thoughts about it. (I guess one could also
try to estimate all of A, B and C from the measurements. Putting such
numerics into speed is something I'd like to do sometime).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.