possible speedup for mpz_nextprime_small

[Seth Troisi]

I tried two changes for pprime_p.c

The first was to change `unsigned int long` to `unsigned int` for static
int isprime
the second was to add primegap_small and change the loop to

static int
isprime (unsigned int t)
{
  unsigned int q, r, i, p;
  ASSERT (t >= 3 && (t & 1) != 0);
  i = 0;
  p = 3;
  do {
      q = t / p;
      r = t - q * p;
      if (q < p)
       return 1;
      p += primegap_small[i++];
  } while (r != 0);
  return 0;
}

The first change is ~2x faster
The primegap change is ~2x faster again

I'd estimate that on my system a tuned threshold would be ~10M which takes
~450 primes (nextprime)



On Fri, Mar 27, 2020 at 1:36 PM Seth Troisi <braintwo at gmail.com> wrote:

> I looked at mpz_probab_prime_p today and for numbers <= 1M it checks all
> odds up to 1000 using very similiar code as nextprime_small.
> So now I'm thinking maybe we should add a medium static list and share it
> with mpz_probab_prime_p.
>
> afterwards mpz_nextprime_small could be simplified to
>
> static unsigned
> mpz_nextprime_small (unsigned t)
> {
>   /* Start from next candidate (2 or odd) */
>   t = (t + 1) | (t > 1);
>   for (; ; t += 2)
>     if (mpz_probab_prime_p_internal_small_case(t))
>       return t;
> }
>
> I'm not sure how to share a list between two source files but if you point
> me at an example I'm happy to try something.
> I also adding probab_prime_p to speed see speed_probab_prime.patch note I
> didn't get the time to look other the patch so it might be extra rought.
>
>
> On Thu, Mar 26, 2020 at 7:20 AM Marco Bodrato <bodrato at mail.dm.unipi.it>
> wrote:
>
>> Ciao,
>>
>> Il 2020-03-26 01:06 Seth Troisi ha scritto:
>> > Marco was interested in what using dynamically allocating primes would
>> > look like.
>> > I've attached a couple of screenshots.
>>
>> I'd like to understand the reason why the line "dynamic" is 5-10% lower
>> than the other lines in the range above 27...
>>
> There's a certain amount of noise in the benchmark (remember that it
> chooses a random start between 2^(n-1) to 2^n which is a big range)
> Sometimes I forget to pause music in chrome which is another source of
> variation.
> I reran (with -p100000000) being careful that nothing was running in the
> background and with 2 runs to show a sense of variation.
>
>
>> > I think a good balance would be to add 70 primes and increase
>> > SMALL_LIMIT to 1,000,000
>>
>> Adding back the primes we just removed, because they are useful again!
>>
>> > We would need a new constant to differentiate
>> > if (nbits / 2 < NUMBER_OF_PRIMES)
>> >   and
>> > ASSERT (i < NUMBER_OF_PRIMES);
>>
>> Yes. The first is a threshold to switch from a method to another. Should
>> it be tuned on different CPUs?
>>
> I've never done this so I'm not sure how much work it is. If you think
> it's a good idea I'm happy to try it out.
>
> NUMBER_OF_PRIMES is the hard limit for that threshold.
>>
>> Ĝis,
>> m
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-27 17-35-34.png
Type: image/png
Size: 81151 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200327/1e377c04/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-27 17-36-30.png
Type: image/png
Size: 65012 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200327/1e377c04/attachment-0003.png>