diff options
author | vlefevre <vlefevre@280ebfd0-de03-0410-8827-d642c229c3f4> | 2007-09-19 00:57:46 +0000 |
---|---|---|
committer | vlefevre <vlefevre@280ebfd0-de03-0410-8827-d642c229c3f4> | 2007-09-19 00:57:46 +0000 |
commit | 0a8cf8c3536ccbf90148c244ed627e65f443c48d (patch) | |
tree | 09c724bac967b0304ccfba1376d067916e55e234 /isqrt.c | |
parent | d697ce26f77a3721b5adf8cc183e06e7cdbe8c90 (diff) | |
download | mpfr-0a8cf8c3536ccbf90148c244ed627e65f443c48d.tar.gz |
isqrt.c: fixed __gmpfr_isqrt.
git-svn-id: svn://scm.gforge.inria.fr/svn/mpfr/trunk@4858 280ebfd0-de03-0410-8827-d642c229c3f4
Diffstat (limited to 'isqrt.c')
-rw-r--r-- | isqrt.c | 17 |
1 files changed, 15 insertions, 2 deletions
@@ -26,14 +26,27 @@ MA 02110-1301, USA. */ unsigned long __gmpfr_isqrt (unsigned long n) { - unsigned long s; + unsigned long i, s; + /* First find an approximation to floor(sqrt(n)) of the form 2^k. */ + i = n; s = 1; + while (i >= 2) + { + i >>= 2; + s <<= 1; + } + do { s = (s + n / s) / 2; } - while (!(s*s <= n && n <= s*(s+2))); + while (!(s*s <= n && (s*s > s*(s+2) || n <= s*(s+2)))); + /* Short explanation: As mathematically s*(s+2) < 2*ULONG_MAX, + the condition s*s > s*(s+2) is evaluated as true when s*(s+2) + overflows but not s*s. This implies that mathematically, one + has s*s <= n <= s*(s+2). If s*s overflows, this means that n + is "large" and the inequality s*s <= n cannot be satisfied. */ return s; } |