about prime number generation
Marco Bodrato
bodrato at mail.dm.unipi.it
Sun May 1 17:01:38 CEST 2022
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
More information about the gmp-devel
mailing list