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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/c6bfed1659e0
changeset: 14830:c6bfed1659e0
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Sun Apr 15 23:51:48 2012 +0200
description:
tests/mpz/t-bin.c: Add more tests on small values.

details:   /var/hg/gmp/rev/9ce3e243a240
changeset: 14831:9ce3e243a240
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Sun Apr 15 23:54:08 2012 +0200
description:
mpz/bin_uiui.c (mpz_bdiv_bin_uiui): Smaller temporary areas.

diffstat:

 ChangeLog         |   5 +++
 mpz/bin_uiui.c    |   7 ++-
 tests/mpz/t-bin.c |  87 ++++++++++++++++++++++++------------------------------
 3 files changed, 47 insertions(+), 52 deletions(-)

diffs (155 lines):

diff -r dbf44b5ce670 -r 9ce3e243a240 ChangeLog
--- a/ChangeLog	Sun Apr 15 16:02:37 2012 +0200
+++ b/ChangeLog	Sun Apr 15 23:54:08 2012 +0200
@@ -1,3 +1,8 @@
+2012-04-15 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+	* tests/mpz/t-bin.c: Add more tests on small values.
+	* mpz/bin_uiui.c (mpz_bdiv_bin_uiui): Smaller temporary areas.
+
 2012-04-15  Torbjorn Granlund  <tege at gmplib.org>
 
 	* mpn/x86_64/fastsse/copyd-palignr.asm: New file.
diff -r dbf44b5ce670 -r 9ce3e243a240 mpz/bin_uiui.c
--- a/mpz/bin_uiui.c	Sun Apr 15 16:02:37 2012 +0200
+++ b/mpz/bin_uiui.c	Sun Apr 15 23:54:08 2012 +0200
@@ -198,9 +198,10 @@
 
   /* FIXME: This allocation might be insufficient, but is usually way too
      large.  */
-  alloc = SOME_THRESHOLD + MAX (3 * maxn / 2, SOME_THRESHOLD);
+  alloc = SOME_THRESHOLD - 1 + MAX (3 * maxn / 2, SOME_THRESHOLD);
+  alloc = MIN (alloc, k) + 1;
   np = TMP_ALLOC_LIMBS (alloc);
-  kp = TMP_ALLOC_LIMBS (alloc);
+  kp = TMP_ALLOC_LIMBS (SOME_THRESHOLD + 1);
 
   MAXFACS (nmax, n);
   nmax = MIN (nmax, M);
@@ -232,7 +233,7 @@
       t = k - j + 1;
       kmax = MIN (kmax, t);
 
-      while (kmax != 0 && kn <  SOME_THRESHOLD)
+      while (kmax != 0 && kn < SOME_THRESHOLD)
 	{
 	  jjj = mulfunc[kmax] (j);
 	  j += kmax;				/* number of factors used */
diff -r dbf44b5ce670 -r 9ce3e243a240 tests/mpz/t-bin.c
--- a/tests/mpz/t-bin.c	Sun Apr 15 16:02:37 2012 +0200
+++ b/tests/mpz/t-bin.c	Sun Apr 15 23:54:08 2012 +0200
@@ -1,6 +1,6 @@
 /* Exercise mpz_bin_ui and mpz_bin_uiui.
 
-Copyright 2000, 2001, 2010 Free Software Foundation, Inc.
+Copyright 2000, 2001, 2010, 2012 Free Software Foundation, Inc.
 
 This file is part of the GNU MP Library.
 
@@ -77,55 +77,11 @@
     const char     *want;
   } data[] = {
 
-    {   "0",  0, "1"   },
-    {   "0",  1, "0"   },
-    {   "0",  2, "0"   },
-    {   "0",  3, "0"   },
-    {   "0",  4, "0"   },
     {   "0", 123456, "0" },
-
-    {   "1",  0, "1"   },
-    {   "1",  1, "1"   },
-    {   "1",  2, "0"   },
-    {   "1",  3, "0"   },
-    {   "1",  4, "0"   },
-    {   "1", 123456, "0" },
-
-    {   "2",  0, "1"   },
-    {   "2",  2, "1"   },
-    {   "2",  3, "0"   },
-    {   "2",  4, "0"   },
-    {   "2", 123456, "0" },
-
-    {   "3",  0, "1"   },
-    {   "3",  1, "3"   },
-    {   "3",  2, "3"   },
-    {   "3",  3, "1"   },
-    {   "3",  4, "0"   },
-    {   "3",  5, "0"   },
-    {   "3", 123456, "0" },
-
-    {   "4",  0, "1"   },
-    {   "4",  1, "4"   },
-    {   "4",  3, "4"   },
-    {   "4",  4, "1"   },
-    {   "4",  5, "0"   },
-    {   "4",  6, "0"   },
-    {   "4", 123456, "0" },
-
-    {   "10",  0, "1"   },
-    {   "10",  1, "10"  },
-    {   "10",  2, "45"  },
-    {   "10",  3, "120" },
-    {   "10",  4, "210" },
-    {   "10",  6, "210" },
-    {   "10",  7, "120" },
-    {   "10",  8, "45"  },
-    {   "10",  9, "10"  },
-    {   "10", 10, "1"   },
-    {   "10", 11,     "0" },
-    {   "10", 12,     "0" },
-    {   "10", 123456, "0" },
+    {   "1", 543210, "0" },
+    {   "2", 123321, "0" },
+    {   "3", 234567, "0" },
+    {   "10", 23456, "0" },
 
     /* negatives, using bin(-n,k)=bin(n+k-1,k) */
     {   "-1",  0,  "1"  },
@@ -250,6 +206,38 @@
   mpz_clear (want);
 }
 
+
+/* Test all bin(n,k) cases, with 0 <= k <= n + 1 <= count.  */
+void
+smallexaustive (unsigned int count)
+{
+  mpz_t          n_z, want;
+  unsigned long  n, k, i, r;
+  int            tests;
+  gmp_randstate_ptr rands;
+
+  mpz_init (n_z);
+  mpz_init (want);
+
+  for (n = 0; n < count; n++)
+    {
+      mpz_set_ui (want, (unsigned long) 1);
+      mpz_set_ui (n_z, n);
+      for (k = 0; k <= n; k++)
+	{
+	  try_mpz_bin_ui (want, n_z, k);
+	  try_mpz_bin_uiui (want, n, k);
+	  mpz_mul_ui (want, want, n - k);
+	  mpz_fdiv_q_ui (want, want, k + 1);
+	}
+      try_mpz_bin_ui (want, n_z, k);
+      try_mpz_bin_uiui (want, n, k);
+    }
+
+  mpz_clear (n_z);
+  mpz_clear (want);
+}
+
 int
 main (int argc, char **argv)
 {
@@ -271,6 +259,7 @@
   tests_start ();
 
   samples ();
+  smallexaustive (count >> 3);
   twos (count >> 1);
   randomwalk (count - (count >> 1));