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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/d742dce030fa
changeset: 15458:d742dce030fa
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Feb 18 10:46:27 2013 +0100
description:
mini-gmp/mini-gmp.c (mpn_div_qr_1): Speed-up the d=1 case, delaying a branch.

details:   /var/hg/gmp/rev/596470e0bc62
changeset: 15459:596470e0bc62
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Feb 18 10:57:37 2013 +0100
description:
mpz/remove.c: Delay allocation in the generic case; use swap instead of set.

diffstat:

 ChangeLog           |   4 ++
 mini-gmp/mini-gmp.c |  16 +++++++---
 mpz/remove.c        |  75 +++++++++++++++++++++++++++++++++-------------------
 3 files changed, 62 insertions(+), 33 deletions(-)

diffs (147 lines):

diff -r 8bb2cde2a534 -r 596470e0bc62 ChangeLog
--- a/ChangeLog	Mon Feb 18 10:29:46 2013 +0100
+++ b/ChangeLog	Mon Feb 18 10:57:37 2013 +0100
@@ -11,10 +11,14 @@
 	(mpz_rootrem): Use _init2 before _setbit.
 	(mpz_set_str): Optimise-out a variable.
 	(mpz_import): Normalise only if needed.
+	(mpn_div_qr_1): Speed-up the d=1 case, delaying a branch.
 
 	* rand/randmts.c: Use init2, as size of variables is known in advance.
 	(mangle_seed): Get a single argument.
 
+	* mpz/remove.c: Delay allocation in the generic case; use swap
+	instead of set.
+
 2013-02-17  Marc Glisse  <marc.glisse at inria.fr>
 
 	* cxx/osdoprnti.cc: Use <stdarg.h> and <string.h> rather than <cstdarg>
diff -r 8bb2cde2a534 -r 596470e0bc62 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c	Mon Feb 18 10:29:46 2013 +0100
+++ b/mini-gmp/mini-gmp.c	Mon Feb 18 10:57:37 2013 +0100
@@ -831,14 +831,20 @@
   assert (d > 0);
 
   /* Special case for powers of two. */
-  if (d > 1 && (d & (d-1)) == 0)
+  if ((d & (d-1)) == 0)
     {
-      unsigned shift;
       mp_limb_t r = np[0] & (d-1);
-      gmp_ctz (shift, d);
       if (qp)
-	mpn_rshift (qp, np, nn, shift);
-
+	{
+	  if (d <= 1)
+	    mpn_copyi (qp, np, nn);
+	  else
+	    {
+	      unsigned shift;
+	      gmp_ctz (shift, d);
+	      mpn_rshift (qp, np, nn, shift);
+	    }
+	}
       return r;
     }
   else
diff -r 8bb2cde2a534 -r 596470e0bc62 mpz/remove.c
--- a/mpz/remove.c	Mon Feb 18 10:29:46 2013 +0100
+++ b/mpz/remove.c	Mon Feb 18 10:57:37 2013 +0100
@@ -65,49 +65,68 @@
     }
   else
     { /* f != +-2 */
-      mpz_t fpow[GMP_LIMB_BITS];		/* Really MP_SIZE_T_BITS */
       mpz_t x, rem;
-      int p;
-
-      /* We could perhaps compute mpz_scan1(src,0)/mpz_scan1(f,0).  It is an
-	 upper bound of the result we're seeking.  We could also shift down the
-	 operands so that they become odd, to make intermediate values
-	 smaller.  */
 
       mpz_init (rem);
       mpz_init (x);
 
       pwr = 0;
-      mpz_init_set (fpow[0], f);
-      mpz_set (dest, src);
+      mpz_tdiv_qr (x, rem, src, f);
+      if (SIZ (rem) == 0)
+	{
+	  mpz_t fpow[GMP_LIMB_BITS];		/* Really MP_SIZE_T_BITS */
+	  int p;
 
+#if WANT_ORIGINAL_DEST
+	  mp_ptr dp;
+	  dp = PTR (dest);
+#endif
+      /* We could perhaps compute mpz_scan1(src,0)/mpz_scan1(f,0).  It is an
+	 upper bound of the result we're seeking.  We could also shift down the
+	 operands so that they become odd, to make intermediate values
+	 smaller.  */
+	  mpz_init_set (fpow[0], f);
+	  mpz_swap (dest, x);
+
+	  p = 1;
       /* Divide by f, f^2 ... f^(2^k) until we get a remainder for f^(2^k).  */
-      for (p = 0;; p++)
-	{
-	  mpz_tdiv_qr (x, rem, dest, fpow[p]);
-	  if (SIZ (rem) != 0)
-	    break;
-	  mpz_init (fpow[p + 1]);
-	  mpz_mul (fpow[p + 1], fpow[p], fpow[p]);
-	  mpz_set (dest, x);
-	}
+	  while (ABSIZ (dest) >= 2 * ABSIZ (fpow[p - 1]) - 1)
+	    {
+	      mpz_init (fpow[p]);
+	      mpz_mul (fpow[p], fpow[p - 1], fpow[p - 1]);
+	      mpz_tdiv_qr (x, rem, dest, fpow[p]);
+	      if (SIZ (rem) != 0) {
+		mpz_clear (fpow[p]);
+		break;
+	      }
+	      mpz_swap (dest, x);
+	      p++;
+	    }
 
-      pwr = ((mp_bitcnt_t)1 << p) - 1;
-
-      mpz_clear (fpow[p]);
+	  pwr = ((mp_bitcnt_t)1 << p) - 1;
 
       /* Divide by f^(2^(k-1)), f^(2^(k-2)), ..., f for all divisors that give
 	 a zero remainder.  */
-      while (--p >= 0)
-	{
-	  mpz_tdiv_qr (x, rem, dest, fpow[p]);
-	  if (SIZ (rem) == 0)
+	  while (--p >= 0)
 	    {
-	      pwr += (mp_bitcnt_t)1 << p;
-	      mpz_set (dest, x);
+	      mpz_tdiv_qr (x, rem, dest, fpow[p]);
+	      if (SIZ (rem) == 0)
+		{
+		  pwr += (mp_bitcnt_t)1 << p;
+		  mpz_swap (dest, x);
+		}
+	      mpz_clear (fpow[p]);
 	    }
-	  mpz_clear (fpow[p]);
+
+#if WANT_ORIGINAL_DEST
+	  if (PTR (x) == dp) {
+	    mpz_swap (dest, x);
+	    mpz_set (dest, x);
+	  }
+#endif
 	}
+      else
+	mpz_set (dest, src);
 
       mpz_clear (x);
       mpz_clear (rem);