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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/20c3eafe27bc
changeset: 16702:20c3eafe27bc
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Thu Jun 11 22:24:14 2015 +0200
description:
mpn/generic/sqrtrem.c: Use sqrtrem1 when second to higest bit is set.

details:   /var/hg/gmp/rev/a7f4abc4ee2e
changeset: 16703:a7f4abc4ee2e
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Thu Jun 11 22:29:51 2015 +0200
description:
mpn/generic/sqrtrem.c: Always use sqrtrem1 for a single limb.

details:   /var/hg/gmp/rev/8f0a5e0d69d6
changeset: 16704:8f0a5e0d69d6
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Thu Jun 11 22:35:36 2015 +0200
description:
ChangeLog

diffstat:

 ChangeLog             |   2 ++
 mpn/generic/sqrtrem.c |  38 +++++++++++++++++++++++++-------------
 2 files changed, 27 insertions(+), 13 deletions(-)

diffs (87 lines):

diff -r a9aebe3c9bfb -r 8f0a5e0d69d6 ChangeLog
--- a/ChangeLog	Thu Jun 11 16:01:42 2015 +0200
+++ b/ChangeLog	Thu Jun 11 22:35:36 2015 +0200
@@ -1,5 +1,7 @@
 2015-06-10 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
+	* mpn/generic/sqrtrem.c: Use sqrtrem1 for single limb operands.
+
 	* tests/mpz/t-root.c: Check also mpz_root retunr value.
 	* mpn/generic/rootrem.c: Shorten first and last loop.
 
diff -r a9aebe3c9bfb -r 8f0a5e0d69d6 mpn/generic/sqrtrem.c
--- a/mpn/generic/sqrtrem.c	Thu Jun 11 16:01:42 2015 +0200
+++ b/mpn/generic/sqrtrem.c	Thu Jun 11 22:35:36 2015 +0200
@@ -8,8 +8,8 @@
    INTERFACES.  IN FACT, IT IS ALMOST GUARANTEED THAT THEY WILL CHANGE OR
    DISAPPEAR IN A FUTURE GMP RELEASE.
 
-Copyright 1999-2002, 2004, 2005, 2008, 2010, 2012 Free Software Foundation,
-Inc.
+Copyright 1999-2002, 2004, 2005, 2008, 2010, 2012, 2015 Free Software
+Foundation, Inc.
 
 This file is part of the GNU MP Library.
 
@@ -195,7 +195,7 @@
   /* now we have (initial rp0)<<Prec + np0>>Prec = (qhl<<Prec + q) * (2sp0) + u */
   sp0 = ((sp0 + qhl) << Prec) + q;
   cc = u >> Prec;
-  rp0 = ((u << Prec) & GMP_NUMB_MASK) + (np0 & (((mp_limb_t) 1 << Prec) - 1));
+  rp0 = ((u << Prec) & GMP_NUMB_MASK) + (np0 & ((CNST_LIMB (1) << Prec) - 1));
   /* subtract q * q or qhl*2^(2*Prec) from rp */
   q2 = q * q;
   cc -= (rp0 < q2) + qhl;
@@ -242,7 +242,7 @@
       h = n - l;
       q = mpn_dc_sqrtrem (sp + l, np + 2 * l, h);
       if (q != 0)
-	mpn_sub_n (np + 2 * l, np + 2 * l, sp + l, h);
+	ASSERT_CARRY (mpn_sub_n (np + 2 * l, np + 2 * l, sp + l, h));
       q += mpn_divrem (sp, 0, np + l, n, sp + l, h);
       c = sp[0] & 1;
       mpn_rshift (sp, sp, l, 1);
@@ -292,14 +292,26 @@
   ASSERT (! MPN_OVERLAP_P (sp, (nn + 1) / 2, np, nn));
 
   high = np[nn - 1];
-  if (nn == 1 && (high & GMP_NUMB_HIGHBIT))
-    {
-      mp_limb_t r;
-      sp[0] = mpn_sqrtrem1 (&r, high);
-      if (rp != NULL)
-	rp[0] = r;
-      return r != 0;
-    }
+  if (nn == 1)
+    if (high & (GMP_NUMB_HIGHBIT | (GMP_NUMB_HIGHBIT >> 1)))
+      {
+	sp[0] = mpn_sqrtrem1 (&rl, high);
+	if (rp != NULL)
+	  rp[0] = rl;
+	return rl != 0;
+      }
+    else
+      {
+	count_leading_zeros (c, high);
+	c -= GMP_NAIL_BITS;
+
+	c = c / 2; /* we have to shift left by 2c bits to normalize {np, nn} */
+	cc = mpn_sqrtrem1 (&rl, high << (2*c)) >> c;
+	sp[0] = cc;
+	if (rp != NULL)
+	  rp[0] = rl = high - cc*cc;
+	return rl != 0;
+      }
   count_leading_zeros (c, high);
   c -= GMP_NAIL_BITS;
 
@@ -319,7 +331,7 @@
       /* We have 2^(2k)*N = S^2 + R where k = c + (2tn-nn)*GMP_NUMB_BITS/2,
 	 thus 2^(2k)*N = (S-s0)^2 + 2*S*s0 - s0^2 + R where s0=S mod 2^k */
       c += (nn % 2) * GMP_NUMB_BITS / 2;		/* c now represents k */
-      s0[0] = sp[0] & (((mp_limb_t) 1 << c) - 1);	/* S mod 2^k */
+      s0[0] = sp[0] & ((CNST_LIMB (1) << c) - 1);	/* S mod 2^k */
       rl += mpn_addmul_1 (tp, sp, tn, 2 * s0[0]);	/* R = R + 2*s0*S */
       cc = mpn_submul_1 (tp, s0, 1, s0[0]);
       rl -= (tn > 1) ? mpn_sub_1 (tp + 1, tp + 1, tn - 1, cc) : cc;