mpz_prevprime

[Marco Bodrato]

Ciao,

Il 2020-03-15 00:07 Seth Troisi ha scritto:
> New patch which is cleaned up and IMO ready to commit

May I write a few more comments?

> On Mon, Mar 9, 2020 at 5:15 PM Seth Troisi <braintwo at gmail.com> wrote:

>>>> I also dislike the boiler plate of the macros but I didn't

Those macros should probably be moved to gmp-impl.h, to we avoid 
duplication.
For this to be possible, we should avoid having different versions of 
the same macros in the different files...

>> When nbits is small (IMHO the most common case) we'd like to be able
>> to fallback to a constant array which I don't think exist for
>> primesieve (because gmp_limb_bits isn't constant).

Only the first "limb" of the sieve is hard-coded in primesieve.c, but it 
is possible to generate a larger "seed" at configure time, if we want.

>>> Why not using a variable for INCR_LIMIT?

I see now:
+  if (nbits <= 32)
+    incr_limit = 336;
+  else if (nbits <= 64)
+    incr_limit = 1550;
+  else
+    /* Corresponds to a merit 10 prime_gap, which is rare. */
+    incr_limit = 7 * nbits / 2;

Probably, we should change the name of the variable to 
odd_candidates_in_sieve, then you would probably have written:
  if (nbits <= 32)
    odd_numbers_in_sieve = 168;
  else if (nbits <= 64)
    odd_numbers_in_sieve = 775;
  else
   ...

Then I wonder if the cost of the /* Sieve next segment */ step is so 
high that we really have to try hard to avoid it. And if we are able to 
reduce the probability of its use to very unlikely, do we then really 
need to allocate the possibly huge next_mult array?

+      mpz_root (tmp, tmp, 2);

I'd use mpz_sqrt.

+  // TODO: break the rare gap larger than this into gaps <= 255

If you need to store larger gaps, you can also save in the array gap>>1, 
because they all are even. The prime limit will be able to go beyond 
2^37...

+  /* Avoid having a primegap > 255, first occurence 436,273,009. */
+  ASSERT( 4000 < sieve_limit && sieve_limit < 436000000 );

Why do you need to check (4000 < sieve_limit)?

I'd expect a condition like

+  if (nbits <= numberof (primegap_small) * 2 + 1)
+    {
+      primegap = primegap_small;
+      prime_limit = nbits / 2;
+    }

so that all primegap_small can be used. If you think this threshold is 
too high, then primegap_small can be reduced...

Ĝis,
m