[Gmp-commit] /var/hg/gmp: 2 new changesets

mercurial at gmplib.org mercurial at gmplib.org
Tue Apr 17 08:10:24 CEST 2012


details:   /var/hg/gmp/rev/8276b7a5cf49
changeset: 14842:8276b7a5cf49
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Tue Apr 17 08:02:34 2012 +0200
description:
mpz/bin_uiui.c: Support small limbs (fallback on bin_ui).

details:   /var/hg/gmp/rev/7293e8f73e2a
changeset: 14843:7293e8f73e2a
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Tue Apr 17 08:10:18 2012 +0200
description:
Re-enable mpz/t-toom?-sqr tests.

diffstat:

 ChangeLog                   |  12 ++++++++++++
 mpz/bin_uiui.c              |  15 ++++++++++++++-
 tests/mpn/Makefile.am       |   1 +
 tests/mpn/t-toom2-sqr.c     |   1 +
 tests/mpn/t-toom3-sqr.c     |   1 +
 tests/mpn/t-toom4-sqr.c     |   1 +
 tests/mpn/t-toom6-sqr.c     |   1 +
 tests/mpn/t-toom8-sqr.c     |   1 +
 tests/mpn/toom-sqr-shared.h |  19 +++----------------
 9 files changed, 35 insertions(+), 17 deletions(-)

diffs (171 lines):

diff -r f8e3d3517187 -r 7293e8f73e2a ChangeLog
--- a/ChangeLog	Tue Apr 17 00:35:57 2012 +0200
+++ b/ChangeLog	Tue Apr 17 08:10:18 2012 +0200
@@ -1,3 +1,15 @@
+2012-04-17 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+	* mpz/bin_uiui.c: Support small limbs (fallback on bin_ui).
+
+	* tests/mpn/toom-sqr-shared.h: Use a restricted range.
+	* tests/mpn/t-toom2-sqr.c: Specify correct range.
+	* tests/mpn/t-toom3-sqr.c: Likewise.
+	* tests/mpn/t-toom4-sqr.c: Likewise.
+	* tests/mpn/t-toom6-sqr.c: Likewise.
+	* tests/mpn/t-toom8-sqr.c: Likewise, but extended.
+	* tests/mpn/Makefile.am (check_PROGRAMS): Add t-toom?-sqr tests.
+
 2012-04-17  Torbjorn Granlund  <tege at gmplib.org>
 
 	* mpn/x86_64/copyd.asm: Rewrite.
diff -r f8e3d3517187 -r 7293e8f73e2a mpz/bin_uiui.c
--- a/mpz/bin_uiui.c	Tue Apr 17 00:35:57 2012 +0200
+++ b/mpz/bin_uiui.c	Tue Apr 17 08:10:18 2012 +0200
@@ -346,6 +346,9 @@
 
   mpn_pi1_bdiv_q_1 (rp, rp, rn, fac[k], facinv[k - 2],
 		    fac2cnt[k / 2 - 1] - i2cnt);
+  /* A two-fold, branch-free normalisation is possible :*/
+  /* rn -= rp[rn - 1] == 0; */
+  /* rn -= rp[rn - 1] == 0; */
   MPN_NORMALIZE_NOT_ZERO (rp, rn);
 
   SIZ(r) = rn;
@@ -426,17 +429,27 @@
   mpn_pi1_bdiv_q_1 (rp, rp, rn, bin2kk[k - ODD_CENTRAL_BINOMIAL_OFFSET],
 		    bin2kkinv[k - ODD_CENTRAL_BINOMIAL_OFFSET],
 		    fac2bin[k - ODD_CENTRAL_BINOMIAL_OFFSET] - (k != hk));
+  /* A two-fold, branch-free normalisation is possible :*/
+  /* rn -= rp[rn - 1] == 0; */
+  /* rn -= rp[rn - 1] == 0; */
   MPN_NORMALIZE_NOT_ZERO (rp, rn);
 
   SIZ(r) = rn;
 }
 
