mpz_prevprime

Seth Troisi braintwo at gmail.com
Wed Aug 21 08:02:09 UTC 2019


There isn't the inverse function for mpz_nextprime which I needed for some
recent prime work so I coded one up.

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)

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.

Finally for mpz_prevprime(rop, op <= 2) it's not clear what rop should be
set to, so I use the smallest prime (2).

https://github.com/sethtroisi/libgmp/pull/10/files

Patches can be seen at
https://patch-diff.githubusercontent.com/raw/sethtroisi/libgmp/pull/6.diff
https://patch-diff.githubusercontent.com/raw/sethtroisi/libgmp/pull/10.diff

Thanks,
Seth


More information about the gmp-devel mailing list