possible speedup for mpz_nextprime_small

[Seth Troisi]

This is a continuation of the mpz_prevprime thread but with a better name.

Marco was interested in what using dynamically allocating primes would look
like.
I've attached a couple of screenshots.

"static_benefit" measures the maximum speedup from having a larger prime
table.
Just above the current threshold (310,000 = 18 bits) the large table gives
us a *3x speedup*, and it is slightly faster up to ~30 million (the speedup
is less and less and requires more and more entries be added to
primegap_small).

I implemented a dynamic version (see patch) which gets about half of the
gain.

With the dynamic version we could improve THRESHOLD from 310,000 to
X,000,000, IMHO if we want that 2-3x speedup it's less code (and maybe less
final size) to just include 70-200 extra primes in primegap_small which
would be faster and require less special code.

All of this got me thinking about Marco's speedup version which reused the
sieve, I was hoping this would be faster on medium / large ranges, so I
tried that out with a larger static table and using their ulong patch
(which was a nice insight) but sadly this is also slower (marco.png)

I think a good balance would be to add 70 primes and increase SMALL_LIMIT
to 1,000,000
This allows us to capture ~1/3 of the potential improvement with relatively
minor change.

We would need a new constant to differentiate
if (nbits / 2 < NUMBER_OF_PRIMES)
  and
ASSERT (i < NUMBER_OF_PRIMES);

At the same time this is a relatively minor improvement and I think we're
good doing nothing (especially if Marco is getting tired of reviewing,
improving, and committing my code)

Much thanks to Marco for their quick reviews and insight throughout.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: static_benefit.png
Type: image/png
Size: 29941 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200325/e25cd070/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dynamic_nextprime_small.patch
Type: text/x-patch
Size: 10115 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200325/e25cd070/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: marco.png
Type: image/png
Size: 34544 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200325/e25cd070/attachment-0003.png>