Per Marco's comments in my prev_prime/next_prime patch
I moved some of the primesieve macros and functions to gmp-impl.h
LOOP_ON_SIEVE_BEGIN
LOOP_ON_SIEVE_CONTINUE
LOOP_ON_SIEVE_STOP
LOOP_ON_SIEVE_END
bit_to_n (renamed sieve_bit_to_n)
id_to_n (renamedi sieve_id_to_n)
n_to_bit (renamed sieve_n_to_bit)
primesieve_size
This allows the four (soon to be five) identical copies in
bin_uiui, oddfac_1, primorial_ui, and tests/devel/primes
to be cleaned up.
It's not clear where this should be documented, if someone tells me I'm
happy to add some documentation. Existing gmp_primesieve_t in gmp-impl.h
doesn't have any documentation so maybe no entry in the manual or maybe
they should both go under "Integer special functions" or a new "Integer
prime functions" section.
diff -r bcca14c8a090 ChangeLog
--- a/ChangeLog Thu Mar 05 00:43:26 2020 +0100
+++ b/ChangeLog Sun Mar 15 20:29:37 2020 -0700
@@ -1,3 +1,7 @@
+2020-03-15 Seth Troisi <sethtro...@google.com>
+
+ * gmp-impl.h: Add primesieve macros (LOOP_ON_SIEVE_*)
+
2020-02-12 Marco Bodrato <bodr...@mail.dm.unipi.it>
* mpz/cmp.c: Avoid overflow on int even for huge sizes.
diff -r bcca14c8a090 gmp-impl.h
--- a/gmp-impl.h Thu Mar 05 00:43:26 2020 +0100
+++ b/gmp-impl.h Sun Mar 15 20:29:37 2020 -0700
@@ -2078,6 +2078,52 @@
__GMP_DECLSPEC mp_limb_t gmp_primesieve (mp_ptr, mp_limb_t);
+/* primesieve macros and functions */
+static mp_limb_t
+sieve_bit_to_n (mp_limb_t bit) { return (bit*3+4)|1; }
+
+static mp_limb_t
+sieve_id_to_n (mp_limb_t id) { return id*3+1+(id&1); }
+
+/* n_to_bit (n) = ((n-1)&(-CNST_LIMB(2)))/3U-1 */
+static mp_limb_t
+sieve_n_to_bit (mp_limb_t n) { return ((n-5)|1)/3U; }
+
+static mp_size_t
+primesieve_size (mp_limb_t n) { return sieve_n_to_bit(n) / GMP_LIMB_BITS + 1; }
+
+#define LOOP_ON_SIEVE_CONTINUE(prime,end,sieve) \
+ __max_i = (end); \
+ \
+ do { \
+ ++__i; \
+ if (((sieve)[__index] & __mask) == 0) \
+ { \
+ mp_limb_t prime; \
+ prime = sieve_id_to_n(__i)
+
+#define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \
+ do { \
+ mp_limb_t __mask, __index, __max_i, __i; \
+ \
+ __i = (start)-(off); \
+ __index = __i / GMP_LIMB_BITS; \
+ __mask = CNST_LIMB(1) << (__i % GMP_LIMB_BITS); \
+ __i += (off); \
+ \
+ LOOP_ON_SIEVE_CONTINUE(prime,end,sieve)
+
+#define LOOP_ON_SIEVE_STOP \
+ } \
+ __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \
+ __index += __mask & 1; \
+ } while (__i <= __max_i)
+
+#define LOOP_ON_SIEVE_END \
+ LOOP_ON_SIEVE_STOP; \
+ } while (0)
+
+
#ifndef MUL_TOOM22_THRESHOLD
#define MUL_TOOM22_THRESHOLD 30
#endif
diff -r bcca14c8a090 mpz/bin_uiui.c
--- a/mpz/bin_uiui.c Thu Mar 05 00:43:26 2020 +0100
+++ b/mpz/bin_uiui.c Sun Mar 15 20:29:37 2020 -0700
@@ -491,57 +491,6 @@
(PR) *= (P); \
} while (0)
-#define LOOP_ON_SIEVE_CONTINUE(prime,end,sieve) \
- __max_i = (end); \
- \
- do { \
- ++__i; \
- if (((sieve)[__index] & __mask) == 0) \
- { \
- mp_limb_t prime; \
- prime = id_to_n(__i)
-
-#define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \
- do { \
- mp_limb_t __mask, __index, __max_i, __i; \
- \
- __i = (start)-(off); \
- __index = __i / GMP_LIMB_BITS; \
- __mask = CNST_LIMB(1) << (__i % GMP_LIMB_BITS); \
- __i += (off); \
- \
- LOOP_ON_SIEVE_CONTINUE(prime,end,sieve)
-
-#define LOOP_ON_SIEVE_STOP \
- } \
- __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \
- __index += __mask & 1; \
- } while (__i <= __max_i)
-
-#define LOOP_ON_SIEVE_END \
- LOOP_ON_SIEVE_STOP; \
- } while (0)
-
-/*********************************************************/
-/* Section sieve: sieving functions and tools for primes */
-/*********************************************************/
-
-#if WANT_ASSERT
-static mp_limb_t
-bit_to_n (mp_limb_t bit) { return (bit*3+4)|1; }
-#endif
-
-/* id_to_n (x) = bit_to_n (x-1) = (id*3+1)|1*/
-static mp_limb_t
-id_to_n (mp_limb_t id) { return id*3+1+(id&1); }
-
-/* n_to_bit (n) = ((n-1)&(-CNST_LIMB(2)))/3U-1 */
-static mp_limb_t
-n_to_bit (mp_limb_t n) { return ((n-5)|1)/3U; }
-
-static mp_size_t
-primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; }
-
/*********************************************************/
/* Section binomial: fast binomial implementation */
/*********************************************************/
@@ -622,17 +571,17 @@
mp_limb_t s;
s = limb_apprsqrt(n);
- s = n_to_bit (s);
+ s = sieve_n_to_bit (s);
ASSERT (bit_to_n (s+1) * bit_to_n (s+1) > n);
- ASSERT (s <= n_to_bit (n >> 1));
- LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (5), s, 0,sieve);
+ ASSERT (s <= sieve_n_to_bit (n >> 1));
+ LOOP_ON_SIEVE_BEGIN (prime, sieve_n_to_bit (5), s, 0, sieve);
COUNT_A_PRIME (prime, n, k, prod, max_prod, factors, j);
LOOP_ON_SIEVE_STOP;
ASSERT (max_prod <= GMP_NUMB_MAX / 2);
max_prod <<= 1;
- LOOP_ON_SIEVE_CONTINUE (prime, n_to_bit (n >> 1),sieve);
+ LOOP_ON_SIEVE_CONTINUE (prime, sieve_n_to_bit (n >> 1), sieve);
SH_COUNT_A_PRIME (prime, n, k, prod, max_prod, factors, j);
LOOP_ON_SIEVE_END;
@@ -640,9 +589,9 @@
}
/* Store primes from (n-k)+1 to n */
- ASSERT (n_to_bit (n - k) < n_to_bit (n));
+ ASSERT (sieve_n_to_bit (n - k) < sieve_n_to_bit (n));
- LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (n - k) + 1, n_to_bit (n), 0,sieve);
+ LOOP_ON_SIEVE_BEGIN (prime, sieve_n_to_bit (n - k) + 1, sieve_n_to_bit (n), 0, sieve);
FACTOR_LIST_STORE (prime, prod, max_prod, factors, j);
LOOP_ON_SIEVE_END;
@@ -661,10 +610,6 @@
#undef COUNT_A_PRIME
#undef SH_COUNT_A_PRIME
-#undef LOOP_ON_SIEVE_END
-#undef LOOP_ON_SIEVE_STOP
-#undef LOOP_ON_SIEVE_BEGIN
-#undef LOOP_ON_SIEVE_CONTINUE
/*********************************************************/
/* End of implementation of Goetgheluck's algorithm */
diff -r bcca14c8a090 mpz/oddfac_1.c
--- a/mpz/oddfac_1.c Thu Mar 05 00:43:26 2020 +0100
+++ b/mpz/oddfac_1.c Sun Mar 15 20:29:37 2020 -0700
@@ -61,59 +61,6 @@
(PR) *= (P); \
} while (0)
-#define LOOP_ON_SIEVE_CONTINUE(prime,end,sieve) \
- __max_i = (end); \
- \
- do { \
- ++__i; \
- if (((sieve)[__index] & __mask) == 0) \
- { \
- mp_limb_t prime; \
- prime = id_to_n(__i)
-
-#define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \
- do { \
- mp_limb_t __mask, __index, __max_i, __i; \
- \
- __i = (start)-(off); \
- __index = __i / GMP_LIMB_BITS; \
- __mask = CNST_LIMB(1) << (__i % GMP_LIMB_BITS); \
- __i += (off); \
- \
- LOOP_ON_SIEVE_CONTINUE(prime,end,sieve)
-
-#define LOOP_ON_SIEVE_STOP \
- } \
- __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \
- __index += __mask & 1; \
- } while (__i <= __max_i)
-
-#define LOOP_ON_SIEVE_END \
- LOOP_ON_SIEVE_STOP; \
- } while (0)
-
-/*********************************************************/
-/* Section sieve: sieving functions and tools for primes */
-/*********************************************************/
-
-#if WANT_ASSERT
-static mp_limb_t
-bit_to_n (mp_limb_t bit) { return (bit*3+4)|1; }
-#endif
-
-/* id_to_n (x) = bit_to_n (x-1) = (id*3+1)|1*/
-static mp_limb_t
-id_to_n (mp_limb_t id) { return id*3+1+(id&1); }
-
-/* n_to_bit (n) = ((n-1)&(-CNST_LIMB(2)))/3U-1 */
-static mp_limb_t
-n_to_bit (mp_limb_t n) { return ((n-5)|1)/3U; }
-
-#if WANT_ASSERT
-static mp_size_t
-primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; }
-#endif
-
/*********************************************************/
/* Section mswing: 2-multiswing factorial */
/*********************************************************/
@@ -211,10 +158,10 @@
s = limb_apprsqrt(n);
ASSERT (s >= 5);
- s = n_to_bit (s);
+ s = sieve_n_to_bit (s);
ASSERT (bit_to_n (s+1) * bit_to_n (s+1) > n);
- ASSERT (s < n_to_bit (n / 3));
- LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (5), s, 0,sieve);
+ ASSERT (s < sieve_n_to_bit (n / 3));
+ LOOP_ON_SIEVE_BEGIN (prime, sieve_n_to_bit (5), s, 0, sieve);
SWING_A_PRIME (prime, n, prod, max_prod, factors, j);
LOOP_ON_SIEVE_STOP;
@@ -222,13 +169,13 @@
l_max_prod = max_prod * 3;
- LOOP_ON_SIEVE_CONTINUE (prime, n_to_bit (n/3), sieve);
+ LOOP_ON_SIEVE_CONTINUE (prime, sieve_n_to_bit (n/3), sieve);
SH_SWING_A_PRIME (prime, n, prod, l_max_prod, factors, j);
LOOP_ON_SIEVE_END;
}
/* Store primes from (n+1)/2 to n */
- LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (n >> 1) + 1, n_to_bit (n), 0,sieve);
+ LOOP_ON_SIEVE_BEGIN (prime, sieve_n_to_bit (n >> 1) + 1, sieve_n_to_bit (n), 0, sieve);
FACTOR_LIST_STORE (prime, prod, max_prod, factors, j);
LOOP_ON_SIEVE_END;
@@ -247,10 +194,6 @@
#undef SWING_A_PRIME
#undef SH_SWING_A_PRIME
-#undef LOOP_ON_SIEVE_END
-#undef LOOP_ON_SIEVE_STOP
-#undef LOOP_ON_SIEVE_BEGIN
-#undef LOOP_ON_SIEVE_CONTINUE
#undef FACTOR_LIST_APPEND
/*********************************************************/
diff -r bcca14c8a090 mpz/primorial_ui.c
--- a/mpz/primorial_ui.c Thu Mar 05 00:43:26 2020 +0100
+++ b/mpz/primorial_ui.c Sun Mar 15 20:29:37 2020 -0700
@@ -48,37 +48,6 @@
(PR) *= (P); \
} while (0)
-#define LOOP_ON_SIEVE_CONTINUE(prime,end,sieve) \
- __max_i = (end); \
- \
- do { \
- ++__i; \
- if (((sieve)[__index] & __mask) == 0) \
- { \
- mp_limb_t prime; \
- prime = id_to_n(__i)
-
-#define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \
- do { \
- mp_limb_t __mask, __index, __max_i, __i; \
- \
- __i = (start)-(off); \
- __index = __i / GMP_LIMB_BITS; \
- __mask = CNST_LIMB(1) << (__i % GMP_LIMB_BITS); \
- __i += (off); \
- \
- LOOP_ON_SIEVE_CONTINUE(prime,end,sieve)
-
-#define LOOP_ON_SIEVE_STOP \
- } \
- __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \
- __index += __mask & 1; \
- } while (__i <= __max_i)
-
-#define LOOP_ON_SIEVE_END \
- LOOP_ON_SIEVE_STOP; \
- } while (0)
-
/*********************************************************/
/* Section sieve: sieving functions and tools for primes */
/*********************************************************/
@@ -88,19 +57,6 @@
bit_to_n (mp_limb_t bit) { return (bit*3+4)|1; }
#endif
-/* id_to_n (x) = bit_to_n (x-1) = (id*3+1)|1*/
-static mp_limb_t
-id_to_n (mp_limb_t id) { return id*3+1+(id&1); }
-
-/* n_to_bit (n) = ((n-1)&(-CNST_LIMB(2)))/3U-1 */
-static mp_limb_t
-n_to_bit (mp_limb_t n) { return ((n-5)|1)/3U; }
-
-#if WANT_ASSERT
-static mp_size_t
-primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; }
-#endif
-
/*********************************************************/
/* Section primorial: implementation */
/*********************************************************/
@@ -141,7 +97,7 @@
max_prod = GMP_NUMB_MAX / n;
- LOOP_ON_SIEVE_BEGIN (prime, n_to_bit(5), n_to_bit (n), 0, sieve);
+ LOOP_ON_SIEVE_BEGIN (prime, sieve_n_to_bit(5), sieve_n_to_bit (n), 0, sieve);
FACTOR_LIST_STORE (prime, prod, max_prod, factors, j);
LOOP_ON_SIEVE_END;
}
diff -r bcca14c8a090 tests/devel/primes.c
--- a/tests/devel/primes.c Thu Mar 05 00:43:26 2020 +0100
+++ b/tests/devel/primes.c Sun Mar 15 20:29:37 2020 -0700
@@ -57,48 +57,6 @@
#define BLOCK_SIZE 2048
#endif
-/*********************************************************/
-/* Section sieve: sieving functions and tools for primes */
-/*********************************************************/
-
-static mp_size_t
-primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; }
-
-/*************************************************************/
-/* Section macros: common macros, for swing/fac/bin (&sieve) */
-/*************************************************************/
-
-#define LOOP_ON_SIEVE_CONTINUE(prime,end,sieve) \
- __max_i = (end); \
- \
- do { \
- ++__i; \
- if (((sieve)[__index] & __mask) == 0) \
- { \
- mp_limb_t prime; \
- prime = id_to_n(__i)
-
-#define LOOP_ON_SIEVE_BEGIN(prime,start,end,off,sieve) \
- do { \
- mp_limb_t __mask, __index, __max_i, __i; \
- \
- __i = (start)-(off); \
- __index = __i / GMP_LIMB_BITS; \
- __mask = CNST_LIMB(1) << (__i % GMP_LIMB_BITS); \
- __i += (off); \
- \
- LOOP_ON_SIEVE_CONTINUE(prime,end,sieve)
-
-#define LOOP_ON_SIEVE_STOP \
- } \
- __mask = __mask << 1 | __mask >> (GMP_LIMB_BITS-1); \
- __index += __mask & 1; \
- } while (__i <= __max_i)
-
-#define LOOP_ON_SIEVE_END \
- LOOP_ON_SIEVE_STOP; \
- } while (0)
-
mpz_t g;
int something_wrong (mpz_t er, int exp)
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
