[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