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

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/30a12946e998
changeset: 17336:30a12946e998
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Mar 27 18:45:59 2017 +0200
description:
mpz/{bin_uiui,oddfac_1}.c (limb_apprsqrt): Better approximation.

details:   /var/hg/gmp/rev/8330de843689
changeset: 17337:8330de843689
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Mar 27 18:46:06 2017 +0200
description:
Changelog

diffstat:

 ChangeLog      |   6 +++++-
 mpz/bin_uiui.c |  18 +++++++++++-------
 mpz/oddfac_1.c |  18 +++++++++++-------
 3 files changed, 27 insertions(+), 15 deletions(-)

diffs (107 lines):

diff -r bd5e734dcb13 -r 8330de843689 ChangeLog
--- a/ChangeLog	Sun Mar 12 14:49:01 2017 +0100
+++ b/ChangeLog	Mon Mar 27 18:46:06 2017 +0200
@@ -1,7 +1,11 @@
+2017-03-27 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+	* mpz/oddfac_1.c (limb_apprsqrt): Better approximation.
+	* mpz/bin_uiui.c (limb_apprsqrt): Likewise.
+
 2017-03-08 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* mpn/generic/sqrtrem.c: Direct use of sqrtrem2 when n==2.
-
 	* mpn/generic/div_qr_2.c (udiv_qr_4by2): Replace add_csaac with add_sssaaaa.
 
 2017-03-07  Torbjörn Granlund  <tg at gmplib.org>
diff -r bd5e734dcb13 -r 8330de843689 mpz/bin_uiui.c
--- a/mpz/bin_uiui.c	Sun Mar 12 14:49:01 2017 +0100
+++ b/mpz/bin_uiui.c	Mon Mar 27 18:46:06 2017 +0200
@@ -2,7 +2,7 @@
 
 Contributed to the GNU project by Torbjorn Granlund and Marco Bodrato.
 
-Copyright 2010-2012, 2015, 2016 Free Software Foundation, Inc.
+Copyright 2010-2012, 2015-2017 Free Software Foundation, Inc.
 
 This file is part of the GNU MP Library.
 
@@ -552,17 +552,21 @@
     }							\
   } while (0)
 
-/* Returns an approximation of the sqare root of x.  *
- * It gives: x <= limb_apprsqrt (x) ^ 2 < x * 9/4    */
+/* Returns an approximation of the sqare root of x.
+ * It gives:
+ *   limb_apprsqrt (x) ^ 2 <= x < (limb_apprsqrt (x)+1) ^ 2
+ * or
+ *   x <= limb_apprsqrt (x) ^ 2 <= x * 9/8
+ */
 static mp_limb_t
 limb_apprsqrt (mp_limb_t x)
 {
   int s;
 
   ASSERT (x > 2);
-  count_leading_zeros (s, x - 1);
-  s = GMP_LIMB_BITS - 1 - s;
-  return (CNST_LIMB(1) << (s >> 1)) + (CNST_LIMB(1) << ((s - 1) >> 1));
+  count_leading_zeros (s, x);
+  s = (GMP_LIMB_BITS - s) >> 1;
+  return ((CNST_LIMB(1) << s) + (x >> s)) >> 1;
 }
 
 static void
@@ -600,7 +604,7 @@
 
       s = limb_apprsqrt(n);
       s = n_to_bit (s);
-      ASSERT (bit_to_n (s) * bit_to_n (s) > n);
+      ASSERT (bit_to_n (s+1) * bit_to_n (s+1) > n);
       ASSERT (s <= n_to_bit (n >> 1));
       LOOP_ON_SIEVE_BEGIN (prime, n_to_bit (5), s, 0,sieve);
       COUNT_A_PRIME (prime, n, k, prod, max_prod, factors, j);
diff -r bd5e734dcb13 -r 8330de843689 mpz/oddfac_1.c
--- a/mpz/oddfac_1.c	Sun Mar 12 14:49:01 2017 +0100
+++ b/mpz/oddfac_1.c	Mon Mar 27 18:46:06 2017 +0200
@@ -7,7 +7,7 @@
 IN FACT, IT IS ALMOST GUARANTEED THAT IT WILL CHANGE OR
 DISAPPEAR IN A FUTURE GNU MP RELEASE.
 
-Copyright 2010-2012, 2015, 2016 Free Software Foundation, Inc.
+Copyright 2010-2012, 2015-2017 Free Software Foundation, Inc.
 
 This file is part of the GNU MP Library.
 
@@ -115,20 +115,24 @@
 #endif
 
 /*********************************************************/
-/* Section mswing: 2-multiswing factorial                 */
+/* Section mswing: 2-multiswing factorial                */
 /*********************************************************/
 
-/* Returns an approximation of the sqare root of x.  *
- * It gives: x <= limb_apprsqrt (x) ^ 2 < x * 9/4    */
+/* Returns an approximation of the sqare root of x.
+ * It gives:
+ *   limb_apprsqrt (x) ^ 2 <= x < (limb_apprsqrt (x)+1) ^ 2
+ * or
+ *   x <= limb_apprsqrt (x) ^ 2 <= x * 9/8
+ */
 static mp_limb_t
 limb_apprsqrt (mp_limb_t x)
 {
   int s;
 
   ASSERT (x > 2);
-  count_leading_zeros (s, x - 1);
-  s = GMP_LIMB_BITS - 1 - s;
-  return (CNST_LIMB(1) << (s >> 1)) + (CNST_LIMB(1) << ((s - 1) >> 1));
+  count_leading_zeros (s, x);
+  s = (GMP_LIMB_BITS - s) >> 1;
+  return ((CNST_LIMB(1) << s) + (x >> s)) >> 1;
 }
 
 #if 0