-/* WARNING: it assumes that n fits in a limb! */
 void
 mpz_bin_uiui (mpz_ptr r, unsigned long int n, unsigned long int k)
 {
   if (UNLIKELY (n < k)) {
     SIZ (r) = 0;
+#if BITS_PER_ULONG > GMP_NUMB_BITS
+  } else if (UNLIKELY (n > GMP_NUMB_MAX)) {
+    mpz_t tmp;
+
+    mpz_init_set_ui (tmp, n);
+    mpz_bin_ui (r, tmp, k);
+    mpz_clear (tmp);
+#endif
   } else {
     ASSERT (n <= GMP_NUMB_MAX);
     /* Rewrite bin(n,k) as bin(n,n-k) if that is smaller. */
diff -r f8e3d3517187 -r 7293e8f73e2a tests/mpn/Makefile.am
--- a/tests/mpn/Makefile.am	Tue Apr 17 00:35:57 2012 +0200
+++ b/tests/mpn/Makefile.am	Tue Apr 17 08:10:18 2012 +0200
@@ -26,6 +26,7 @@
   t-instrument t-iord_u t-mp_bases t-perfsqr t-scan logic		\
   t-toom22 t-toom32 t-toom33 t-toom42 t-toom43 t-toom44			\
   t-toom52 t-toom53 t-toom54 t-toom62 t-toom63 t-toom6h t-toom8h	\
+  t-toom2-sqr t-toom3-sqr t-toom4-sqr t-toom6-sqr t-toom8-sqr		\
   t-mul t-mullo t-mulmod_bnm1 t-sqrmod_bnm1 t-mulmid			\
   t-hgcd t-hgcd_appr t-matrix22 t-invert t-div t-bdiv
 
diff -r f8e3d3517187 -r 7293e8f73e2a tests/mpn/t-toom2-sqr.c
--- a/tests/mpn/t-toom2-sqr.c	Tue Apr 17 00:35:57 2012 +0200
+++ b/tests/mpn/t-toom2-sqr.c	Tue Apr 17 08:10:18 2012 +0200
@@ -1,5 +1,6 @@
 #define mpn_toomN_sqr mpn_toom2_sqr
 #define mpn_toomN_sqr_itch mpn_toom2_sqr_itch
 #define MIN_AN MPN_TOOM2_SQR_MINSIZE
+#define MAX_AN SQR_TOOM3_THRESHOLD
 
 #include "toom-sqr-shared.h"
diff -r f8e3d3517187 -r 7293e8f73e2a tests/mpn/t-toom3-sqr.c
--- a/tests/mpn/t-toom3-sqr.c	Tue Apr 17 00:35:57 2012 +0200
+++ b/tests/mpn/t-toom3-sqr.c	Tue Apr 17 08:10:18 2012 +0200
@@ -1,5 +1,6 @@
 #define mpn_toomN_sqr mpn_toom3_sqr
 #define mpn_toomN_sqr_itch mpn_toom3_sqr_itch
 #define MIN_AN MAX(SQR_TOOM3_THRESHOLD,MPN_TOOM3_SQR_MINSIZE)
+#define MAX_AN SQR_TOOM4_THRESHOLD
 
 #include "toom-sqr-shared.h"
diff -r f8e3d3517187 -r 7293e8f73e2a tests/mpn/t-toom4-sqr.c
--- a/tests/mpn/t-toom4-sqr.c	Tue Apr 17 00:35:57 2012 +0200
+++ b/tests/mpn/t-toom4-sqr.c	Tue Apr 17 08:10:18 2012 +0200
@@ -1,5 +1,6 @@
 #define mpn_toomN_sqr mpn_toom4_sqr
 #define mpn_toomN_sqr_itch mpn_toom4_sqr_itch
 #define MIN_AN MAX(SQR_TOOM4_THRESHOLD,MPN_TOOM4_SQR_MINSIZE)
+#define MAX_AN SQR_TOOM6_THRESHOLD
 
 #include "toom-sqr-shared.h"
diff -r f8e3d3517187 -r 7293e8f73e2a tests/mpn/t-toom6-sqr.c
--- a/tests/mpn/t-toom6-sqr.c	Tue Apr 17 00:35:57 2012 +0200
+++ b/tests/mpn/t-toom6-sqr.c	Tue Apr 17 08:10:18 2012 +0200
@@ -1,5 +1,6 @@
 #define mpn_toomN_sqr mpn_toom6_sqr
 #define mpn_toomN_sqr_itch mpn_toom6_sqr_itch
 #define MIN_AN MAX(SQR_TOOM6_THRESHOLD,MPN_TOOM6_SQR_MINSIZE)
+#define MAX_AN SQR_TOOM8_THRESHOLD
 
 #include "toom-sqr-shared.h"
diff -r f8e3d3517187 -r 7293e8f73e2a tests/mpn/t-toom8-sqr.c
--- a/tests/mpn/t-toom8-sqr.c	Tue Apr 17 00:35:57 2012 +0200
+++ b/tests/mpn/t-toom8-sqr.c	Tue Apr 17 08:10:18 2012 +0200
@@ -1,5 +1,6 @@
 #define mpn_toomN_sqr mpn_toom8_sqr
 #define mpn_toomN_sqr_itch mpn_toom8_sqr_itch
 #define MIN_AN MAX(SQR_TOOM8_THRESHOLD,MPN_TOOM8_SQR_MINSIZE)
+#define MAX_AN (SQR_FFT_THRESHOLD * 2)
 
 #include "toom-sqr-shared.h"
diff -r f8e3d3517187 -r 7293e8f73e2a tests/mpn/toom-sqr-shared.h
--- a/tests/mpn/toom-sqr-shared.h	Tue Apr 17 00:35:57 2012 +0200
+++ b/tests/mpn/toom-sqr-shared.h	Tue Apr 17 08:10:18 2012 +0200
@@ -26,19 +26,12 @@
 #include "tests.h"
 
 /* Main file is expected to define mpn_toomN_mul, mpn_toomN_sqr_itch,
- * MIN_AN and then include this file. */
-
-/* Sizes are up to 2^SIZE_LOG limbs */
-#ifndef SIZE_LOG
-#define SIZE_LOG 10
-#endif
+ * MIN_AN, MAX_AN and then include this file. */
 
 #ifndef COUNT
 #define COUNT 500
 #endif
 
-#define MAX_AN (1L << SIZE_LOG)
-
 int
 main (int argc, char **argv)
 {
@@ -69,6 +62,7 @@
   scratch
     = 1+TMP_ALLOC_LIMBS (mpn_toomN_sqr_itch (MAX_AN) + 2);
 
+  if (MAX_AN >= MIN_AN)
   for (test = 0; test < count; test++)
     {
       unsigned size_min;
@@ -77,15 +71,8 @@
       mp_size_t itch;
       mp_limb_t p_before, p_after, s_before, s_after;
 
-      for (size_min = 1; (1L << size_min) < MIN_AN; size_min++)
-	;
-
-      /* We generate an in the MIN_AN <= an <= (1 << size_range). */
-      size_range = size_min
-	+ gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min);
-
       an = MIN_AN
-	+ gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_AN);
+	+ gmp_urandomm_ui (rands, MAX_AN - MIN_AN);
 
       mpn_random2 (ap, an);
       mpn_random2 (pp-1, an * 2 + 2);


More information about the gmp-commit mailing list