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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/15787a10700d
changeset: 16436:15787a10700d
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Sun Jun 15 01:26:06 2014 +0200
description:
(refmpn_mul): Rewrite to avoid O(n) recursion depth.

details:   /var/hg/gmp/rev/4942270f8f2a
changeset: 16437:4942270f8f2a
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Sun Jun 15 01:27:26 2014 +0200
description:
ChangeLog

diffstat:

 ChangeLog      |   4 ++
 tests/refmpn.c |  80 ++++++++++++++++++++++++++++-----------------------------
 2 files changed, 43 insertions(+), 41 deletions(-)

diffs (126 lines):

diff -r b315de004ea1 -r 4942270f8f2a ChangeLog
--- a/ChangeLog	Mon Jun 09 14:46:00 2014 +0200
+++ b/ChangeLog	Sun Jun 15 01:27:26 2014 +0200
@@ -1,3 +1,7 @@
+2014-06-15  Torbjörn Granlund  <tege at gmplib.org>
+
+	* tests/refmpn.c (refmpn_mul): Rewrite to avoid O(n) recursion depth.
+
 2014-06-09  Torbjörn Granlund  <tege at gmplib.org>
 
 	* mpn/generic/mullo_n.c: Remove default THRESHOLDs.
diff -r b315de004ea1 -r 4942270f8f2a tests/refmpn.c
--- a/tests/refmpn.c	Mon Jun 09 14:46:00 2014 +0200
+++ b/tests/refmpn.c	Sun Jun 15 01:27:26 2014 +0200
@@ -1,7 +1,7 @@
 /* Reference mpn functions, designed to be simple, portable and independent
    of the normal gmp code.  Speed isn't a consideration.
 
-Copyright 1996-2009, 2011-2013 Free Software Foundation, Inc.
+Copyright 1996-2009, 2011-2014 Free Software Foundation, Inc.
 
 This file is part of the GNU MP Library test suite.
 
@@ -1863,12 +1863,12 @@
 void
 refmpn_mul (mp_ptr wp, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
 {
-  mp_ptr tp;
+  mp_ptr tp, rp;
   mp_size_t tn;
 
   if (vn < TOOM3_THRESHOLD)
     {
-      /* In the mpn_mul_basecase and toom2 range, use our own mul_basecase.  */
+      /* In the mpn_mul_basecase and toom2 ranges, use our own mul_basecase. */
       if (vn != 0)
 	refmpn_mul_basecase (wp, up, un, vp, vn);
       else
@@ -1876,51 +1876,49 @@
       return;
     }
 
+  MPN_ZERO (wp, vn);
+  rp = refmpn_malloc_limbs (2 * vn);
+
   if (vn < TOOM4_THRESHOLD)
+    tn = mpn_toom22_mul_itch (vn, vn);
+  else if (vn < TOOM6_THRESHOLD)
+    tn = mpn_toom33_mul_itch (vn, vn);
+  else if (vn < FFT_THRESHOLD)
+    tn = mpn_toom44_mul_itch (vn, vn);
+  else
+    tn = mpn_toom6h_mul_itch (vn, vn);
+  tp = refmpn_malloc_limbs (tn);
+
+  while (un >= vn)
     {
-      /* In the toom3 range, use mpn_toom22_mul.  */
-      tn = 2 * vn + mpn_toom22_mul_itch (vn, vn);
-      tp = refmpn_malloc_limbs (tn);
-      mpn_toom22_mul (tp, up, vn, vp, vn, tp + 2 * vn);
-    }
-  else if (vn < TOOM6_THRESHOLD)
-    {
-      /* In the toom4 range, use mpn_toom33_mul.  */
-      tn = 2 * vn + mpn_toom33_mul_itch (vn, vn);
-      tp = refmpn_malloc_limbs (tn);
-      mpn_toom33_mul (tp, up, vn, vp, vn, tp + 2 * vn);
-    }
-  else if (vn < FFT_THRESHOLD)
-    {
-      /* In the toom6 range, use mpn_toom44_mul.  */
-      tn = 2 * vn + mpn_toom44_mul_itch (vn, vn);
-      tp = refmpn_malloc_limbs (tn);
-      mpn_toom44_mul (tp, up, vn, vp, vn, tp + 2 * vn);
-    }
-  else
-    {
-      /* Finally, for the largest operands, use mpn_toom6h_mul.  */
-      tn = 2 * vn + mpn_toom6h_mul_itch (vn, vn);
-      tp = refmpn_malloc_limbs (tn);
-      mpn_toom6h_mul (tp, up, vn, vp, vn, tp + 2 * vn);
-    }
+      if (vn < TOOM4_THRESHOLD)
+	/* In the toom3 range, use mpn_toom22_mul.  */
+	mpn_toom22_mul (rp, up, vn, vp, vn, tp);
+      else if (vn < TOOM6_THRESHOLD)
+	/* In the toom4 range, use mpn_toom33_mul.  */
+	mpn_toom33_mul (rp, up, vn, vp, vn, tp);
+      else if (vn < FFT_THRESHOLD)
+	/* In the toom6 range, use mpn_toom44_mul.  */
+	mpn_toom44_mul (rp, up, vn, vp, vn, tp);
+      else
+	/* For the largest operands, use mpn_toom6h_mul.  */
+	mpn_toom6h_mul (rp, up, vn, vp, vn, tp);
 
-  if (un != vn)
-    {
-      if (un - vn < vn)
-	refmpn_mul (wp + vn, vp, vn, up + vn, un - vn);
-      else
-	refmpn_mul (wp + vn, up + vn, un - vn, vp, vn);
+      ASSERT_NOCARRY (refmpn_add (wp, rp, 2 * vn, wp, vn));
+      wp += vn;
 
-      MPN_COPY (wp, tp, vn);
-      ASSERT_NOCARRY (refmpn_add (wp + vn, wp + vn, un, tp + vn, vn));
-    }
-  else
-    {
-      MPN_COPY (wp, tp, 2 * vn);
+      up += vn;
+      un -= vn;
     }
 
   free (tp);
+
+  if (un != 0)
+    {
+      refmpn_mul (rp, vp, vn, up, un);
+      ASSERT_NOCARRY (refmpn_add (wp, rp, un + vn, wp, vn));
+    }
+  free (rp);
 }
 
 void