I'm confused by the pretty bad performance of sec_invert. Try e.g.,
./tune/speed -s 1-200 -P invert mpn_gcdext mpn_sec_invert mpz_powm_sec
Say we have inputs of n bits. Then my understadning of these algorithms
is:
* mpn_gcdext, for sizes of interest, is Lehmer's algorithm, O(n^2), with
a
ni...@lysator.liu.se (Niels Möller) writes:
Any idea what's going on?
I quick guess is that the exponent is fixed for powm, not a function of
the input size.
___
gmp-devel mailing list
gmp-devel@gmplib.org
Torbjorn Granlund t...@gmplib.org writes:
I quick guess is that the exponent is fixed for powm, not a function of
the input size.
Ah, its hardcoded to always use 6 limbs. If I change it to use the same
size as b and m, results are a bit different:
$ ./speed -s 1-64 -c -r mpn_gcdext
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
