[Gmp-commit] /var/hg/gmp: Use mpn_hgcd_reduce.

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/d60545d62c22
changeset: 14530:d60545d62c22
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Tue Dec 06 15:16:48 2011 +0100
description:
Use mpn_hgcd_reduce.

diffstat:

 ChangeLog          |   5 +++++
 mpn/generic/hgcd.c |  15 +++++++++------
 2 files changed, 14 insertions(+), 6 deletions(-)

diffs (48 lines):

diff -r e80a51dd5354 -r d60545d62c22 ChangeLog
--- a/ChangeLog	Tue Dec 06 11:47:08 2011 +0100
+++ b/ChangeLog	Tue Dec 06 15:16:48 2011 +0100
@@ -1,3 +1,8 @@
+2011-12-06  Niels Möller  <nisse at lysator.liu.se>
+
+	* mpn/generic/hgcd.c (mpn_hgcd): Use hgcd_reduce for first
+	recursive call.
+
 2011-12-06  Torbjorn Granlund  <tege at gmplib.org>
 
 	* tune/mod_1_1-1.c: Redefine the mpn_ functions, not __gmpn_ (for the
diff -r e80a51dd5354 -r d60545d62c22 mpn/generic/hgcd.c
--- a/mpn/generic/hgcd.c	Tue Dec 06 11:47:08 2011 +0100
+++ b/mpn/generic/hgcd.c	Tue Dec 06 15:16:48 2011 +0100
@@ -91,16 +91,15 @@
       mp_size_t n2 = (3*n)/4 + 1;
       mp_size_t p = n/2;
 
-      nn = mpn_hgcd (ap + p, bp + p, n - p, M, tp);
-      if (nn > 0)
+      nn = mpn_hgcd_reduce (M, ap, bp, n, p, tp);
+      if (nn)
 	{
-	  /* Needs 2*(p + M->n) <= 2*(floor(n/2) + ceil(n/2) - 1)
-	     = 2 (n - 1) */
-	  n = mpn_hgcd_matrix_adjust (M, p + nn, ap, bp, p, tp);
+	  n = nn;
 	  success = 1;
 	}
 
-      /* NOTE: It apppears this loop never runs more than once. */
+      /* NOTE: It apppears this loop never runs more than once (at
+	 least when not recursing to hgcd_appr). */
       while (n > n2)
 	{
 	  /* Needs n + 1 storage */
@@ -121,6 +120,10 @@
 	  scratch = MPN_HGCD_MATRIX_INIT_ITCH (n-p);
 
 	  mpn_hgcd_matrix_init(&M1, n - p, tp);
+
+	  /* FIXME: Should use hgcd_reduce, but that may require more
+	     scratch space, which requires review. */
+
 	  nn = mpn_hgcd (ap + p, bp + p, n - p, &M1, tp + scratch);
 	  if (nn > 0)
 	    {