Implementing a pi(n) sieve in gmp.
amenezes007 at gmail.com
Wed Apr 15 09:28:44 UTC 2015
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?
On Mon, Apr 6, 2015 at 4:31 AM, Allan Menezes <amenezes007 at gmail.com> 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