1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.math; 18 19 import static com.google.common.math.MathTesting.ALL_BIGINTEGER_CANDIDATES; 20 import static com.google.common.math.MathTesting.ALL_ROUNDING_MODES; 21 import static com.google.common.math.MathTesting.ALL_SAFE_ROUNDING_MODES; 22 import static com.google.common.math.MathTesting.NEGATIVE_BIGINTEGER_CANDIDATES; 23 import static com.google.common.math.MathTesting.NONZERO_BIGINTEGER_CANDIDATES; 24 import static com.google.common.math.MathTesting.POSITIVE_BIGINTEGER_CANDIDATES; 25 import static com.google.common.truth.Truth.assertThat; 26 import static com.google.common.truth.Truth.assertWithMessage; 27 import static java.math.BigInteger.ONE; 28 import static java.math.BigInteger.TEN; 29 import static java.math.BigInteger.ZERO; 30 import static java.math.RoundingMode.CEILING; 31 import static java.math.RoundingMode.DOWN; 32 import static java.math.RoundingMode.FLOOR; 33 import static java.math.RoundingMode.HALF_DOWN; 34 import static java.math.RoundingMode.HALF_EVEN; 35 import static java.math.RoundingMode.HALF_UP; 36 import static java.math.RoundingMode.UNNECESSARY; 37 import static java.math.RoundingMode.UP; 38 import static java.math.RoundingMode.values; 39 import static java.util.Arrays.asList; 40 41 import com.google.common.annotations.GwtCompatible; 42 import com.google.common.annotations.GwtIncompatible; 43 import com.google.common.testing.NullPointerTester; 44 import java.math.BigDecimal; 45 import java.math.BigInteger; 46 import java.math.RoundingMode; 47 import java.util.EnumMap; 48 import java.util.EnumSet; 49 import java.util.Map; 50 import junit.framework.TestCase; 51 52 /** 53 * Tests for BigIntegerMath. 54 * 55 * @author Louis Wasserman 56 */ 57 @GwtCompatible(emulated = true) 58 public class BigIntegerMathTest extends TestCase { testCeilingPowerOfTwo()59 public void testCeilingPowerOfTwo() { 60 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 61 BigInteger result = BigIntegerMath.ceilingPowerOfTwo(x); 62 assertTrue(BigIntegerMath.isPowerOfTwo(result)); 63 assertTrue(result.compareTo(x) >= 0); 64 assertTrue(result.compareTo(x.add(x)) < 0); 65 } 66 } 67 68 public void testFloorPowerOfTwo() { 69 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 70 BigInteger result = BigIntegerMath.floorPowerOfTwo(x); 71 assertTrue(BigIntegerMath.isPowerOfTwo(result)); 72 assertTrue(result.compareTo(x) <= 0); 73 assertTrue(result.add(result).compareTo(x) > 0); 74 } 75 } 76 77 public void testCeilingPowerOfTwoNegative() { 78 for (BigInteger x : NEGATIVE_BIGINTEGER_CANDIDATES) { 79 try { 80 BigIntegerMath.ceilingPowerOfTwo(x); 81 fail("Expected IllegalArgumentException"); 82 } catch (IllegalArgumentException expected) { 83 } 84 } 85 } 86 87 public void testFloorPowerOfTwoNegative() { 88 for (BigInteger x : NEGATIVE_BIGINTEGER_CANDIDATES) { 89 try { 90 BigIntegerMath.floorPowerOfTwo(x); 91 fail("Expected IllegalArgumentException"); 92 } catch (IllegalArgumentException expected) { 93 } 94 } 95 } 96 97 public void testCeilingPowerOfTwoZero() { 98 try { 99 BigIntegerMath.ceilingPowerOfTwo(BigInteger.ZERO); 100 fail("Expected IllegalArgumentException"); 101 } catch (IllegalArgumentException expected) { 102 } 103 } 104 105 public void testFloorPowerOfTwoZero() { 106 try { 107 BigIntegerMath.floorPowerOfTwo(BigInteger.ZERO); 108 fail("Expected IllegalArgumentException"); 109 } catch (IllegalArgumentException expected) { 110 } 111 } 112 113 @GwtIncompatible // TODO 114 public void testConstantSqrt2PrecomputedBits() { 115 assertEquals( 116 BigIntegerMath.sqrt( 117 BigInteger.ZERO.setBit(2 * BigIntegerMath.SQRT2_PRECOMPUTE_THRESHOLD + 1), FLOOR), 118 BigIntegerMath.SQRT2_PRECOMPUTED_BITS); 119 } 120 121 public void testIsPowerOfTwo() { 122 for (BigInteger x : ALL_BIGINTEGER_CANDIDATES) { 123 // Checks for a single bit set. 124 boolean expected = x.signum() > 0 & x.and(x.subtract(ONE)).equals(ZERO); 125 assertEquals(expected, BigIntegerMath.isPowerOfTwo(x)); 126 } 127 } 128 testLog2ZeroAlwaysThrows()129 public void testLog2ZeroAlwaysThrows() { 130 for (RoundingMode mode : ALL_ROUNDING_MODES) { 131 try { 132 BigIntegerMath.log2(ZERO, mode); 133 fail("Expected IllegalArgumentException"); 134 } catch (IllegalArgumentException expected) { 135 } 136 } 137 } 138 testLog2NegativeAlwaysThrows()139 public void testLog2NegativeAlwaysThrows() { 140 for (RoundingMode mode : ALL_ROUNDING_MODES) { 141 try { 142 BigIntegerMath.log2(BigInteger.valueOf(-1), mode); 143 fail("Expected IllegalArgumentException"); 144 } catch (IllegalArgumentException expected) { 145 } 146 } 147 } 148 testLog2Floor()149 public void testLog2Floor() { 150 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 151 for (RoundingMode mode : asList(FLOOR, DOWN)) { 152 int result = BigIntegerMath.log2(x, mode); 153 assertTrue(ZERO.setBit(result).compareTo(x) <= 0); 154 assertTrue(ZERO.setBit(result + 1).compareTo(x) > 0); 155 } 156 } 157 } 158 testLog2Ceiling()159 public void testLog2Ceiling() { 160 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 161 for (RoundingMode mode : asList(CEILING, UP)) { 162 int result = BigIntegerMath.log2(x, mode); 163 assertTrue(ZERO.setBit(result).compareTo(x) >= 0); 164 assertTrue(result == 0 || ZERO.setBit(result - 1).compareTo(x) < 0); 165 } 166 } 167 } 168 169 // Relies on the correctness of isPowerOfTwo(BigInteger). testLog2Exact()170 public void testLog2Exact() { 171 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 172 // We only expect an exception if x was not a power of 2. 173 boolean isPowerOf2 = BigIntegerMath.isPowerOfTwo(x); 174 try { 175 assertEquals(x, ZERO.setBit(BigIntegerMath.log2(x, UNNECESSARY))); 176 assertTrue(isPowerOf2); 177 } catch (ArithmeticException e) { 178 assertFalse(isPowerOf2); 179 } 180 } 181 } 182 testLog2HalfUp()183 public void testLog2HalfUp() { 184 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 185 int result = BigIntegerMath.log2(x, HALF_UP); 186 BigInteger x2 = x.pow(2); 187 // x^2 < 2^(2 * result + 1), or else we would have rounded up 188 assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) > 0); 189 // x^2 >= 2^(2 * result - 1), or else we would have rounded down 190 assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) <= 0); 191 } 192 } 193 testLog2HalfDown()194 public void testLog2HalfDown() { 195 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 196 int result = BigIntegerMath.log2(x, HALF_DOWN); 197 BigInteger x2 = x.pow(2); 198 // x^2 <= 2^(2 * result + 1), or else we would have rounded up 199 assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) >= 0); 200 // x^2 > 2^(2 * result - 1), or else we would have rounded down 201 assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) < 0); 202 } 203 } 204 205 // Relies on the correctness of log2(BigInteger, {HALF_UP,HALF_DOWN}). testLog2HalfEven()206 public void testLog2HalfEven() { 207 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 208 int halfEven = BigIntegerMath.log2(x, HALF_EVEN); 209 // Now figure out what rounding mode we should behave like (it depends if FLOOR was 210 // odd/even). 211 boolean floorWasEven = (BigIntegerMath.log2(x, FLOOR) & 1) == 0; 212 assertEquals(BigIntegerMath.log2(x, floorWasEven ? HALF_DOWN : HALF_UP), halfEven); 213 } 214 } 215 216 @GwtIncompatible // TODO testLog10ZeroAlwaysThrows()217 public void testLog10ZeroAlwaysThrows() { 218 for (RoundingMode mode : ALL_ROUNDING_MODES) { 219 try { 220 BigIntegerMath.log10(ZERO, mode); 221 fail("Expected IllegalArgumentException"); 222 } catch (IllegalArgumentException expected) { 223 } 224 } 225 } 226 227 @GwtIncompatible // TODO testLog10NegativeAlwaysThrows()228 public void testLog10NegativeAlwaysThrows() { 229 for (RoundingMode mode : ALL_ROUNDING_MODES) { 230 try { 231 BigIntegerMath.log10(BigInteger.valueOf(-1), mode); 232 fail("Expected IllegalArgumentException"); 233 } catch (IllegalArgumentException expected) { 234 } 235 } 236 } 237 238 @GwtIncompatible // TODO testLog10Floor()239 public void testLog10Floor() { 240 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 241 for (RoundingMode mode : asList(FLOOR, DOWN)) { 242 int result = BigIntegerMath.log10(x, mode); 243 assertTrue(TEN.pow(result).compareTo(x) <= 0); 244 assertTrue(TEN.pow(result + 1).compareTo(x) > 0); 245 } 246 } 247 } 248 249 @GwtIncompatible // TODO testLog10Ceiling()250 public void testLog10Ceiling() { 251 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 252 for (RoundingMode mode : asList(CEILING, UP)) { 253 int result = BigIntegerMath.log10(x, mode); 254 assertTrue(TEN.pow(result).compareTo(x) >= 0); 255 assertTrue(result == 0 || TEN.pow(result - 1).compareTo(x) < 0); 256 } 257 } 258 } 259 260 // Relies on the correctness of log10(BigInteger, FLOOR). 261 @GwtIncompatible // TODO testLog10Exact()262 public void testLog10Exact() { 263 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 264 int logFloor = BigIntegerMath.log10(x, FLOOR); 265 boolean expectSuccess = TEN.pow(logFloor).equals(x); 266 try { 267 assertEquals(logFloor, BigIntegerMath.log10(x, UNNECESSARY)); 268 assertTrue(expectSuccess); 269 } catch (ArithmeticException e) { 270 assertFalse(expectSuccess); 271 } 272 } 273 } 274 275 @GwtIncompatible // TODO testLog10HalfUp()276 public void testLog10HalfUp() { 277 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 278 int result = BigIntegerMath.log10(x, HALF_UP); 279 BigInteger x2 = x.pow(2); 280 // x^2 < 10^(2 * result + 1), or else we would have rounded up 281 assertTrue(TEN.pow(2 * result + 1).compareTo(x2) > 0); 282 // x^2 >= 10^(2 * result - 1), or else we would have rounded down 283 assertTrue(result == 0 || TEN.pow(2 * result - 1).compareTo(x2) <= 0); 284 } 285 } 286 287 @GwtIncompatible // TODO testLog10HalfDown()288 public void testLog10HalfDown() { 289 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 290 int result = BigIntegerMath.log10(x, HALF_DOWN); 291 BigInteger x2 = x.pow(2); 292 // x^2 <= 10^(2 * result + 1), or else we would have rounded up 293 assertTrue(TEN.pow(2 * result + 1).compareTo(x2) >= 0); 294 // x^2 > 10^(2 * result - 1), or else we would have rounded down 295 assertTrue(result == 0 || TEN.pow(2 * result - 1).compareTo(x2) < 0); 296 } 297 } 298 299 // Relies on the correctness of log10(BigInteger, {HALF_UP,HALF_DOWN}). 300 @GwtIncompatible // TODO testLog10HalfEven()301 public void testLog10HalfEven() { 302 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 303 int halfEven = BigIntegerMath.log10(x, HALF_EVEN); 304 // Now figure out what rounding mode we should behave like (it depends if FLOOR was 305 // odd/even). 306 boolean floorWasEven = (BigIntegerMath.log10(x, FLOOR) & 1) == 0; 307 assertEquals(BigIntegerMath.log10(x, floorWasEven ? HALF_DOWN : HALF_UP), halfEven); 308 } 309 } 310 311 @GwtIncompatible // TODO testLog10TrivialOnPowerOf10()312 public void testLog10TrivialOnPowerOf10() { 313 BigInteger x = BigInteger.TEN.pow(100); 314 for (RoundingMode mode : ALL_ROUNDING_MODES) { 315 assertEquals(100, BigIntegerMath.log10(x, mode)); 316 } 317 } 318 319 @GwtIncompatible // TODO testSqrtZeroAlwaysZero()320 public void testSqrtZeroAlwaysZero() { 321 for (RoundingMode mode : ALL_ROUNDING_MODES) { 322 assertEquals(ZERO, BigIntegerMath.sqrt(ZERO, mode)); 323 } 324 } 325 326 @GwtIncompatible // TODO testSqrtNegativeAlwaysThrows()327 public void testSqrtNegativeAlwaysThrows() { 328 for (RoundingMode mode : ALL_ROUNDING_MODES) { 329 try { 330 BigIntegerMath.sqrt(BigInteger.valueOf(-1), mode); 331 fail("Expected IllegalArgumentException"); 332 } catch (IllegalArgumentException expected) { 333 } 334 } 335 } 336 337 @GwtIncompatible // TODO testSqrtFloor()338 public void testSqrtFloor() { 339 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 340 for (RoundingMode mode : asList(FLOOR, DOWN)) { 341 BigInteger result = BigIntegerMath.sqrt(x, mode); 342 assertTrue(result.compareTo(ZERO) > 0); 343 assertTrue(result.pow(2).compareTo(x) <= 0); 344 assertTrue(result.add(ONE).pow(2).compareTo(x) > 0); 345 } 346 } 347 } 348 349 @GwtIncompatible // TODO testSqrtCeiling()350 public void testSqrtCeiling() { 351 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 352 for (RoundingMode mode : asList(CEILING, UP)) { 353 BigInteger result = BigIntegerMath.sqrt(x, mode); 354 assertTrue(result.compareTo(ZERO) > 0); 355 assertTrue(result.pow(2).compareTo(x) >= 0); 356 assertTrue(result.signum() == 0 || result.subtract(ONE).pow(2).compareTo(x) < 0); 357 } 358 } 359 } 360 361 // Relies on the correctness of sqrt(BigInteger, FLOOR). 362 @GwtIncompatible // TODO 363 public void testSqrtExact() { 364 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 365 BigInteger floor = BigIntegerMath.sqrt(x, FLOOR); 366 // We only expect an exception if x was not a perfect square. 367 boolean isPerfectSquare = floor.pow(2).equals(x); 368 try { 369 assertEquals(floor, BigIntegerMath.sqrt(x, UNNECESSARY)); 370 assertTrue(isPerfectSquare); 371 } catch (ArithmeticException e) { 372 assertFalse(isPerfectSquare); 373 } 374 } 375 } 376 377 @GwtIncompatible // TODO 378 public void testSqrtHalfUp() { 379 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 380 BigInteger result = BigIntegerMath.sqrt(x, HALF_UP); 381 BigInteger plusHalfSquared = result.pow(2).add(result).shiftLeft(2).add(ONE); 382 BigInteger x4 = x.shiftLeft(2); 383 // sqrt(x) < result + 0.5, so 4 * x < (result + 0.5)^2 * 4 384 // (result + 0.5)^2 * 4 = (result^2 + result)*4 + 1 385 assertTrue(x4.compareTo(plusHalfSquared) < 0); 386 BigInteger minusHalfSquared = result.pow(2).subtract(result).shiftLeft(2).add(ONE); 387 // sqrt(x) > result - 0.5, so 4 * x > (result - 0.5)^2 * 4 388 // (result - 0.5)^2 * 4 = (result^2 - result)*4 + 1 389 assertTrue(result.equals(ZERO) || x4.compareTo(minusHalfSquared) >= 0); 390 } 391 } 392 393 @GwtIncompatible // TODO 394 public void testSqrtHalfDown() { 395 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 396 BigInteger result = BigIntegerMath.sqrt(x, HALF_DOWN); 397 BigInteger plusHalfSquared = result.pow(2).add(result).shiftLeft(2).add(ONE); 398 BigInteger x4 = x.shiftLeft(2); 399 // sqrt(x) <= result + 0.5, so 4 * x <= (result + 0.5)^2 * 4 400 // (result + 0.5)^2 * 4 = (result^2 + result)*4 + 1 401 assertTrue(x4.compareTo(plusHalfSquared) <= 0); 402 BigInteger minusHalfSquared = result.pow(2).subtract(result).shiftLeft(2).add(ONE); 403 // sqrt(x) > result - 0.5, so 4 * x > (result - 0.5)^2 * 4 404 // (result - 0.5)^2 * 4 = (result^2 - result)*4 + 1 405 assertTrue(result.equals(ZERO) || x4.compareTo(minusHalfSquared) > 0); 406 } 407 } 408 409 // Relies on the correctness of sqrt(BigInteger, {HALF_UP,HALF_DOWN}). 410 @GwtIncompatible // TODO 411 public void testSqrtHalfEven() { 412 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 413 BigInteger halfEven = BigIntegerMath.sqrt(x, HALF_EVEN); 414 // Now figure out what rounding mode we should behave like (it depends if FLOOR was 415 // odd/even). 416 boolean floorWasOdd = BigIntegerMath.sqrt(x, FLOOR).testBit(0); 417 assertEquals(BigIntegerMath.sqrt(x, floorWasOdd ? HALF_UP : HALF_DOWN), halfEven); 418 } 419 } 420 421 @GwtIncompatible // TODO 422 @AndroidIncompatible // slow 423 public void testDivNonZero() { 424 for (BigInteger p : NONZERO_BIGINTEGER_CANDIDATES) { 425 for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) { 426 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) { 427 BigInteger expected = 428 new BigDecimal(p).divide(new BigDecimal(q), 0, mode).toBigIntegerExact(); 429 assertEquals(expected, BigIntegerMath.divide(p, q, mode)); 430 } 431 } 432 } 433 } 434 435 private static final BigInteger BAD_FOR_ANDROID_P = new BigInteger("-9223372036854775808"); 436 private static final BigInteger BAD_FOR_ANDROID_Q = new BigInteger("-1"); 437 438 private static final BigInteger BAD_FOR_GINGERBREAD_P = new BigInteger("-9223372036854775808"); 439 private static final BigInteger BAD_FOR_GINGERBREAD_Q = new BigInteger("-4294967296"); 440 441 @GwtIncompatible // TODO 442 @AndroidIncompatible // slow 443 public void testDivNonZeroExact() { 444 boolean isAndroid = System.getProperties().getProperty("java.runtime.name").contains("Android"); 445 for (BigInteger p : NONZERO_BIGINTEGER_CANDIDATES) { 446 for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) { 447 if (isAndroid && p.equals(BAD_FOR_ANDROID_P) && q.equals(BAD_FOR_ANDROID_Q)) { 448 // https://code.google.com/p/android/issues/detail?id=196555 449 continue; 450 } 451 if (isAndroid && p.equals(BAD_FOR_GINGERBREAD_P) && q.equals(BAD_FOR_GINGERBREAD_Q)) { 452 // Works fine under Marshmallow, so I haven't filed a bug. 453 continue; 454 } 455 456 boolean dividesEvenly = p.remainder(q).equals(ZERO); 457 458 try { 459 BigInteger quotient = BigIntegerMath.divide(p, q, UNNECESSARY); 460 BigInteger undone = quotient.multiply(q); 461 if (!p.equals(undone)) { 462 failFormat("expected %s.multiply(%s) = %s; got %s", quotient, q, p, undone); 463 } 464 assertTrue(dividesEvenly); 465 } catch (ArithmeticException e) { 466 assertFalse(dividesEvenly); 467 } 468 } 469 } 470 } 471 472 @GwtIncompatible // TODO 473 public void testZeroDivIsAlwaysZero() { 474 for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) { 475 for (RoundingMode mode : ALL_ROUNDING_MODES) { 476 assertEquals(ZERO, BigIntegerMath.divide(ZERO, q, mode)); 477 } 478 } 479 } 480 481 @GwtIncompatible // TODO 482 public void testDivByZeroAlwaysFails() { 483 for (BigInteger p : ALL_BIGINTEGER_CANDIDATES) { 484 for (RoundingMode mode : ALL_ROUNDING_MODES) { 485 try { 486 BigIntegerMath.divide(p, ZERO, mode); 487 fail("Expected ArithmeticException"); 488 } catch (ArithmeticException expected) { 489 } 490 } 491 } 492 } 493 494 public void testFactorial() { 495 BigInteger expected = BigInteger.ONE; 496 for (int i = 1; i <= 200; i++) { 497 expected = expected.multiply(BigInteger.valueOf(i)); 498 assertEquals(expected, BigIntegerMath.factorial(i)); 499 } 500 } 501 502 public void testFactorial0() { 503 assertEquals(BigInteger.ONE, BigIntegerMath.factorial(0)); 504 } 505 506 public void testFactorialNegative() { 507 try { 508 BigIntegerMath.factorial(-1); 509 fail("Expected IllegalArgumentException"); 510 } catch (IllegalArgumentException expected) { 511 } 512 } 513 514 public void testBinomialSmall() { 515 runBinomialTest(0, 30); 516 } 517 518 @GwtIncompatible // too slow 519 public void testBinomialLarge() { 520 runBinomialTest(31, 100); 521 } 522 523 // Depends on the correctness of BigIntegerMath.factorial 524 private static void runBinomialTest(int firstN, int lastN) { 525 for (int n = firstN; n <= lastN; n++) { 526 for (int k = 0; k <= n; k++) { 527 BigInteger expected = 528 BigIntegerMath.factorial(n) 529 .divide(BigIntegerMath.factorial(k)) 530 .divide(BigIntegerMath.factorial(n - k)); 531 assertEquals(expected, BigIntegerMath.binomial(n, k)); 532 } 533 } 534 } 535 536 public void testBinomialOutside() { 537 for (int n = 0; n <= 50; n++) { 538 try { 539 BigIntegerMath.binomial(n, -1); 540 fail("Expected IllegalArgumentException"); 541 } catch (IllegalArgumentException expected) { 542 } 543 try { 544 BigIntegerMath.binomial(n, n + 1); 545 fail("Expected IllegalArgumentException"); 546 } catch (IllegalArgumentException expected) { 547 } 548 } 549 } 550 551 @GwtIncompatible 552 private static final class RoundToDoubleTester { 553 private final BigInteger input; 554 private final Map<RoundingMode, Double> expectedValues = new EnumMap<>(RoundingMode.class); 555 private boolean unnecessaryShouldThrow = false; 556 557 RoundToDoubleTester(BigInteger input) { 558 this.input = input; 559 } 560 561 RoundToDoubleTester setExpectation(double expectedValue, RoundingMode... modes) { 562 for (RoundingMode mode : modes) { 563 Double previous = expectedValues.put(mode, expectedValue); 564 if (previous != null) { 565 throw new AssertionError(); 566 } 567 } 568 return this; 569 } 570 571 public RoundToDoubleTester roundUnnecessaryShouldThrow() { 572 unnecessaryShouldThrow = true; 573 return this; 574 } 575 576 public void test() { 577 assertThat(expectedValues.keySet()) 578 .containsAtLeastElementsIn(EnumSet.complementOf(EnumSet.of(UNNECESSARY))); 579 for (Map.Entry<RoundingMode, Double> entry : expectedValues.entrySet()) { 580 RoundingMode mode = entry.getKey(); 581 Double expectation = entry.getValue(); 582 assertWithMessage("roundToDouble(" + input + ", " + mode + ")") 583 .that(BigIntegerMath.roundToDouble(input, mode)) 584 .isEqualTo(expectation); 585 } 586 587 if (!expectedValues.containsKey(UNNECESSARY)) { 588 assertWithMessage("Expected roundUnnecessaryShouldThrow call") 589 .that(unnecessaryShouldThrow) 590 .isTrue(); 591 try { 592 BigIntegerMath.roundToDouble(input, UNNECESSARY); 593 fail("Expected ArithmeticException for roundToDouble(" + input + ", UNNECESSARY)"); 594 } catch (ArithmeticException expected) { 595 // expected 596 } 597 } 598 } 599 } 600 601 @GwtIncompatible 602 public void testRoundToDouble_Zero() { 603 new RoundToDoubleTester(BigInteger.ZERO).setExpectation(0.0, values()).test(); 604 } 605 606 @GwtIncompatible 607 public void testRoundToDouble_smallPositive() { 608 new RoundToDoubleTester(BigInteger.valueOf(16)).setExpectation(16.0, values()).test(); 609 } 610 611 @GwtIncompatible 612 public void testRoundToDouble_maxPreciselyRepresentable() { 613 new RoundToDoubleTester(BigInteger.valueOf(1L << 53)) 614 .setExpectation(Math.pow(2, 53), values()) 615 .test(); 616 } 617 618 @GwtIncompatible 619 public void testRoundToDouble_maxPreciselyRepresentablePlusOne() { 620 double twoToThe53 = Math.pow(2, 53); 621 // the representable doubles are 2^53 and 2^53 + 2. 622 // 2^53+1 is halfway between, so HALF_UP will go up and HALF_DOWN will go down. 623 new RoundToDoubleTester(BigInteger.valueOf((1L << 53) + 1)) 624 .setExpectation(twoToThe53, DOWN, FLOOR, HALF_DOWN, HALF_EVEN) 625 .setExpectation(Math.nextUp(twoToThe53), CEILING, UP, HALF_UP) 626 .roundUnnecessaryShouldThrow() 627 .test(); 628 } 629 630 @GwtIncompatible 631 public void testRoundToDouble_twoToThe54PlusOne() { 632 double twoToThe54 = Math.pow(2, 54); 633 // the representable doubles are 2^54 and 2^54 + 4 634 // 2^54+1 is less than halfway between, so HALF_DOWN and HALF_UP will both go down. 635 new RoundToDoubleTester(BigInteger.valueOf((1L << 54) + 1)) 636 .setExpectation(twoToThe54, DOWN, FLOOR, HALF_DOWN, HALF_UP, HALF_EVEN) 637 .setExpectation(Math.nextUp(twoToThe54), CEILING, UP) 638 .roundUnnecessaryShouldThrow() 639 .test(); 640 } 641 642 @GwtIncompatible 643 public void testRoundToDouble_twoToThe54PlusThree() { 644 double twoToThe54 = Math.pow(2, 54); 645 // the representable doubles are 2^54 and 2^54 + 4 646 // 2^54+3 is more than halfway between, so HALF_DOWN and HALF_UP will both go up. 647 new RoundToDoubleTester(BigInteger.valueOf((1L << 54) + 3)) 648 .setExpectation(twoToThe54, DOWN, FLOOR) 649 .setExpectation(Math.nextUp(twoToThe54), CEILING, UP, HALF_DOWN, HALF_UP, HALF_EVEN) 650 .roundUnnecessaryShouldThrow() 651 .test(); 652 } 653 654 @GwtIncompatible 655 public void testRoundToDouble_twoToThe54PlusFour() { 656 new RoundToDoubleTester(BigInteger.valueOf((1L << 54) + 4)) 657 .setExpectation(Math.pow(2, 54) + 4, values()) 658 .test(); 659 } 660 661 @GwtIncompatible 662 public void testRoundToDouble_maxDouble() { 663 BigInteger maxDoubleAsBI = DoubleMath.roundToBigInteger(Double.MAX_VALUE, UNNECESSARY); 664 new RoundToDoubleTester(maxDoubleAsBI).setExpectation(Double.MAX_VALUE, values()).test(); 665 } 666 667 @GwtIncompatible 668 public void testRoundToDouble_maxDoublePlusOne() { 669 BigInteger maxDoubleAsBI = 670 DoubleMath.roundToBigInteger(Double.MAX_VALUE, UNNECESSARY).add(BigInteger.ONE); 671 new RoundToDoubleTester(maxDoubleAsBI) 672 .setExpectation(Double.MAX_VALUE, DOWN, FLOOR, HALF_EVEN, HALF_UP, HALF_DOWN) 673 .setExpectation(Double.POSITIVE_INFINITY, UP, CEILING) 674 .roundUnnecessaryShouldThrow() 675 .test(); 676 } 677 678 @GwtIncompatible 679 public void testRoundToDouble_wayTooBig() { 680 BigInteger bi = BigInteger.ONE.shiftLeft(2 * Double.MAX_EXPONENT); 681 new RoundToDoubleTester(bi) 682 .setExpectation(Double.MAX_VALUE, DOWN, FLOOR, HALF_EVEN, HALF_UP, HALF_DOWN) 683 .setExpectation(Double.POSITIVE_INFINITY, UP, CEILING) 684 .roundUnnecessaryShouldThrow() 685 .test(); 686 } 687 688 @GwtIncompatible 689 public void testRoundToDouble_smallNegative() { 690 new RoundToDoubleTester(BigInteger.valueOf(-16)).setExpectation(-16.0, values()).test(); 691 } 692 693 @GwtIncompatible 694 public void testRoundToDouble_minPreciselyRepresentable() { 695 new RoundToDoubleTester(BigInteger.valueOf(-1L << 53)) 696 .setExpectation(-Math.pow(2, 53), values()) 697 .test(); 698 } 699 700 @GwtIncompatible 701 public void testRoundToDouble_minPreciselyRepresentableMinusOne() { 702 // the representable doubles are -2^53 and -2^53 - 2. 703 // -2^53-1 is halfway between, so HALF_UP will go up and HALF_DOWN will go down. 704 new RoundToDoubleTester(BigInteger.valueOf((-1L << 53) - 1)) 705 .setExpectation(-Math.pow(2, 53), DOWN, CEILING, HALF_DOWN, HALF_EVEN) 706 .setExpectation(DoubleUtils.nextDown(-Math.pow(2, 53)), FLOOR, UP, HALF_UP) 707 .roundUnnecessaryShouldThrow() 708 .test(); 709 } 710 711 @GwtIncompatible 712 public void testRoundToDouble_negativeTwoToThe54MinusOne() { 713 new RoundToDoubleTester(BigInteger.valueOf((-1L << 54) - 1)) 714 .setExpectation(-Math.pow(2, 54), DOWN, CEILING, HALF_DOWN, HALF_UP, HALF_EVEN) 715 .setExpectation(DoubleUtils.nextDown(-Math.pow(2, 54)), FLOOR, UP) 716 .roundUnnecessaryShouldThrow() 717 .test(); 718 } 719 720 @GwtIncompatible 721 public void testRoundToDouble_negativeTwoToThe54MinusThree() { 722 new RoundToDoubleTester(BigInteger.valueOf((-1L << 54) - 3)) 723 .setExpectation(-Math.pow(2, 54), DOWN, CEILING) 724 .setExpectation( 725 DoubleUtils.nextDown(-Math.pow(2, 54)), FLOOR, UP, HALF_DOWN, HALF_UP, HALF_EVEN) 726 .roundUnnecessaryShouldThrow() 727 .test(); 728 } 729 730 @GwtIncompatible 731 public void testRoundToDouble_negativeTwoToThe54MinusFour() { 732 new RoundToDoubleTester(BigInteger.valueOf((-1L << 54) - 4)) 733 .setExpectation(-Math.pow(2, 54) - 4, values()) 734 .test(); 735 } 736 737 @GwtIncompatible 738 public void testRoundToDouble_minDouble() { 739 BigInteger minDoubleAsBI = DoubleMath.roundToBigInteger(-Double.MAX_VALUE, UNNECESSARY); 740 new RoundToDoubleTester(minDoubleAsBI).setExpectation(-Double.MAX_VALUE, values()).test(); 741 } 742 743 @GwtIncompatible 744 public void testRoundToDouble_minDoubleMinusOne() { 745 BigInteger minDoubleAsBI = 746 DoubleMath.roundToBigInteger(-Double.MAX_VALUE, UNNECESSARY).subtract(BigInteger.ONE); 747 new RoundToDoubleTester(minDoubleAsBI) 748 .setExpectation(-Double.MAX_VALUE, DOWN, CEILING, HALF_EVEN, HALF_UP, HALF_DOWN) 749 .setExpectation(Double.NEGATIVE_INFINITY, UP, FLOOR) 750 .roundUnnecessaryShouldThrow() 751 .test(); 752 } 753 754 @GwtIncompatible 755 public void testRoundToDouble_negativeWayTooBig() { 756 BigInteger bi = BigInteger.ONE.shiftLeft(2 * Double.MAX_EXPONENT).negate(); 757 new RoundToDoubleTester(bi) 758 .setExpectation(-Double.MAX_VALUE, DOWN, CEILING, HALF_EVEN, HALF_UP, HALF_DOWN) 759 .setExpectation(Double.NEGATIVE_INFINITY, UP, FLOOR) 760 .roundUnnecessaryShouldThrow() 761 .test(); 762 } 763 764 @GwtIncompatible // NullPointerTester 765 public void testNullPointers() { 766 NullPointerTester tester = new NullPointerTester(); 767 tester.setDefault(BigInteger.class, ONE); 768 tester.setDefault(int.class, 1); 769 tester.setDefault(long.class, 1L); 770 tester.testAllPublicStaticMethods(BigIntegerMath.class); 771 } 772 773 @GwtIncompatible // String.format 774 private static void failFormat(String template, Object... args) { 775 fail(String.format(template, args)); 776 } 777 } 778