Il 2020-03-21 11:42 Seth Troisi ha scritto:
I see this was pushed, with a few more polishing tweaks.
Yes, but there are bad news, it introduces a speed regression for small
numbers.
I see you also added more testing in tests/devel/primes.c which is a
great triple check.
It looks like the usage on line 21-28 / 399 wasn't updated.
Not yet updated, you are right.
I also added a target for tune/speed.
tune/speed -s<num> mpz_nextprime_1.<r>
measure the time needed to compute the first <r> primes larger than
<num>, and divides by <r>.
If on my environment I try
$ tune/speed -s1-4000 -t2 mpz_nextprime_1.16
before, and after the patch, I see that nextprime on small numbers is
now slower.
Before introducing new functions, may I suggest to try to speed up the
function also for small numbers?
You measured how much it is worth sieving before using the Miller-Rabin
(actually BPSW) test. But for really small numbers, the sieve alone can
be enough and the expensive test can be totally skipped.
I attach a possible patch for this purpose.
Ĝis,
m
diff -r a7836288d2c0 mpz/nextprime.c
--- a/mpz/nextprime.c Fri Mar 20 16:19:07 2020 +0100
+++ b/mpz/nextprime.c Sat Mar 21 15:16:27 2020 +0100
@@ -85,6 +85,11 @@
};
#define NUMBER_OF_PRIMES 100
+#define LAST_PRIME 557
+/* SIEVE_ONLY_GAP = maximal gap between primes < LAST_PRIME^2,
+ We are between 155921+86=156007 and 360653+96=360749 .
+*/
+#define SIEVE_ONLY_GAP 86
static unsigned long
calculate_sievelimit(mp_bitcnt_t nbits) {
@@ -130,6 +135,7 @@
mp_bitcnt_t nbits;
int i, m;
unsigned odds_in_composite_sieve;
+ int sieve_only;
TMP_DECL;
/* First handle tiny numbers */
@@ -141,10 +147,37 @@
mpz_add_ui (p, n, 1);
mpz_setbit (p, 0);
- if (mpz_cmp_ui (p, 7) <= 0)
- return;
+ TMP_MARK;
- TMP_MARK;
+ if (mpz_cmp_ui (p, LAST_PRIME*LAST_PRIME - SIEVE_ONLY_GAP) <= 0)
+ {
+ unsigned long pl, cp;
+ int i;
+ primegap = primegap_small;
+
+ pl = mpz_get_ui (p);
+ cp = 3;
+ i = 0;
+ if (mpz_cmp_ui (p, LAST_PRIME) <= 0)
+ {
+ for ( ; cp < pl; cp += primegap[i++])
+ ;
+ mpz_set_ui (p, cp);
+ return;
+ }
+
+ odds_in_composite_sieve = SIEVE_ONLY_GAP / 2;
+ pl += SIEVE_ONLY_GAP - 2;
+ do {
+ cp += primegap[i++];
+ } while (cp*cp < pl);
+
+ prime_limit = i;
+ sieve_only = 1;
+ }
+ else
+ {
+ /* TODO: Reindent the following code. */
pn = SIZ(p);
MPN_SIZEINBASE_2EXP(nbits, PTR(p), pn, 1);
if (nbits / 2 <= NUMBER_OF_PRIMES)
@@ -192,6 +225,9 @@
/* Corresponds to a merit 14 prime_gap, which is rare. */
odds_in_composite_sieve = 5 * nbits;
+ sieve_only = 0;
+ }
+
/* composite[2*i] stores if p+2*i is a known composite */
composite = TMP_SALLOC_TYPE (odds_in_composite_sieve, char);
@@ -226,7 +262,7 @@
difference = 0;
/* Miller-Rabin test */
- if (mpz_millerrabin (p, 25))
+ if (sieve_only || mpz_millerrabin (p, 25))
{
TMP_FREE;
return;
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
