mpz_prevprime

[Marco Bodrato]

Il 2020-03-21 11:42 Seth Troisi ha scritto:
> I see this was pushed, with a few more polishing tweaks.

Yes, but there are bad news, it introduces a speed regression for small 
numbers.

> I see you also added more testing in tests/devel/primes.c which is a
> great triple check.
> It looks like the usage on line 21-28 / 399 wasn't updated.

Not yet updated, you are right.

I also added a target for tune/speed.

tune/speed -s<num> mpz_nextprime_1.<r>
measure the time needed to compute the first <r> primes larger than 
<num>, and divides by <r>.

If on my environment I try
$ tune/speed -s1-4000 -t2 mpz_nextprime_1.16
before, and after the patch, I see that nextprime on small numbers is 
now slower.

Before introducing new functions, may I suggest to try to speed up the 
function also for small numbers?

You measured how much it is worth sieving before using the Miller-Rabin 
(actually BPSW) test. But for really small numbers, the sieve alone can 
be enough and the expensive test can be totally skipped.

I attach a possible patch for this purpose.

Ĝis,
m
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nextprime_smallval.diff
Type: text/x-diff
Size: 1971 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200321/bb3b1597/attachment.bin>