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

Reply via email to