[Gmp-commit] /var/hg/gmp: (mpn_gcdext): Deleted code for handling impossible ...

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/a99ae560d512
changeset: 15046:a99ae560d512
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Sun Jun 03 09:55:01 2012 +0200
description:
(mpn_gcdext): Deleted code for handling impossible case u1 == 0,
Simplified test for unlikely case u0 == 0.

diffstat:

 ChangeLog            |   5 ++++
 mpn/generic/gcdext.c |  59 ++++++++++++++++++++++-----------------------------
 2 files changed, 30 insertions(+), 34 deletions(-)

diffs (115 lines):

diff -r da34816982bf -r a99ae560d512 ChangeLog
--- a/ChangeLog	Sat Jun 02 19:09:24 2012 +0200
+++ b/ChangeLog	Sun Jun 03 09:55:01 2012 +0200
@@ -1,3 +1,8 @@
+2012-06-03  Niels Möller  <nisse at lysator.liu.se>
+
+	* mpn/generic/gcdext.c (mpn_gcdext): Deleted code for handling
+	impossible case u1 == 0, Simplified test for unlikely case u0 == 0.
+
 2012-06-02  Torbjorn Granlund  <tege at gmplib.org>
 
 	* mpn/arm/lshiftc.asm: New file.
diff -r da34816982bf -r a99ae560d512 mpn/generic/gcdext.c
--- a/mpn/generic/gcdext.c	Sat Jun 02 19:09:24 2012 +0200
+++ b/mpn/generic/gcdext.c	Sun Jun 03 09:55:01 2012 +0200
@@ -384,6 +384,26 @@
 	  ASSERT (un < ualloc);
 	}
     }
+  /* We have A = ... a + ... b
+	     B =  u0 a +  u1 b
+
+	     a = u1  A + ... B
+	     b = -u0 A + ... B
+
+     with bounds
+
+       |u0|, |u1| <= B / min(a, b)
+
+     We always have u1 > 0, and u0 == 0 is possible only if u1 == 1,
+     in which case the only reduction done so far is a = A - k B for
+     some k.
+	 
+     Compute g = u a + v b = (u u1 - v u0) A + (...) B
+     Here, u, v are bounded by
+
+       |u| <= b,
+       |v| <= a
+  */
 
   ASSERT ( (ap[n-1] | bp[n-1]) > 0);
 
@@ -415,10 +435,9 @@
       TMP_FREE;
       return n;
     }
-  else if (mpn_zero_p (u0, un))
+  else if (UNLIKELY (u0[0] == 0) && un == 1)
     {
       mp_size_t gn;
-      ASSERT (un == 1);
       ASSERT (u1[0] == 1);
 
       /* g = u a + v b = (u u1 - v u0) A + (...) B = u A + (...) B */
@@ -429,23 +448,6 @@
     }
   else
     {
-      /* We have A = ... a + ... b
-		 B =  u0 a +  u1 b
-
-		 a = u1  A + ... B
-		 b = -u0 A + ... B
-
-	 with bounds
-
-	   |u0|, |u1| <= B / min(a, b)
-
-	 Compute g = u a + v b = (u u1 - v u0) A + (...) B
-	 Here, u, v are bounded by
-
-	 |u| <= b,
-	 |v| <= a
-      */
-
       mp_size_t u0n;
       mp_size_t u1n;
       mp_size_t lehmer_un;
@@ -465,6 +467,8 @@
 
       u0n = un;
       MPN_NORMALIZE (u0, u0n);
+      ASSERT (u0n > 0);
+
       if (lehmer_un == 0)
 	{
 	  /* u == 0  ==>  v = g / b == 1  ==> g = - u0 A + (...) B */
@@ -490,25 +494,12 @@
 
       u1n = un;
       MPN_NORMALIZE (u1, u1n);
-
-      /* It's possible that u0 = 1, u1 = 0 */
-      if (u1n == 0)
-	{
-	  ASSERT (un == 1);
-	  ASSERT (u0[0] == 1);
-
-	  /* u1 == 0 ==> u u1 + v u0 = v */
-	  MPN_COPY (up, lehmer_vp, lehmer_vn);
-	  *usizep = negate ? lehmer_vn : - lehmer_vn;
-
-	  TMP_FREE;
-	  return gn;
-	}
+      ASSERT (u1n > 0);
 
       ASSERT (lehmer_un + u1n <= ualloc);
       ASSERT (lehmer_vn + u0n <= ualloc);
 
-      /* Now u0, u1, u are non-zero. We may still have v == 0 */
+      /* We may still have v == 0 */
 
       /* Compute u u0 */
       if (lehmer_un <= u1n)