diff options
| author | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2017-03-27 18:45:59 +0200 |
|---|---|---|
| committer | Marco Bodrato <bodrato@mail.dm.unipi.it> | 2017-03-27 18:45:59 +0200 |
| commit | 4bad22eb9c1d8cb4a5ac4ff288a1b9ceac1ffc94 (patch) | |
| tree | 57db703b7410d57d33824cbb8adc2cabe00b1ae3 /mpz/oddfac_1.c | |
| parent | 9699b4c085f6eb71d851c85f8f12895edcd94a90 (diff) | |
| download | gmp-4bad22eb9c1d8cb4a5ac4ff288a1b9ceac1ffc94.tar.gz | |
mpz/{bin_uiui,oddfac_1}.c (limb_apprsqrt): Better approximation.
Diffstat (limited to 'mpz/oddfac_1.c')
| -rw-r--r-- | mpz/oddfac_1.c | 18 |
1 files changed, 11 insertions, 7 deletions
diff --git a/mpz/oddfac_1.c b/mpz/oddfac_1.c index 37e7b54f4..9c99d1e49 100644 --- a/mpz/oddfac_1.c +++ b/mpz/oddfac_1.c @@ -7,7 +7,7 @@ IT IS ONLY SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. 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 @@ primesieve_size (mp_limb_t n) { return n_to_bit(n) / GMP_LIMB_BITS + 1; } #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 |