diff options
| author | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2021-08-02 21:31:17 +0200 |
|---|---|---|
| committer | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2021-08-02 21:31:17 +0200 |
| commit | a015e5100ab9d01460bd6ec15bcf6ae783134b57 (patch) | |
| tree | 63bc2cb8e568f16dee64e24916ddea583e674b73 /mini-gmp | |
| parent | 3142bb1db21507714afc4f915b240898603d3f08 (diff) | |
| download | gmp-a015e5100ab9d01460bd6ec15bcf6ae783134b57.tar.gz | |
mini-gmp/mini-gmp.c (mpz_rootrem): Better initial guess.
Diffstat (limited to 'mini-gmp')
| -rw-r--r-- | mini-gmp/ChangeLog | 5 | ||||
| -rw-r--r-- | mini-gmp/mini-gmp.c | 7 |
2 files changed, 10 insertions, 2 deletions
diff --git a/mini-gmp/ChangeLog b/mini-gmp/ChangeLog index deb4ce962..d97292743 100644 --- a/mini-gmp/ChangeLog +++ b/mini-gmp/ChangeLog @@ -1,3 +1,8 @@ +2021-08-02 Marco Bodrato <bodrato@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@mail.dm.unipi.it> * tests/t-reuse.c: Use numberof() to reduce the risk of typos. diff --git a/mini-gmp/mini-gmp.c b/mini-gmp/mini-gmp.c index c0b2e0192..a61ebf312 100644 --- a/mini-gmp/mini-gmp.c +++ b/mini-gmp/mini-gmp.c @@ -3198,6 +3198,7 @@ void 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_rootrem (mpz_t x, mpz_t r, const mpz_t y, unsigned long z) 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 @@ gmp_stronglucas (const mpz_t x, mpz_t Qk) 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); |