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 <theh...@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 <brain...@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@gmplib.org > > https://gmplib.org/mailman/listinfo/gmp-devel > _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
