mpz_prevprime

[Seth Troisi]

Code looks great, I don't have any further comments

On Tue, Mar 24, 2020 at 12:21 PM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

> Ciao,
>
> Il 2020-03-24 18:54 Seth Troisi ha scritto:
> > On Tue, Mar 24, 2020 at 9:56 AM Marco Bodrato
> > <bodrato at mail.dm.unipi.it> wrote:
> >> I propose a variation of your patch, you find it attached, on my
> >> computer it's faster.
> >
> > Couple of small notes but otherwise this looks good
> >
> > +/* NP_SMALL_LIMIT = prevprime (LAST_PRIME ^ 2) */
> >
> > In the light of the day this can be bumped slightly to
> > prevprime(nextprime(LAST_PRIME)^2) - 1 = 316960
>
> I'm not sure.
> I mean: with that list of primes we can certify primality up to that
> limit, I agree.
> But what about the exit condition?

The current code consider that a number is prime if(n/prime<prime).
> To support n > LAST_PRIME^2, we should add one more branch in the loop.
>
You are correct I was remembering my code.


> > +  /* Technically this should be prev_prime(LAST_PRIME ^ 2) */
> > I'd remove this, It's covered by the comment above


> Right.
>
> > +  if (q < prime)
> > +    return t;
> > +  if (r == 0)
> > +    break;
> >
> > Can this be rearranged to
> >
> > +   if (r == 0)
> > +      break;
> > +   if (q <= prime)
> > +      return t;
>
> I fear it can't. The case t=3, prime=3 would consider 3 a composite.
> Moreover I believe that, on some architectures, q can be ready before r
> is, so the order Torbjorn used should reduce latency. But I may be wrong
> on that point.
>

> The case t=3 can be healed with an if(t<9) return t; just before the
> loop. Then we should measure speed on different platforms.
> With the order you propose, we may use
> NP_SMALL_LIMIT = prevprime (LAST_PRIME * (LAST_PRIME + 1))
> right?
>

I thought my proposed code would allow us to exit potentially one prime
earlier
but if we have to add an additional check before the loop it doesn't help.


>
> > +  ASSERT (i < NUMBER_OF_PRIMES);
> > Should this be placed at the start of the loop or be?
> > +  ASSERT (i+1 < NUMBER_OF_PRIMES);
>
> The ASSERT on i make sense just before i is used by the instruction
> prime+=primegap[i], i.e. at the end of the loop. Isn't it?
>
For some reason I was thinking ++i not i++

>
> >> If writing the code is not too complex, it may be interesting to
> >> test if it is worth.
> >
> > I'll try it out tonight
>
> Great!
>
> >> Did you try tweaking with the -p parameter? It can be useful when a
> >> measure is "noisy".
> >
> > Nope I had not, using -p3 seems to work just as well.
>
> I would have used something like -p100000 or -p1000000, but if -p3 is
> good for you, I'm happy :-)
>
> Ĝis,
> m
>