mpz_prevprime

[Seth Troisi]

Did you still limit the trial division to prime_limit?
trialdivtab.h has extra primes (1000 primes up to 10,000 instead of the
first 180 primes up to 1000).
which decreases the percentage of numbers that need prime testing from ~8%
to ~6%

This shouldn't affect numbers less than 200 bits (where you are still
seeing gains),
I'd love to see your code so I can try to understand what I might not
tested.








On Mon, Feb 10, 2020 at 12:01 PM Niels Möller <nisse at lysator.liu.se> wrote:

> Seth Troisi <braintwo at gmail.com> writes:
>
> > This was discussed previously in this thread
> > https://gmplib.org/list-archives/gmp-devel/2019-September/005465.html
> > TL;DR >95% of time is spent in miller rabin.
>
> I tried out using the same dtab table used in trialdiv.c.
>
> On my laptop, it gives a speedup of about 25% for larger sizes. Not sure
> how to tune for small sizes, but clearly the old code clamping the size
> of the prime table based on the bit size is better than doing nothing.
>
> The computation of all the moduli could be speed up by using ptab, and
> by using precomputed reciprocals. Not clear to me how much the speed of
> that part matters. I haven't run any profiling.
>
> Before:
>
> $ ./tune/speed -s 100-300 -f 1.1 mpz_nextprime
> overhead 0.000000005 secs, precision 10000 units of 8.34e-10 secs, CPU
> freq 1198.47 MHz
>         mpz_nextprime
> 100       0.000134064
> 110       0.000145867
> 121       0.000170687
> 133       0.000301883
> 146       0.000341107
> 160       0.000403326
> 176       0.000451402
> 193       0.000745043
> 212       0.000790877
> 233       0.000896869
> 256       0.001118979
> 281       0.001641613
>
> 500       0.008096105
> 1000      0.091219932
>
> After:
> $ ./tune/speed -s 100-300 -f 1.1 mpz_nextprime
> overhead 0.000000005 secs, precision 10000 units of 8.14e-10 secs, CPU
> freq 1228.24 MHz
>         mpz_nextprime
> 100       0.000212717
> 110       0.000223992
> 121       0.000241062
> 133       0.000355139
> 146       0.000388422
> 160       0.000435633
> 176       0.000477857
> 193       0.000716578
> 212       0.000757639
> 233       0.000847678
> 256       0.001018164
> 281       0.001435439
>
> 500       0.006692777
> 1000      0.072001893
>
> Regards,
> /Niels
>
>
>
> --
> Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
> Internet email is subject to wholesale government surveillance.
>