about prime number generation

[Marco Bodrato]

Il 2022-05-01 17:01 Marco Bodrato ha scritto:
> Il 2022-04-30 23:39 Seth Troisi ha scritto:
>> next_prime took up all of my energy
> 
> We should further improve that work!
> 
> With your improvements to nextprime, it's really a waste of resources
> if ones have to write
>   for (int i = 0; i < delta2; i++)
>     mpz_nextprime(p, p);
> because every sieved range is used just once, instead of scanning it to 
> the end.
> 
> I mean, we should add a couple of (public or not?) functions:
>  mpz_nth_{prec,next}prime

I wrote a simple mpz_nth_nextprime, and here are some timings:

$ build/tune/speed -p100000000 -rs 10-60 -t5 mpz_nextprime 
mpz_nth_nextprime.2 mpz_nth_nextprime.4 mpz_nth_nextprime.16 
mpz_nth_nextprime.256
overhead 0.000000007 secs, precision 100000000 units of 8.56e-10 secs, 
CPU freq 1167.94 MHz
    mpz_nextprime nth_nxtprim.2 nth_nxtprim.4 nth_nxtprm.16 nth_nxtp.256
10  #0.000001141        2.4384        6.1353       42.1803   4318.7026
15  #0.000002587        2.0795        4.4340       23.0275   1946.8527
20  #0.000025472        1.8204        3.4797       13.7392    237.0212
25  #0.000032677        1.8830        3.6122       14.1018    225.8131
30  #0.000040690        1.8905        3.6741       14.3550    230.1069
35  #0.000053511        1.8285        3.5060       13.4946    215.2175
40  #0.000060637        1.8421        3.5508       13.6446    217.1993
45  #0.000070047        1.8280        3.4869       13.5221    217.8561
50  #0.000078157        1.8100        3.5152       13.6302    216.4944
55  #0.000094682        1.9049        3.6773       14.4213    231.4945
60  #0.000106016        1.8642        3.5877       14.0455    231.0008

This means that, the 256th next prime of a large enough number (more 
than 20 bits) is found faster than using _nextprime 256 times.
For smaller numbers this is not evident, for two reasons: current code 
use different strategies for numbers smaller than 20 bits, and the 256th 
next prime of a 10bit number is a 12bit prime, i.e. a much larger 
number.

But I realize that this is not a clever approach.
My code actually finds all the primes and skips them, but this is not 
very useful. The need to have a way to loop on primes emerges again.

Ĝis,
m