nisse at lysator.liu.se
Tue Feb 4 20:48:48 UTC 2014
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
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).
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel