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
