mpz_nextprime

[Seth Troisi]

Hans,

I believe there's already a gmp_primesieve which is 20-30x faster than
mpz_nextprime for getting a list of primes

On Thu, Sep 5, 2019 at 12:49 PM Hans L <thehans at gmail.com> wrote:

> What are the axes in the chart of your original post?
>
> By the way, I wonder how commonly next_prime is used to generate a
> large sequence of straight consecutive primes, in which case I think
> it would be very beneficial to implement a segmented sieve that keeps
> some state between calls, having the successive primes already sieved
> and queued up after the first call etc.  Probably would make the most
> sense a new/separate interface designed explicitly for that case.
>
> Because a segmented sieve would be 1000's of times faster (for single
> limbs sizes at least).  See the application "primesieve" (
> https://github.com/kimwalisch/primesieve ) for an example of a very
> efficient sieve algorithm that works up to 2^64.
> Even the simplified example implementation as part of primesieve's
> docs is quite fast:
>
> https://github.com/kimwalisch/primesieve/wiki/Segmented-sieve-of-Eratosthenes
> (eg. primes up to 1e9 in 0.65s)
>
> As a rough comparison I ran mpz_nextprime consecutively up to 1e9 and
> it took a total of 16m22.553s (on a Ryzen 2700x @4.0GHz).
>
> Hans
>
> On Tue, Sep 3, 2019 at 6:41 PM Seth Troisi <braintwo at gmail.com> wrote:
> >
> > I think this small cleanup patch is appropriate given the testing of the
> > other
> > patch which I've tried several variations of and have been unable to
> improve
> > beyond the existing implementation.
> >
> > The idea is to try and avoid performing modulo by storing the distance to
> > the
> > next multiple of each prime. This avoids divisions, unfortunately it
> > requires
> > writing back to the table each time a multiple is passed.
> >
> > I'm happy to look at other ideas but I think these comments can be
> cleaned
> > up.
> > _______________________________________________
> > gmp-devel mailing list
> > gmp-devel at gmplib.org
> > https://gmplib.org/mailman/listinfo/gmp-devel
>