mpz_prevprime

[Marco Bodrato]

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.

> +  /* 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?

> +  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?

>> 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