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
