mpz_prevprime

[Marco Bodrato]

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