mpz_nextprime

[Hans L]

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