[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Thu Oct 14 05:06:58 UTC 2021
details: /var/hg/gmp/rev/7fdee05cf219
changeset: 18258:7fdee05cf219
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Thu Oct 14 07:05:13 2021 +0200
description:
Add speed support for gmp_primesieve.
details: /var/hg/gmp/rev/82a948702059
changeset: 18259:82a948702059
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Thu Oct 14 07:06:45 2021 +0200
description:
primesieve.c: Siplify block sieving code.
diffstat:
primesieve.c | 47 ++++++++++++++---------------------------------
tune/common.c | 6 ++++++
tune/speed.c | 1 +
tune/speed.h | 29 +++++++++++++++++++++++++++++
4 files changed, 50 insertions(+), 33 deletions(-)
diffs (155 lines):
diff -r 9d7487ca7ec4 -r 82a948702059 primesieve.c
--- a/primesieve.c Sun Oct 10 03:35:48 2021 +0200
+++ b/primesieve.c Thu Oct 14 07:06:45 2021 +0200
@@ -7,7 +7,7 @@
IN FACT, IT IS ALMOST GUARANTEED THAT IT WILL CHANGE OR
DISAPPEAR IN A FUTURE GNU MP RELEASE.
-Copyright 2010-2012, 2015, 2016 Free Software Foundation, Inc.
+Copyright 2010-2012, 2015, 2016, 2021 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -301,34 +301,11 @@
} while (1);
}
-static void
-first_block_primesieve (mp_ptr bit_array, mp_limb_t n)
-{
- static mp_limb_t presieved[] = {PRIMESIEVE_INIT_TABLE};
-
- mp_size_t bits, limbs;
- mp_limb_t i;
-
- ASSERT (n > 4);
-
- bits = n_fto_bit(n);
- limbs = bits / GMP_LIMB_BITS + 1;
-
- for (mp_size_t j = 0, lim = MIN (limbs, PRIMESIEVE_NUMBEROF_TABLE);
- j < lim; ++j)
- bit_array [j] = presieved [j]; /* memcopy? */
-
- if (limbs > PRIMESIEVE_NUMBEROF_TABLE)
- block_resieve (bit_array + PRIMESIEVE_NUMBEROF_TABLE,
- limbs - PRIMESIEVE_NUMBEROF_TABLE,
- GMP_LIMB_BITS * PRIMESIEVE_NUMBEROF_TABLE, bit_array);
-}
-
#define BLOCK_SIZE 2048
/* Fills bit_array with the characteristic function of composite
- numbers up to the parameter n. I.e. a bit set to "1" represent a
- composite, a "0" represent a prime.
+ numbers up to the parameter n. I.e. a bit set to "1" represents a
+ composite, a "0" represents a prime.
The primesieve_size(n) limbs pointed to by bit_array are
overwritten. The returned value counts prime integers in the
@@ -347,21 +324,25 @@
{
mp_size_t size;
mp_limb_t bits;
+ static mp_limb_t presieved[] = {PRIMESIEVE_INIT_TABLE};
ASSERT (n > 4);
bits = n_fto_bit(n);
size = bits / GMP_LIMB_BITS + 1;
- if (size > BLOCK_SIZE * 2) {
+ for (mp_size_t j = 0, lim = MIN (size, PRIMESIEVE_NUMBEROF_TABLE);
+ j < lim; ++j)
+ bit_array [j] = presieved [j]; /* memcopy? */
+
+ if (size > PRIMESIEVE_NUMBEROF_TABLE) {
mp_size_t off;
- off = BLOCK_SIZE + (size % BLOCK_SIZE);
- first_block_primesieve (bit_array, id_to_n (off * GMP_LIMB_BITS));
- do {
+ off = size > 2 * BLOCK_SIZE ? BLOCK_SIZE + (size % BLOCK_SIZE) : size;
+ block_resieve (bit_array + PRIMESIEVE_NUMBEROF_TABLE,
+ off - PRIMESIEVE_NUMBEROF_TABLE,
+ GMP_LIMB_BITS * PRIMESIEVE_NUMBEROF_TABLE, bit_array);
+ for (; off < size; off += BLOCK_SIZE)
block_resieve (bit_array + off, BLOCK_SIZE, off * GMP_LIMB_BITS, bit_array);
- } while ((off += BLOCK_SIZE) < size);
- } else {
- first_block_primesieve (bit_array, n);
}
if ((bits + 1) % GMP_LIMB_BITS != 0)
diff -r 9d7487ca7ec4 -r 82a948702059 tune/common.c
--- a/tune/common.c Sun Oct 10 03:35:48 2021 +0200
+++ b/tune/common.c Thu Oct 14 07:06:45 2021 +0200
@@ -1781,6 +1781,12 @@
}
double
+speed_gmp_primesieve (struct speed_params *s)
+{
+ SPEED_ROUTINE_GMP_PRIMESIEVE (gmp_primesieve);
+}
+
+double
speed_mpz_nextprime (struct speed_params *s)
{
SPEED_ROUTINE_MPZ_NEXTPRIME (mpz_nextprime);
diff -r 9d7487ca7ec4 -r 82a948702059 tune/speed.c
--- a/tune/speed.c Sun Oct 10 03:35:48 2021 +0200
+++ b/tune/speed.c Thu Oct 14 07:06:45 2021 +0200
@@ -321,6 +321,7 @@
{ "mpn_gcdext_lehmer", speed_mpn_gcdext_lehmer },
#endif
+ { "gmp_primesieve", speed_gmp_primesieve },
{ "mpz_nextprime", speed_mpz_nextprime },
{ "mpz_nextprime_1", speed_mpz_nextprime_1, FLAG_R_OPTIONAL },
{ "mpz_prevprime", speed_mpz_prevprime },
diff -r 9d7487ca7ec4 -r 82a948702059 tune/speed.h
--- a/tune/speed.h Sun Oct 10 03:35:48 2021 +0200
+++ b/tune/speed.h Thu Oct 14 07:06:45 2021 +0200
@@ -410,6 +410,7 @@
double speed_mpz_fib2_ui (struct speed_params *);
double speed_mpz_init_clear (struct speed_params *);
double speed_mpz_init_realloc_clear (struct speed_params *);
+double speed_gmp_primesieve (struct speed_params *);
double speed_mpz_nextprime (struct speed_params *);
double speed_mpz_nextprime_1 (struct speed_params *);
double speed_mpz_prevprime (struct speed_params *);
@@ -3248,6 +3249,34 @@
return t; \
}
+#define SPEED_ROUTINE_GMP_PRIMESIEVE(function) \
+{ \
+ mp_ptr wp; \
+ unsigned i; \
+ double t; \
+ mp_limb_t a = s->size * GMP_LIMB_BITS * 3; \
+ TMP_DECL; \
+ \
+ SPEED_RESTRICT_COND (s->size >= 1); \
+ \
+ TMP_MARK; \
+ SPEED_TMP_ALLOC_LIMBS (wp, s->size, s->align_wp); \
+ \
+ speed_operand_dst (s, wp, s->size); \
+ speed_cache_fill (s); \
+ \
+ speed_starttime (); \
+ i = s->reps; \
+ do \
+ function (wp, a); \
+ while (--i != 0); \
+ t = speed_endtime (); \
+ \
+ TMP_FREE; \
+ return t; \
+}
+
+
/* Calculate nextprime(n) for random n of s->size bits (not limbs). */
#define SPEED_ROUTINE_MPZ_NEXTPRIME(function) \
{ \
More information about the gmp-commit
mailing list