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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/1dde68b6b7fc
changeset: 15017:1dde68b6b7fc
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Mon May 28 10:32:37 2012 +0200
description:
Simplified compute_v carry handling.

details:   /var/hg/gmp/rev/eeff898dd3a6
changeset: 15018:eeff898dd3a6
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Mon May 28 10:33:01 2012 +0200
description:
Fixed comment typo.

diffstat:

 ChangeLog            |   6 ++++++
 mpn/generic/gcd.c    |   2 +-
 mpn/generic/gcdext.c |  21 ++++++++++-----------
 3 files changed, 17 insertions(+), 12 deletions(-)

diffs (89 lines):

diff -r 2757606ce063 -r eeff898dd3a6 ChangeLog
--- a/ChangeLog	Mon May 28 00:37:51 2012 +0200
+++ b/ChangeLog	Mon May 28 10:33:01 2012 +0200
@@ -1,3 +1,9 @@
+2012-05-28  Niels Möller  <nisse at lysator.liu.se>
+
+	* mpn/generic/gcdext.c (compute_v): Simplified carry handling a
+	bit, reduced stated scratch need from 2n+1 to 2n. Also comment and
+	ASSERT improvements.
+
 2012-05-27  Torbjorn Granlund  <tege at gmplib.org>
 
 	* config.guess: Add new x86 CPUs.
diff -r 2757606ce063 -r eeff898dd3a6 mpn/generic/gcd.c
--- a/mpn/generic/gcd.c	Mon May 28 00:37:51 2012 +0200
+++ b/mpn/generic/gcd.c	Mon May 28 10:33:01 2012 +0200
@@ -241,7 +241,7 @@
 	  vl = MPN_EXTRACT_NUMB (shift, vp[n-2], vp[n-3]);
 	}
 
-      /* Try an mpn_nhgcd2 step */
+      /* Try an mpn_hgcd2 step */
       if (mpn_hgcd2 (uh, ul, vh, vl, &M))
 	{
 	  n = mpn_matrix22_mul1_inverse_vector (&M, tp, up, vp, n);
diff -r 2757606ce063 -r eeff898dd3a6 mpn/generic/gcdext.c
--- a/mpn/generic/gcdext.c	Mon May 28 00:37:51 2012 +0200
+++ b/mpn/generic/gcdext.c	Mon May 28 10:33:01 2012 +0200
@@ -85,10 +85,10 @@
   return n;
 }
 
-#define COMPUTE_V_ITCH(n) (2*(n) + 1)
+#define COMPUTE_V_ITCH(n) (2*(n))
 
 /* Computes |v| = |(g - u a)| / b, where u may be positive or
-   negative, and v is of the opposite sign. a, b are of size n, u and
+   negative, and v is of the opposite sign. max(a, b) is of size n, u and
    v at most size n, and v must have space for n+1 limbs. */
 static mp_size_t
 compute_v (mp_ptr vp,
@@ -108,9 +108,11 @@
 
   size = ABS (usize);
   ASSERT (size <= n);
+  ASSERT (up[size-1] > 0);
 
   an = n;
   MPN_NORMALIZE (ap, an);
+  ASSERT (gn <= an);
 
   if (an >= size)
     mpn_mul (tp, ap, an, up, size);
@@ -118,9 +120,6 @@
     mpn_mul (tp, up, size, ap, an);
 
   size += an;
-  size -= tp[size - 1] == 0;
-
-  ASSERT (gn <= size);
 
   if (usize > 0)
     {
@@ -132,11 +131,11 @@
 	return 0;
     }
   else
-    { /* usize < 0 */
-      /* |v| = v = (c - u a) / b = (c + |u| a) / b */
-      mp_limb_t cy = mpn_add (tp, tp, size, gp, gn);
-      if (cy)
-	tp[size++] = cy;
+    { /* |v| = v = (g - u a) / b = (g + |u| a) / b. Since g <= a,
+	 (g + |u| a) always fits in (|usize| + an) limbs. */
+      
+      ASSERT_NOCARRY (mpn_add (tp, tp, size, gp, gn));
+      size -= (tp[size - 1] == 0);
     }
 
   /* Now divide t / b. There must be no remainder */
@@ -170,7 +169,7 @@
    For the lehmer call after the loop, Let T denote
    GCDEXT_DC_THRESHOLD. For the gcdext_lehmer call, we need T each for
    u, a and b, and 4T+3 scratch space. Next, for compute_v, we need T
-   for u, T+1 for v and 2T + 1 scratch space. In all, 7T + 3 is
+   for u, T+1 for v and 2T scratch space. In all, 7T + 3 is
    sufficient for both operations.
 
 */