patch for speed
nisse at lysator.liu.se
Tue Sep 10 15:42:04 UTC 2019
paul zimmermann <Paul.Zimmermann at inria.fr> writes:
>> Wouldn't that patch call mpz_legendre (a, p) with p not prime? Which is
>> invalid, but kind-of works *because* mpz_legendre is an alias for
> good point. Do you want a new patch which ensures p is an odd positive prime?
I'd like to understand the benefits of ./speed mpz_legendre first, since
I don't really see any. Currently, it's an alias for mpz_jacobi, and I'm
not aware of any concrete plans to change that.
One could consider computing the legendre symbol with modular
exponentiation, which is asymptotically slower but potentially faster
for some smallish sizes. But at the moment, mpz_powm is at best 7 times
slower than mpz_jacobi, for size n = 3, when I try it on my closest
$ ./tune/speed -c -s 1-10 -r mpz_jacobi mpz_powm
overhead 4.68 cycles, precision 10000 units of 1.13e-09 secs, CPU freq
1 #699.45 14.8460
2 #1481.50 11.8880
3 #4512.19 7.1814
4 #6352.69 9.1231
5 #8173.88 9.3008
6 #10050.12 8.9304
7 #11914.19 9.1968
8 #13811.12 10.1785
9 #15741.36 11.3230
10 #17467.37 12.0439
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel