Implementing a pi(n) sieve in gmp.

Allan Menezes amenezes007 at
Wed Apr 15 09:28:44 UTC 2015

Dear GMP-Developers,
   GCC version 5.1 should available for download soon and it contains
support for OPENACC which parallelizes C code with switches to the compiler
in NVIDIA CUDA or OPENMP or Intel PHI aceelators.
So for version > 6.0.0a can you include a makefile with the -fopenacc
switces for NVIDIA GPUs for the generic C GMP code? So one can have a GMP
library that is optimized for CUDA as well as OPENMP?
Thank you,
Best wishes,
Allan Menezes

On Mon, Apr 6, 2015 at 4:31 AM, Allan Menezes <amenezes007 at> wrote:

> Dear All,
>  One can implement a sieve that calculates pi(n) and the n'th prime Pn and
> instant primality check
> for small bit strings p[] as follows:
> Calculate and implement the following  primes and composites bit string
> p[] upto a convenient large n starrting from 2 as such storing the m'th bit
> as a 1 if m is prime and 0 otherwise.
> Store this string upto n bits as a mpz_t ropp.
> Now for all numbers below n primality of m <=n is determine the return
> value of mpz_tstbit(mpz_t ropp, m);
> For pi(x) x<=n; pi(x)=mpz_popcount(mpz_t ropp,x);
> To determine Pm we need more complexity
> Pm ~ m ln(m)+/-Delta;
> Determine x=m ln(m) - epsilon for a small integer values of epsilon, Delta.
> Iterate k=mpz_scan1(mpz_t ropp,x + eps1)
> till we get m for the return value m of mpz_popcount(mpz_t ropp,x+esp0);
> This can be implemented in many ways but creating built in functions in
> GMP and implementing
> the last iterative method as a binary search to find m from mln(m)-Delta
> would be good.
> Thank you,
> Thanks for a very fast and excellent Multiple precision library GMP.
> We are all in debt to you over the years.
> Best wishes,
> Allan Menezes
> PS It would be nice if mpz_popcount and mpz_scan1 and mpz_scan0 were
> implemented to return
> as a var to the functions in mpz_t for large p[] bit strings.
> It would be nice all bit fiddling mpz instructions returned their values
> as mpz_t except for those
> functions that return bit values or always small integer values.

More information about the gmp-discuss mailing list