Re: 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 -p1 -rs 10-60 -t5 mpz_nextprime 
mpz_nth_nextprime.2 mpz_nth_nextprime.4 mpz_nth_nextprime.16 
mpz_nth_nextprime.256
overhead 0.7 secs, precision 1 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.011412.43846.1353   42.1803   4318.7026
15  #0.025872.07954.4340   23.0275   1946.8527
20  #0.254721.82043.4797   13.7392237.0212
25  #0.326771.88303.6122   14.1018225.8131
30  #0.406901.89053.6741   14.3550230.1069
35  #0.535111.82853.5060   13.4946215.2175
40  #0.606371.84213.5508   13.6446217.1993
45  #0.700471.82803.4869   13.5221217.8561
50  #0.781571.81003.5152   13.6302216.4944
55  #0.946821.90493.6773   14.4213231.4945
60  #0.0001060161.86423.5877   14.0455231.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
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: about prime number generation

[Marco Bodrato]

Ciao Seth,

Il 2022-04-30 23:39 Seth Troisi ha scritto:

I worked on nth_prime(n) in a series of patches three years ago


That code was very interesting.
It would be nice to get rid of the double type and the function log(). 
The library is not using math.h and libm anywhere now. But it doesn't 
seem simple, at least for me.


We should start pushing a primepi(N) function, counting the primes 
between 1 and N.

I have a function, which is almost ready, with the following prototype:
long gmp_pi_ui (unsigned long n)

But to have a function that really belongs to GMP, we should extend it 
to at least mpz_pi (mpz_t n) ... With a reasonable return type ...



Sadly this never made it upstream as the review process for a faster
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


In practice I'd recommend you also take a look at the
highly optimized code from kimwalisch
https://github.com/kimwalisch/primecount


Of course a specialized library will remain faster than some small piece 
of code in GMP...


Ĝis,
m
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel