mpz_prevprime

[Seth Troisi]

I measure the regression as ~5-15% for input < ~10,000
I have a proposed patch which uses int, and trial div up to some threshold
this appears to be 5x faster.
The cut off point as I measure it is ~80,000,000 but requires increasing
the primegap_small list to ~1100 entries
I'm not sure what you think about a list of that length.

It might also be useful to commit tune_nextprime_small which dynamically
selects a higher reps count for
mpz_nextprime input and helps increase precision.


On Sat, Mar 21, 2020 at 7:18 AM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

> 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: Screenshot from 2020-03-22 00-42-59.png
Type: image/png
Size: 42629 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200322/884ae0b9/attachment-0003.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-22 00-57-54.png
Type: image/png
Size: 52523 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200322/884ae0b9/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-22 00-58-13.png
Type: image/png
Size: 45353 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200322/884ae0b9/attachment-0005.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: next_prime_small.patch
Type: text/x-patch
Size: 1961 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200322/884ae0b9/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tune_nextprime_small.patch
Type: text/x-patch
Size: 1363 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200322/884ae0b9/attachment-0003.bin>