Torbjorn Granlund <t...@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. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel