mpz_prevprime
Niels Möller
nisse at lysator.liu.se
Thu Aug 22 05:24:42 UTC 2019
Seth Troisi <braintwo at gmail.com> writes:
> In order to profile parts of this I also added tune/speed support for
> mpz_nextprime
> https://github.com/sethtroisi/libgmp/pull/6/files
> Note that I change the behavior of s->size to mean size bits instead
> of limbs for for measuring mpz_nextprime, as the function is slow (in the
> worstcase it can take >5 second for a 1500 bit input, and >90 seconds for a
> ~2700 bit input)
Good. I imagine mpz_nextprime performance has some room for improvement.
For benchmarking, maybe one should use something other than arithmetic
mean for averaging, since some numbers will be much slower than others?
> For implementing mpz_prevprime, I tried to reuse as much code as possible
> with a macro for the function body, I'm not sure how readable it ended up.
> it also possible this could be speed up if I used separate code for each of
> the functions, by calculating the negative modulo and using unsigned
> integers everywhere. I'm open to hearing how folks thinks code could be
> better reused / structured.
Maybe it would make sense to generalize a bit further, and write a
function to find the first prime (if any) in an arithmetic sequence.
I.e., find the smallest k >= such that A + kB is prime (if any). A
corresponds the current input to mpz_nextprime, and B could be either a
signed long or a bignum.
Implementation strategy would be roughly the same: Consider the
sequences A + kB (mod p) for some list of small primes, and find first k
so that they all are non-zero, then do a heavier primality test (or a
compositeness test, if we want to make that distinction). One would also
need some initial checks to identify inputs for which there is no such
prime.
> Finally for mpz_prevprime(rop, op <= 2) it's not clear what rop should be
> set to, so I use the smallest prime (2).
I'd prefer using the function return value to indicate success/failure.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list