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.
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")
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.
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.
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...
Did you try to use the gmp_primesieve function directly?
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?
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?
Ĝis,
m
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
