Il 2022-05-01 17:01 Marco Bodrato ha scritto:
Il 2022-04-30 23:39 Seth Troisi ha scritto:
next_prime took up all of my energy
We should further improve that work!
With your improvements to nextprime, it's really a waste of resources
if ones have to write
for (int i = 0; i < delta2; i++)
mpz_nextprime(p, p);
because every sieved range is used just once, instead of scanning it to
the end.
I mean, we should add a couple of (public or not?) functions:
mpz_nth_{prec,next}prime
I wrote a simple mpz_nth_nextprime, and here are some timings:
$ build/tune/speed -p100000000 -rs 10-60 -t5 mpz_nextprime
mpz_nth_nextprime.2 mpz_nth_nextprime.4 mpz_nth_nextprime.16
mpz_nth_nextprime.256
overhead 0.000000007 secs, precision 100000000 units of 8.56e-10 secs,
CPU freq 1167.94 MHz
mpz_nextprime nth_nxtprim.2 nth_nxtprim.4 nth_nxtprm.16 nth_nxtp.256
10 #0.000001141 2.4384 6.1353 42.1803 4318.7026
15 #0.000002587 2.0795 4.4340 23.0275 1946.8527
20 #0.000025472 1.8204 3.4797 13.7392 237.0212
25 #0.000032677 1.8830 3.6122 14.1018 225.8131
30 #0.000040690 1.8905 3.6741 14.3550 230.1069
35 #0.000053511 1.8285 3.5060 13.4946 215.2175
40 #0.000060637 1.8421 3.5508 13.6446 217.1993
45 #0.000070047 1.8280 3.4869 13.5221 217.8561
50 #0.000078157 1.8100 3.5152 13.6302 216.4944
55 #0.000094682 1.9049 3.6773 14.4213 231.4945
60 #0.000106016 1.8642 3.5877 14.0455 231.0008
This means that, the 256th next prime of a large enough number (more
than 20 bits) is found faster than using _nextprime 256 times.
For smaller numbers this is not evident, for two reasons: current code
use different strategies for numbers smaller than 20 bits, and the 256th
next prime of a 10bit number is a 12bit prime, i.e. a much larger
number.
But I realize that this is not a clever approach.
My code actually finds all the primes and skips them, but this is not
very useful. The need to have a way to loop on primes emerges again.
Ĝis,
m
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
