mpz_prevprime

[Seth Troisi]

Thanks for committing this code!

I'm back with a new mpz_prevprime patch

I also added large negative tests for mpz_nextprime
and we can enable test_largegaps now that the default gap is smaller



On Tue, Mar 24, 2020 at 12:45 PM Seth Troisi <braintwo at gmail.com> wrote:

> 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
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-24 18-12-58.png
Type: image/png
Size: 34751 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200324/1fa3316b/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: prevprime.patch
Type: text/x-patch
Size: 15366 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200324/1fa3316b/attachment-0001.bin>