thehans at gmail.com
Thu Sep 5 19:49:18 UTC 2019
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:
(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).
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
> 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
> next multiple of each prime. This avoids divisions, unfortunately it
> 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
> gmp-devel mailing list
> gmp-devel at gmplib.org
More information about the gmp-devel