[Gmp-commit] /home/hgfiles/gmp: Interface change, require an >= bn in mpn_mul...

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/331dcec2adce
changeset: 13022:331dcec2adce
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Thu Dec 10 14:59:23 2009 +0100
description:
Interface change, require an >= bn in mpn_mulmod_bnm1.

diffstat:

 ChangeLog                 |   6 ++++++
 mpn/generic/mulmod_bnm1.c |  11 ++++-------
 tests/mpn/t-mulmod_bnm1.c |  18 +++++++++++-------
 3 files changed, 21 insertions(+), 14 deletions(-)

diffs (101 lines):

diff -r 4cd499b57d36 -r 331dcec2adce ChangeLog
--- a/ChangeLog	Thu Dec 10 13:16:39 2009 +0100
+++ b/ChangeLog	Thu Dec 10 14:59:23 2009 +0100
@@ -1,5 +1,11 @@
 2009-12-10  Niels Möller  <nisse at lysator.liu.se>
 
+	* tests/mpn/t-mulmod_bnm1.c (main): Ensure thatn an >= bn. Lowered
+	MIN_N to 1. Various fixes to handle n == 1 properly.
+
+	* mpn/generic/mulmod_bnm1.c (mpn_mulmod_bnm1): Small interface
+	change, require an >= bn.
+
 	* mpn/generic/mulmod_bnm1.c (mpn_mulmod_bnm1): Fixed non-recursive
 	case to not write beyond end of result area.
 
diff -r 4cd499b57d36 -r 331dcec2adce mpn/generic/mulmod_bnm1.c
--- a/mpn/generic/mulmod_bnm1.c	Thu Dec 10 13:16:39 2009 +0100
+++ b/mpn/generic/mulmod_bnm1.c	Thu Dec 10 14:59:23 2009 +0100
@@ -70,7 +70,7 @@
 
 
 /* Computes {rp,rn} <- {ap,an}*{bp,bn} Mod(B^rn-1)
- * Requires both an and bn <= rn
+ * Requires both 0 < bn <= an <= rn
  * Scratch need: rn + 2 + (need for recursive call OR rn + 2). This gives
  *
  * S(n) <= rn + 2 + MAX (rn + 2, S(n/2)) <= 2rn + 2 log2 rn + 2
@@ -87,15 +87,12 @@
 void
 mpn_mulmod_bnm1 (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn, mp_ptr tp)
 {
-  ASSERT (0 < an && an <= rn);
-  ASSERT (0 < bn && bn <= rn);
-  ASSERT (0 < rn);
+  ASSERT (0 < bn);
+  ASSERT (bn <= an);
+  ASSERT (an <= rn);
 
   if ((rn & 1) != 0 || BELOW_THRESHOLD (rn, MULMOD_BNM1_THRESHOLD))
     {
-      /* FIXME: We depend on an >= bn, this should be an official
-	 requirement. */
-      ASSERT (bn <= an);
       if (UNLIKELY (bn < rn))
 	{
 	  if (UNLIKELY (an + bn <= rn))
diff -r 4cd499b57d36 -r 331dcec2adce tests/mpn/t-mulmod_bnm1.c
--- a/tests/mpn/t-mulmod_bnm1.c	Thu Dec 10 13:16:39 2009 +0100
+++ b/tests/mpn/t-mulmod_bnm1.c	Thu Dec 10 14:59:23 2009 +0100
@@ -35,7 +35,7 @@
 #endif
 
 #define MAX_N (1L << SIZE_LOG)
-#define MIN_N MULMOD_BNM1_THRESHOLD
+#define MIN_N 1
 
 /*
   Reference function for multiplication modulo B^rn-1.
@@ -82,7 +82,7 @@
 int
 main (int argc, char **argv)
 {
-  mp_ptr ap, ac, bp, bc, refp, pp, scratch;
+  mp_ptr ap, bp, refp, pp, scratch;
   int count = COUNT;
   int test;
   gmp_randstate_ptr rands;
@@ -134,16 +134,20 @@
       if (test & 1) {
 	/* Half of the tests are done with the main scenario in mind:
 	   both an and bn >= rn/2 */
-	an = (n >> 1) + gmp_urandomm_ui (rands, n >> 1);
-	bn = (n >> 1) + gmp_urandomm_ui (rands, n >> 1);
+	an = ((n+1) >> 1) + gmp_urandomm_ui (rands, (n+1) >> 1);
+	bn = ((n+1) >> 1) + gmp_urandomm_ui (rands, (n+1) >> 1);
       } else {
 	/* Second half of the tests are done using mulmod to compute a
 	   full product and an >= bn > 0; recursion make it eventually
 	   fall in the case above. */
-	an = (n >> 2) + gmp_urandomm_ui (rands, n - (n >> 2));
-	bn = 1 + gmp_urandomm_ui (rands, an - 1);
+	an = ((n+3) >> 2) + gmp_urandomm_ui (rands, n - (n >> 2));	
+	bn = 1 + ((an == 1) ? 0 : gmp_urandomm_ui (rands, an - 1));
       }
 
+      /* Make sure an >= bn */
+      if (an < bn)
+	MP_SIZE_T_SWAP (an, bn);
+
       mpn_random2 (ap, an);
       mpn_random2 (bp, bn);
 
@@ -154,7 +158,7 @@
 	MPN_ZERO (ap + an - (n >> 1) , n - an);
 	MPN_COPY (bp, bp + (n >> 1), bn - (n >> 1));
 	MPN_ZERO (bp + bn - (n >> 1) , n - bn);
-	x = gmp_urandomm_ui (rands, n - an);
+	x = (n == an) ? 0 : gmp_urandomm_ui (rands, n - an);
 	ap[x] += gmp_urandomm_ui (rands, 3) - 1;
 	x = (n >> 1) - x % (n >> 1);
 	bp[x] += gmp_urandomm_ui (rands, 3) - 1;