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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/143191ace2ff
changeset: 13957:143191ace2ff
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Tue Mar 01 19:14:49 2011 +0100
description:
Rewrite, as per Marc Glisse's suggestion.

details:   /var/hg/gmp/rev/d8d1be62260c
changeset: 13958:d8d1be62260c
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Tue Mar 01 19:14:53 2011 +0100
description:
*** empty log message ***

diffstat:

 ChangeLog     |    5 ++
 mpz/divegcd.c |  100 ++++++++++++++++++++++++++-------------------------------
 2 files changed, 51 insertions(+), 54 deletions(-)

diffs (155 lines):

diff -r 7e776bf3b094 -r d8d1be62260c ChangeLog
--- a/ChangeLog	Tue Mar 01 13:39:01 2011 +0100
+++ b/ChangeLog	Tue Mar 01 19:14:53 2011 +0100
@@ -1,3 +1,8 @@
+2011-03-01  Torbjorn Granlund  <tege at gmplib.org>
+
+	* mpz/divegcd.c: Rewrite, as per Marc Glisse's suggestion.  Also fix
+	problem with passing a longlong limb to a _ui function.
+
 2011-03-01  Niels Möller  <nisse at lysator.liu.se>
 
 	* mpn/sparc64/mod_1_4.c (mpn_mod_1s_4p_cps): Use udiv_rnnd_preinv
diff -r 7e776bf3b094 -r d8d1be62260c mpz/divegcd.c
--- a/mpz/divegcd.c	Tue Mar 01 13:39:01 2011 +0100
+++ b/mpz/divegcd.c	Tue Mar 01 19:14:53 2011 +0100
@@ -49,62 +49,77 @@
 mpz_divexact_by3 (mpz_ptr q, mpz_srcptr a)
 {
   mp_size_t  size = SIZ(a);
-  if (size == 0)
-    {
-      SIZ(q) = 0;
-      return;
-    }
-  else
-    {
-      mp_size_t  abs_size = ABS(size);
-      mp_ptr     qp;
+  mp_size_t  abs_size = ABS(size);
+  mp_ptr     qp;
 
-      MPZ_REALLOC (q, abs_size);
+  MPZ_REALLOC (q, abs_size);
 
-      qp = PTR(q);
-      mpn_bdiv_dbm1 (qp, PTR(a), abs_size, GMP_NUMB_MASK / 3);
+  qp = PTR(q);
+  mpn_bdiv_dbm1 (qp, PTR(a), abs_size, GMP_NUMB_MASK / 3);
 
-      abs_size -= (qp[abs_size-1] == 0);
-      SIZ(q) = (size>0 ? abs_size : -abs_size);
-    }
+  abs_size -= (qp[abs_size-1] == 0);
+  SIZ(q) = (size>0 ? abs_size : -abs_size);
 }
 #endif
+
 #if GMP_NUMB_BITS % 4 == 0
 static void
 mpz_divexact_by5 (mpz_ptr q, mpz_srcptr a)
 {
   mp_size_t  size = SIZ(a);
-  if (size == 0)
-    {
-      SIZ(q) = 0;
-      return;
-    }
-  else
-    {
-      mp_size_t  abs_size = ABS(size);
-      mp_ptr     qp;
+  mp_size_t  abs_size = ABS(size);
+  mp_ptr     qp;
 
-      MPZ_REALLOC (q, abs_size);
+  MPZ_REALLOC (q, abs_size);
 
-      qp = PTR(q);
-      mpn_bdiv_dbm1 (qp, PTR(a), abs_size, GMP_NUMB_MASK / 5);
+  qp = PTR(q);
+  mpn_bdiv_dbm1 (qp, PTR(a), abs_size, GMP_NUMB_MASK / 5);
 
-      abs_size -= (qp[abs_size-1] == 0);
-      SIZ(q) = (size>0 ? abs_size : -abs_size);
-    }
+  abs_size -= (qp[abs_size-1] == 0);
+  SIZ(q) = (size>0 ? abs_size : -abs_size);
 }
 #endif
 
+static void
+mpz_divexact_limb (mpz_ptr q, mpz_srcptr a, mp_limb_t d)
+{
+  mp_size_t  size = SIZ(a);
+  mp_size_t  abs_size = ABS(size);
+  mp_ptr     qp;
+
+  MPZ_REALLOC (q, abs_size);
+
+  qp = PTR(q);
+  mpn_divexact_1 (qp, PTR(a), abs_size, d);
+
+  abs_size -= (qp[abs_size-1] == 0);
+  SIZ(q) = (size>0 ? abs_size : -abs_size);
+}
+
 void
 mpz_divexact_gcd (mpz_ptr q, mpz_srcptr a, mpz_srcptr d)
 {
   ASSERT (mpz_sgn (d) > 0);
 
+  if (SIZ(a) == 0)
+    {
+      SIZ(q) = 0;
+      return;
+    }
+
   if (SIZ(d) == 1)
     {
       mp_limb_t  dl = PTR(d)[0];
       int        twos;
 
+      if ((dl & 1) == 0)
+	{
+	  count_trailing_zeros (twos, dl);
+	  dl >>= twos;
+	  mpz_tdiv_q_2exp (q, a, twos);
+	  a = q;
+	}
+
       if (dl == 1)
 	{
 	  if (q != a)
@@ -126,30 +141,7 @@
 	}
 #endif
 
-      count_trailing_zeros (twos, dl);
-      dl >>= twos;
-      mpz_tdiv_q_2exp (q, a, twos);
-
-      if (dl == 1)
-	{
-	  return;
-	}
-#if GMP_NUMB_BITS % 2 == 0
-      if (dl == 3)
-	{
-	  mpz_divexact_by3 (q, q);
-	  return;
-	}
-#endif
-#if GMP_NUMB_BITS % 4 == 0
-      if (dl == 5)
-	{
-	  mpz_divexact_by5 (q, q);
-	  return;
-	}
-#endif
-
-      mpz_divexact_ui (q, q, dl);
+      mpz_divexact_limb (q, a, dl);
       return;
     }