[Gmp-commit] /home/hgfiles/gmp: Allocation improvements, and a special case f...

[mercurial at gmplib.org]

details:   /home/hgfiles/gmp/rev/a43049d48245
changeset: 13116:a43049d48245
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Thu Dec 17 17:26:42 2009 +0100
description:
Allocation improvements, and a special case for dn == 1.

diffstat:

 ChangeLog              |   5 +++++
 mpn/generic/divexact.c |  46 ++++++++++++++++++++++++----------------------
 2 files changed, 29 insertions(+), 22 deletions(-)

diffs (96 lines):

diff -r 7ec6dba53d54 -r a43049d48245 ChangeLog
--- a/ChangeLog	Thu Dec 17 17:06:47 2009 +0100
+++ b/ChangeLog	Thu Dec 17 17:26:42 2009 +0100
@@ -13,6 +13,11 @@
 
 2009-12-17  Niels Möller  <nisse at lysator.liu.se>
 
+	* mpn/generic/divexact.c (mpn_divexact): Don't require that the
+	dividend is normalized. Use MPN_DIVREM_OR_PREINV_DIVREM_1. When
+	shifting, allocate and process only the low qn+1 limbs. Eliminated
+	code for the impossible case nn < qn.
+
 	* mpn/generic/dcpi1_div_qr.c (mpn_dcpi1_div_qr): Added some input
 	asserts.
 
diff -r 7ec6dba53d54 -r a43049d48245 mpn/generic/divexact.c
--- a/mpn/generic/divexact.c	Thu Dec 17 17:06:47 2009 +0100
+++ b/mpn/generic/divexact.c	Thu Dec 17 17:26:42 2009 +0100
@@ -38,15 +38,12 @@
 {
   unsigned shift;
   mp_size_t qn;
-  mp_ptr tp;
+  mp_ptr tp, wp;
   TMP_DECL;
 
   ASSERT (dn > 0);
   ASSERT (nn >= dn);
   ASSERT (dp[dn-1] > 0);
-  ASSERT (np[nn-1] > 0);
-
-  qn = nn + 1 - dn;
 
   while (dp[0] == 0)
     {
@@ -56,37 +53,42 @@
       dn--;
       nn--;
     }
+
+  if (dn == 1)
+    {
+      MPN_DIVREM_OR_DIVEXACT_1 (qp, np, nn, dp[0]);
+      return;
+    }
+
+  TMP_MARK;
+
+  qn = nn + 1 - dn;
   count_trailing_zeros (shift, dp[0]);
 
-  TMP_MARK;
   if (shift > 0)
     {
-      tp = TMP_ALLOC_LIMBS (dn);
-      mpn_rshift (tp, dp, dn, shift);
+      mp_size_t ss = (dn > qn) ? qn + 1 : dn;
+
+      tp = TMP_ALLOC_LIMBS (ss);
+      mpn_rshift (tp, dp, ss, shift);
       dp = tp;
 
-      /* FIXME: It's sufficient to get the qn least significant
-	 limbs. */
-      tp = TMP_ALLOC_LIMBS (nn);
-      mpn_rshift (tp, np, nn, shift);
-      np = tp;
+      /* Since we have excluded dn == 1, we have nn > qn, and we need
+	 to shift one limb beyond qn. */
+      wp = TMP_ALLOC_LIMBS (qn + 1);
+      mpn_rshift (wp, np, qn + 1, shift);
     }
   else
     {
-      mp_ptr tp = TMP_ALLOC_LIMBS (qn);
-      MPN_COPY (tp, np, qn);
-      np = tp;
+      wp = TMP_ALLOC_LIMBS (qn);
+      MPN_COPY (wp, np, qn);
     }
-  if (nn > qn)
-    nn = qn;
+
   if (dn > qn)
     dn = qn;
 
-  if (qn > nn)
-    MPN_ZERO (qp + nn, qn - nn);
-
-  tp = TMP_ALLOC_LIMBS (mpn_bdiv_q_itch (nn, dn));
-  mpn_bdiv_q (qp, np, nn, dp, dn, tp);
+  tp = TMP_ALLOC_LIMBS (mpn_bdiv_q_itch (qn, dn));
+  mpn_bdiv_q (qp, wp, qn, dp, dn, tp);
   TMP_FREE;
 }