[Gmp-commit] /var/hg/gmp: mini-gmp/mini-gmp.c (mpz_rootrem): Better initial g...

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/2425a19ff9a4
changeset: 18229:2425a19ff9a4
user:      Marco Bodrato <bodrato at mail.dm.unipi.it>
date:      Mon Aug 02 21:31:17 2021 +0200
description:
mini-gmp/mini-gmp.c (mpz_rootrem): Better initial guess.

diffstat:

 mini-gmp/ChangeLog  |  5 +++++
 mini-gmp/mini-gmp.c |  7 +++++--
 2 files changed, 10 insertions(+), 2 deletions(-)

diffs (43 lines):

diff -r 560b15cf1266 -r 2425a19ff9a4 mini-gmp/ChangeLog
--- a/mini-gmp/ChangeLog	Fri Jul 02 08:05:46 2021 +0200
+++ b/mini-gmp/ChangeLog	Mon Aug 02 21:31:17 2021 +0200
@@ -1,3 +1,8 @@
+2021-08-02 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+	* mini-gmp.c (mpz_rootrem): Better initial guess.
+	(gmp_stronglucas): Shortcut, mpn_common_scan instead of mpz_scan0.
+
 2021-05-13 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* tests/t-reuse.c: Use numberof() to reduce the risk of typos.
diff -r 560b15cf1266 -r 2425a19ff9a4 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c	Fri Jul 02 08:05:46 2021 +0200
+++ b/mini-gmp/mini-gmp.c	Mon Aug 02 21:31:17 2021 +0200
@@ -3198,6 +3198,7 @@
 mpz_rootrem (mpz_t x, mpz_t r, const mpz_t y, unsigned long z)
 {
   int sgn;
+  mp_bitcnt_t bc;
   mpz_t t, u;
 
   sgn = y->_mp_size < 0;
@@ -3216,7 +3217,8 @@
 
   mpz_init (u);
   mpz_init (t);
-  mpz_setbit (t, mpz_sizeinbase (y, 2) / z + 1);
+  bc = (mpz_sizeinbase (y, 2) - 1) / z + 1;
+  mpz_setbit (t, bc);
 
   if (z == 2) /* simplify sqrt loop: z-1 == 1 */
     do {
@@ -3523,7 +3525,8 @@
   mpz_init (V);
 
   /* n-(D/n) = n+1 = d*2^{b0}, with d = (n>>b0) | 1 */
-  b0 = mpz_scan0 (n, 0);
+  b0 = mpn_common_scan (~ n->_mp_d[0], 0, n->_mp_d, n->_mp_size, GMP_LIMB_MAX);
+  /* b0 = mpz_scan0 (n, 0); */
 
   /* D= P^2 - 4Q; P = 1; Q = (1-D)/4 */
   Q = (D & 2) ? (long) (D >> 2) + 1 : -(long) (D >> 2);