[Gmp-commit] /var/hg/gmp: 6 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Fri Oct 1 21:27:25 UTC 2021
details: /var/hg/gmp/rev/c38bad0f9c4b
changeset: 18244:c38bad0f9c4b
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri Oct 01 22:36:14 2021 +0200
description:
mini-gmp/mini-mpq.c: #define needed if mini-gmp.h is not included
details: /var/hg/gmp/rev/ee32996c8d12
changeset: 18245:ee32996c8d12
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri Oct 01 22:39:11 2021 +0200
description:
mini-gmp/mini-gmp.c: Add asserts (removed at compile time) on limb size.
details: /var/hg/gmp/rev/7c031f543da0
changeset: 18246:7c031f543da0
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri Oct 01 22:40:41 2021 +0200
description:
gen-sieve.c: New file to generate a small pre-sieved array
details: /var/hg/gmp/rev/cbb57408d6fd
changeset: 18247:cbb57408d6fd
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri Oct 01 22:42:42 2021 +0200
description:
primesieve.c: Simplify first_block_primesieve if a presieved array is available
details: /var/hg/gmp/rev/68e21c72de7b
changeset: 18248:68e21c72de7b
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri Oct 01 22:44:16 2021 +0200
description:
Makefile.am, gmp-impl.h: Use gen-sieve and its output
details: /var/hg/gmp/rev/d13fbd898d4e
changeset: 18249:d13fbd898d4e
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Fri Oct 01 22:58:49 2021 +0200
description:
ChangeLog
diffstat:
ChangeLog | 7 ++
Makefile.am | 9 +++
gen-sieve.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++
gmp-impl.h | 1 +
mini-gmp/ChangeLog | 5 ++
mini-gmp/mini-gmp.c | 2 +
mini-gmp/mini-mpq.c | 1 +
primesieve.c | 105 +++++++++++--------------------------------
8 files changed, 175 insertions(+), 78 deletions(-)
diffs (truncated from 349 to 300 lines):
diff -r 0140c03f9c72 -r d13fbd898d4e ChangeLog
--- a/ChangeLog Sun Sep 26 13:56:41 2021 +0200
+++ b/ChangeLog Fri Oct 01 22:58:49 2021 +0200
@@ -1,3 +1,10 @@
+2021-10-01 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * gen-sieve.c: New file to generate a small presieved array.
+ * primesieve.c (first_block_primesieve): Use the presieved array.
+ * gmp-impl.h: #include output of gen-sieve.
+ * Makefile.am: Add rules for gen-sieve and sieve_table.h.
+
2021-09-25 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mpz/import.c: Use MPN_BSWAP_REVERSE, reorder branches.
diff -r 0140c03f9c72 -r d13fbd898d4e Makefile.am
--- a/Makefile.am Sun Sep 26 13:56:41 2021 +0200
+++ b/Makefile.am Fri Oct 01 22:58:49 2021 +0200
@@ -353,6 +353,15 @@
DISTCLEANFILES += gen-fac$(EXEEXT_FOR_BUILD)
EXTRA_DIST += gen-fac.c
+sieve_table.h: gen-sieve$(EXEEXT_FOR_BUILD)
+ ./gen-sieve $(GMP_LIMB_BITS) >sieve_table.h || (rm -f sieve_table.h; exit 1)
+BUILT_SOURCES += sieve_table.h
+
+gen-sieve$(EXEEXT_FOR_BUILD): gen-sieve$(U_FOR_BUILD).c bootstrap.c
+ $(CC_FOR_BUILD) `test -f 'gen-sieve$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-sieve$(U_FOR_BUILD).c -o gen-sieve$(EXEEXT_FOR_BUILD)
+DISTCLEANFILES += gen-sieve$(EXEEXT_FOR_BUILD)
+EXTRA_DIST += gen-sieve.c
+
fib_table.h: gen-fib$(EXEEXT_FOR_BUILD)
./gen-fib header $(GMP_LIMB_BITS) $(GMP_NAIL_BITS) >fib_table.h || (rm -f fib_table.h; exit 1)
diff -r 0140c03f9c72 -r d13fbd898d4e gen-sieve.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/gen-sieve.c Fri Oct 01 22:58:49 2021 +0200
@@ -0,0 +1,123 @@
+/* Generate primesieve data.
+
+ Contributed to the GNU project by Marco Bodrato.
+
+Copyright 2021 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of either:
+
+ * the GNU Lesser General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your
+ option) any later version.
+
+or
+
+ * the GNU General Public License as published by the Free Software
+ Foundation; either version 2 of the License, or (at your option) any
+ later version.
+
+or both in parallel, as here.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received copies of the GNU General Public License and the
+GNU Lesser General Public License along with the GNU MP Library. If not,
+see https://www.gnu.org/licenses/. */
+
+#include <stdio.h>
+#include "bootstrap.c"
+
+static int
+bit_to_n (int bit) { return (bit*3+4)|1; }
+
+int
+generate (int limb_bits, int limit)
+{
+ mpz_t limb;
+ int i, lb, pc, c, totpc, maxprime;
+
+ mpz_init (limb);
+
+ printf ("/* This file generated by gen-sieve.c - DO NOT EDIT. */\n");
+ printf ("\n");
+ printf ("#if GMP_LIMB_BITS != %d\n", limb_bits);
+ printf ("Error, error, this data is for %d bits\n", limb_bits);
+ printf ("#endif\n");
+ printf ("\n");
+ printf ("#define PRIMESIEVE_INIT_TABLE ");
+
+ maxprime = 3;
+ lb = pc = c = totpc = 0;
+ for (i = 0; i < limit; i++)
+ {
+ if (! isprime (bit_to_n (i)))
+ mpz_setbit (limb, lb);
+ else
+ maxprime = bit_to_n (i), ++pc;
+ ++lb;
+ if (lb == limb_bits)
+ {
+ ++c;
+ printf ("\\\n\tCNST_LIMB (0x");
+ mpz_out_str (stdout, -16, limb);
+ printf ("),\t/* %d - %d (%d primes) */\t", bit_to_n (i + 1 - limb_bits),
+ bit_to_n (i + 1) - 1, pc);
+ totpc += pc;
+ lb = pc = 0;
+ mpz_set_ui (limb, 0);
+ }
+ }
+
+ if ((mpz_sgn (limb) | lb | pc) != 0)
+ {
+ printf ("\ngen-sieve: Internal error, during generate (%d, %d).\n", limb_bits, limit);
+ abort();
+ }
+
+ mpz_clear (limb);
+
+ printf ("\n");
+ printf ("#define PRIMESIEVE_NUMBEROF_TABLE %d\n", c);
+
+ printf ("/* #define PRIMESIEVE_PRIMES_IN_TABLE %d */\n", totpc);
+ printf ("/* #define PRIMESIEVE_HIGHEST_PRIME %d */\n", maxprime);
+ printf ("/* #define PRIMESIEVE_FIRST_UNCHECKED %d */\n", bit_to_n (limit));
+
+ return c;
+}
+
+/* 5*2 = 10
+ 7*2 = 14
+ 5*7*2 = 70 (2*35, 3*24, 4*18, 5*14...)
+ 5*11*2 = 110 (2*55, 3*37, 4*28, 5*22...)
+ 5*13*2 = 130 (2*65, 3*44, 4*33, 5*26...)
+ 7*11*2 = 154 (2*77, 3*52, 4*39, 5*31...)
+ 7*13*2 = 182 (2*91, 3*61, 4*46, 5*37...)
+*/
+
+int
+main (int argc, char *argv[])
+{
+ int limb_bits, limit;
+
+ if (argc != 2)
+ {
+ fprintf (stderr, "Usage: gen-sieve <limbbits>\n");
+ exit (1);
+ }
+
+ limb_bits = atoi (argv[1]);
+
+ limit = 64 * 28; /* bits in the presieved sieve */
+ if (limit % limb_bits != 0)
+ limit += limb_bits - limit % limb_bits;
+ generate (limb_bits, limit);
+
+ return 0;
+}
diff -r 0140c03f9c72 -r d13fbd898d4e gmp-impl.h
--- a/gmp-impl.h Sun Sep 26 13:56:41 2021 +0200
+++ b/gmp-impl.h Fri Oct 01 22:58:49 2021 +0200
@@ -146,6 +146,7 @@
#include "gmp-mparam.h"
#include "fib_table.h"
#include "fac_table.h"
+#include "sieve_table.h"
#include "mp_bases.h"
#if WANT_FAT_BINARY
#include "fat.h"
diff -r 0140c03f9c72 -r d13fbd898d4e mini-gmp/ChangeLog
--- a/mini-gmp/ChangeLog Sun Sep 26 13:56:41 2021 +0200
+++ b/mini-gmp/ChangeLog Fri Oct 01 22:58:49 2021 +0200
@@ -1,3 +1,8 @@
+2021-10-01 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mini-gmp.c: Add asserts (removed at compile time) on limb size.
+ * mini-mpq.c: Add #defines needed if mini-gmp.h is not included.
+
2021-08-02 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mini-gmp.c (mpz_rootrem): Better initial guess.
diff -r 0140c03f9c72 -r d13fbd898d4e mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Sun Sep 26 13:56:41 2021 +0200
+++ b/mini-gmp/mini-gmp.c Fri Oct 01 22:58:49 2021 +0200
@@ -148,6 +148,7 @@
mp_limb_t __x0, __x1, __x2, __x3; \
unsigned __ul, __vl, __uh, __vh; \
mp_limb_t __u = (u), __v = (v); \
+ assert (sizeof (unsigned) * 2 >= sizeof (mp_limb_t)); \
\
__ul = __u & GMP_LLIMB_MASK; \
__uh = __u >> (GMP_LIMB_BITS / 2); \
@@ -783,6 +784,7 @@
mp_limb_t p, ql;
unsigned ul, uh, qh;
+ assert (sizeof (unsigned) * 2 >= sizeof (mp_limb_t));
/* For notation, let b denote the half-limb base, so that B = b^2.
Split u1 = b uh + ul. */
ul = u1 & GMP_LLIMB_MASK;
diff -r 0140c03f9c72 -r d13fbd898d4e mini-gmp/mini-mpq.c
--- a/mini-gmp/mini-mpq.c Sun Sep 26 13:56:41 2021 +0200
+++ b/mini-gmp/mini-mpq.c Fri Oct 01 22:58:49 2021 +0200
@@ -45,6 +45,7 @@
/* Define macros and static functions already defined by mini-gmp.c */
#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT)
#define GMP_LIMB_HIGHBIT ((mp_limb_t) 1 << (GMP_LIMB_BITS - 1))
+#define GMP_LIMB_MAX ((mp_limb_t) ~ (mp_limb_t) 0)
#define GMP_NEG_CAST(T,x) (-((T)((x) + 1) - 1))
#define GMP_MIN(a, b) ((a) < (b) ? (a) : (b))
diff -r 0140c03f9c72 -r d13fbd898d4e primesieve.c
--- a/primesieve.c Sun Sep 26 13:56:41 2021 +0200
+++ b/primesieve.c Fri Oct 01 22:58:49 2021 +0200
@@ -190,15 +190,9 @@
#ifdef SIEVE_2MSK2
mp_limb_t m11, m12, m21, m22, m23;
- if (offset == 0) { /* This branch is not needed. */
- m11 = SIEVE_MASK1;
- m12 = SIEVE_MASKT;
- m21 = SIEVE_2MSK1;
- m22 = SIEVE_2MSK2;
- m23 = SIEVE_2MSKT;
- } else { /* correctly handle offset == 0... */
- m21 = offset % (11 * 5 * 2);
- SET_OFF1 (m11, m12, SIEVE_MASK1, SIEVE_MASKT, m21, 11 * 5 * 2);
+ { /* correctly handle offset == 0... */
+ mp_limb_t off1 = offset % (11 * 5 * 2);
+ SET_OFF1 (m11, m12, SIEVE_MASK1, SIEVE_MASKT, off1, 11 * 5 * 2);
offset %= 13 * 7 * 2;
SET_OFF2 (m21, m22, m23, SIEVE_2MSK1, SIEVE_2MSK2, SIEVE_2MSKT, offset, 13 * 7 * 2);
}
@@ -219,11 +213,7 @@
#ifdef SIEVE_MASK2
mp_limb_t mask, mask2, tail;
- if (offset == 0) { /* This branch is not needed. */
- mask = SIEVE_MASK1;
- mask2 = SIEVE_MASK2;
- tail = SIEVE_MASKT;
- } else { /* correctly handle offset == 0... */
+ { /* correctly handle offset == 0... */
offset %= 7 * 5 * 2;
SET_OFF2 (mask, mask2, tail, SIEVE_MASK1, SIEVE_MASK2, SIEVE_MASKT, offset, 7 * 5 * 2);
}
@@ -246,70 +236,6 @@
}
static void
-first_block_primesieve (mp_ptr bit_array, mp_limb_t n)
-{
- mp_size_t bits, limbs;
- mp_limb_t i;
-
- ASSERT (n > 4);
-
- bits = n_fto_bit(n);
- limbs = bits / GMP_LIMB_BITS;
-
- if (limbs != 0)
- i = fill_bitpattern (bit_array + 1, limbs, 0);
- bit_array[0] = SIEVE_SEED;
-
- if (n > SEED_LIMIT) {
- mp_limb_t mask, index;
-
- ASSERT (i < GMP_LIMB_BITS);
-
- if (n_cto_bit (SEED_LIMIT) < GMP_LIMB_BITS)
- i = 0;
- mask = CNST_LIMB(1) << i;
- index = 0;
- do {
- ++i;
- if ((bit_array[index] & mask) == 0)
- {
- mp_size_t step, lindex;
- mp_limb_t lmask;
- unsigned maskrot;
-
- step = id_to_n(i);
-/* lindex = n_to_bit(id_to_n(i)*id_to_n(i)); */
- lindex = i*(step+1)-1+(-(i&1)&(i+1));
-/* lindex = i*(step+1+(i&1))-1+(i&1); */
- if (lindex > bits)
- break;
-
- step <<= 1;
- maskrot = step % GMP_LIMB_BITS;
-
- lmask = CNST_LIMB(1) << (lindex % GMP_LIMB_BITS);
- do {
- bit_array[lindex / GMP_LIMB_BITS] |= lmask;
- lmask = lmask << maskrot | lmask >> (GMP_LIMB_BITS - maskrot);
- lindex += step;
- } while (lindex <= bits);
-
More information about the gmp-commit
mailing list