| 259 | } |
| 260 | |
| 261 | @GwtIncompatible // TODO |
| 262 | private static BigInteger sqrtFloor(BigInteger x) { |
| 263 | /* |
| 264 | * Adapted from Hacker's Delight, Figure 11-1. |
| 265 | * |
| 266 | * Using DoubleUtils.bigToDouble, getting a double approximation of x is extremely fast, and |
| 267 | * then we can get a double approximation of the square root. Then, we iteratively improve this |
| 268 | * guess with an application of Newton's method, which sets guess := (guess + (x / guess)) / 2. |
| 269 | * This iteration has the following two properties: |
| 270 | * |
| 271 | * a) every iteration (except potentially the first) has guess >= floor(sqrt(x)). This is |
| 272 | * because guess' is the arithmetic mean of guess and x / guess, sqrt(x) is the geometric mean, |
| 273 | * and the arithmetic mean is always higher than the geometric mean. |
| 274 | * |
| 275 | * b) this iteration converges to floor(sqrt(x)). In fact, the number of correct digits doubles |
| 276 | * with each iteration, so this algorithm takes O(log(digits)) iterations. |
| 277 | * |
| 278 | * We start out with a double-precision approximation, which may be higher or lower than the |
| 279 | * true value. Therefore, we perform at least one Newton iteration to get a guess that's |
| 280 | * definitely >= floor(sqrt(x)), and then continue the iteration until we reach a fixed point. |
| 281 | */ |
| 282 | BigInteger sqrt0; |
| 283 | int log2 = log2(x, FLOOR); |
| 284 | if (log2 < Double.MAX_EXPONENT) { |
| 285 | sqrt0 = sqrtApproxWithDoubles(x); |
| 286 | } else { |
| 287 | int shift = (log2 - DoubleUtils.SIGNIFICAND_BITS) & ~1; // even! |
| 288 | /* |
| 289 | * We have that x / 2^shift < 2^54. Our initial approximation to sqrtFloor(x) will be |
| 290 | * 2^(shift/2) * sqrtApproxWithDoubles(x / 2^shift). |
| 291 | */ |
| 292 | sqrt0 = sqrtApproxWithDoubles(x.shiftRight(shift)).shiftLeft(shift >> 1); |
| 293 | } |
| 294 | BigInteger sqrt1 = sqrt0.add(x.divide(sqrt0)).shiftRight(1); |
| 295 | if (sqrt0.equals(sqrt1)) { |
| 296 | return sqrt0; |
| 297 | } |
| 298 | do { |
| 299 | sqrt0 = sqrt1; |
| 300 | sqrt1 = sqrt0.add(x.divide(sqrt0)).shiftRight(1); |
| 301 | } while (sqrt1.compareTo(sqrt0) < 0); |
| 302 | return sqrt0; |
| 303 | } |
| 304 | |
| 305 | @GwtIncompatible // TODO |
| 306 | private static BigInteger sqrtApproxWithDoubles(BigInteger x) { |