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 <ni...@lysator.liu.se> wrote: > Seth Troisi <brain...@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. > _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
