[Gmp-commit] /home/hgfiles/gmp: Fixes for mpn_gcdext_1 with a < b.

mercurial at gmplib.org mercurial at gmplib.org
Thu Dec 3 19:14:25 CET 2009


details:   /home/hgfiles/gmp/rev/f48329882a7b
changeset: 12971:f48329882a7b
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Thu Dec 03 19:13:46 2009 +0100
description:
Fixes for mpn_gcdext_1 with a < b.

diffstat:

 ChangeLog                   |   7 +++++++
 mpn/generic/gcdext_1.c      |   7 +++++--
 mpn/generic/gcdext_lehmer.c |  11 +++++++++--
 3 files changed, 21 insertions(+), 4 deletions(-)

diffs (65 lines):

diff -r eb98bbab31f4 -r f48329882a7b ChangeLog
--- a/ChangeLog	Thu Dec 03 16:43:17 2009 +0100
+++ b/ChangeLog	Thu Dec 03 19:13:46 2009 +0100
@@ -1,3 +1,10 @@
+2009-12-03  Niels Möller  <nisse at lysator.liu.se>
+
+	* mpn/generic/gcdext_lehmer.c (mpn_gcdext_lehmer_n): Handle v == 0
+	from mpn_gcdext_1.
+	* mpn/generic/gcdext_1.c (mpn_gcdext_1): Allow inputs with a < b,
+	assertions fixed accordingly.
+
 2009-12-03  Torbjorn Granlund  <tege at gmplib.org>
 
 	* tune/tuneup.c: Tune DC_DIVAPPR_Q_THRESHOLD.  Rewrite
diff -r eb98bbab31f4 -r f48329882a7b mpn/generic/gcdext_1.c
--- a/mpn/generic/gcdext_1.c	Thu Dec 03 16:43:17 2009 +0100
+++ b/mpn/generic/gcdext_1.c	Thu Dec 03 19:13:46 2009 +0100
@@ -42,10 +42,12 @@
   mp_limb_signed_t u1 = 0;
   mp_limb_signed_t v1 = 1;
 
-  ASSERT (a >= b);
+  ASSERT (a > 0);
   ASSERT (b > 0);
 
-  /* FIXME: Use div1. */
+  if (a < b)
+    goto divide_by_b;
+
   for (;;)
     {
       mp_limb_t q;
@@ -62,6 +64,7 @@
       u0 -= q * u1;
       v0 -= q * v1;
 
+    divide_by_b:
       q = b / a;
       b -= q * a;
 
diff -r eb98bbab31f4 -r f48329882a7b mpn/generic/gcdext_lehmer.c
--- a/mpn/generic/gcdext_lehmer.c	Thu Dec 03 16:43:17 2009 +0100
+++ b/mpn/generic/gcdext_lehmer.c	Thu Dec 03 19:13:46 2009 +0100
@@ -169,12 +169,19 @@
 	  *usize = -un;
 	  return 1;
 	}
-
+      else if (v == 0)
+	{
+	  ASSERT (u == 1);
+	  MPN_NORMALIZE (u1, un);
+	  MPN_COPY (up, u1, un);
+	  *usize = un;
+	  return 1;
+	}
       else if (u > 0)
 	{
 	  negate = 0;
 	  ASSERT (v < 0);
-	  v= -v;
+	  v = -v;
 	}
       else
 	{


More information about the gmp-commit mailing list