On Mon, Mar 9, 2020 at 2:05 AM Marco Bodrato <bodr...@mail.dm.unipi.it> wrote:
> Ciao, > > Il 2020-03-09 02:56 Seth Troisi ha scritto: > > From Marco Bodrato's analysis I got inspired and modified nextprime to > > Your analysis is much deeper than mine :-) > I do not have much time now... but I glanced at the code and write here > a few comments. > Thanks for the comments, I'll improve the code with these in mind. > > You can see some of my thresholds and testing input in this google > > sheet[1]. The end result is sieve up ~ LOG2(N) ^ (20/7) / 3268 > > Funny numbers :-) > In the code, you compute LOG2(N) ^ (20/7) / 3268. (A comment says "/ > 1880") I updated the comment and tweaked the constant again > Then, if the result is greater than 430000000, you cut it. > Cutting seems a good idea, but I'd do the reverse: > if nbits is larger than (430000000*3268) ^ (7/20) = 17940, set limit to > 430000000, > compute otherwise. Happy to do it this way. > > > For 10,000 bit numbers this sieves up to 80 million (which takes ~4 > > seconds but reduces nextprime from ~300seconds to ~200 seconds) > > Seems interesting :-) > > > I cleaned up the code without any of the debug printing in the 3rd > > patch nextprime_sieve_clean.patch which I'd love people to consider > > Some random comments: > > If you use TMP_DECL, then you don't need to use also TMP_SDECL. > The same for TMP_MARK and TMP_SMARK; or TMP_FREE and TMP_SFREE. > Thanks > > I'm happy to see that you used gmp_primesieve and the macros for it, > but... > ... maybe that code is too messy? I mean, my code with the > LOOP_ON_SIEVE_ macros... > You did not use that sieve to directly loop on primes, but you used it > to loop on primes for building a primegap table, and then use that table > to loop on primes... It's highly possible I misunderstand how these macros are supposed to be used. I also dislike the boiler plate of the macros but I didn't like handrolling my own sieve or sacrificing a huge amount of speed by using gmp_nextprime (~8x slower). I don't understand "I mean, my code with the LOOP_ON_SIEVE_ macros..." If you have suggestions or code pointers for a better pattern I'd appreciate that. Did you try to use the gmp_primesieve function directly? > I'm not sure what you're referencing here, I tried with gmp_primesieve_t ps; gmp_init_primesieve (&ps); prime = gmp_nextprime (&ps); but it was ~8x slower If sieve_limit = 430000000, you are allocating 17M for mp_limb_t *sieve, > then another 22M for primegap_tmp, and both are kept in memory. > I believe that looping with primegap is faster, but... how many times do > we need too loop, on average? I mean, how often is the /*Sieve next > segment*/ code used? > next_mult is also in memory so another 88 MB, I didn't think ~100M of RAM in the worst case was very much. If that's an issue we can always reduce the max sieve_limit to 200M or 100M and reduce max memory. Is there a way to unalloc a TMP_ALLOC_LIMBS before TMP_FREE? Sieve next segment is rare, the average gap is ln(n), if INCR_LIMIT was changed to be a variable it could be set so /*sieve next segment*/ happened on average less than once, and then the primegap array could be removed as you're correct in guessing it's not the slow part. > In the array char *sieve, you use only the even entries. Maybe you can > reduce its size by half, and remove some "*2" around the code? > it's only 4000 entries so I wasn't bothering at this time, but it would be easy to change. Ĝis, > m > Thanks for the comments, they have given me more energy to work on this. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
