IntMathTest.java revision 3c77433663281544363151bf284b0240dfd22a42
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 17package com.google.common.math; 18 19import static com.google.common.math.MathTesting.ALL_INTEGER_CANDIDATES; 20import static com.google.common.math.MathTesting.ALL_ROUNDING_MODES; 21import static com.google.common.math.MathTesting.ALL_SAFE_ROUNDING_MODES; 22import static com.google.common.math.MathTesting.EXPONENTS; 23import static com.google.common.math.MathTesting.NEGATIVE_INTEGER_CANDIDATES; 24import static com.google.common.math.MathTesting.NONZERO_INTEGER_CANDIDATES; 25import static com.google.common.math.MathTesting.POSITIVE_INTEGER_CANDIDATES; 26import static com.google.common.math.TestPlatform.intsCanGoOutOfRange; 27import static java.math.BigInteger.valueOf; 28import static java.math.RoundingMode.FLOOR; 29import static java.math.RoundingMode.UNNECESSARY; 30 31import com.google.common.annotations.GwtCompatible; 32import com.google.common.annotations.GwtIncompatible; 33import com.google.common.testing.NullPointerTester; 34 35import junit.framework.TestCase; 36 37import java.math.BigDecimal; 38import java.math.BigInteger; 39import java.math.RoundingMode; 40 41/** 42 * Tests for {@link IntMath}. 43 * 44 * @author Louis Wasserman 45 */ 46@GwtCompatible(emulated = true) 47public class IntMathTest extends TestCase { 48 @GwtIncompatible("BigIntegerMath") // TODO(cpovirk): GWT-enable BigIntegerMath 49 public void testConstantMaxPowerOfSqrt2Unsigned() { 50 assertEquals( 51 BigIntegerMath.sqrt(BigInteger.ZERO.setBit(2 * Integer.SIZE - 1), FLOOR).intValue(), 52 IntMath.MAX_POWER_OF_SQRT2_UNSIGNED); 53 } 54 55 @GwtIncompatible("pow()") 56 public void testConstantsPowersOf10() { 57 for (int i = 0; i < IntMath.powersOf10.length - 1; i++) { 58 assertEquals(IntMath.pow(10, i), IntMath.powersOf10[i]); 59 } 60 } 61 62 @GwtIncompatible("BigIntegerMath") // TODO(cpovirk): GWT-enable BigIntegerMath 63 public void testMaxLog10ForLeadingZeros() { 64 for (int i = 0; i < Integer.SIZE; i++) { 65 assertEquals( 66 BigIntegerMath.log10(BigInteger.ONE.shiftLeft(Integer.SIZE - i), FLOOR), 67 IntMath.maxLog10ForLeadingZeros[i]); 68 } 69 } 70 71 @GwtIncompatible("BigIntegerMath") // TODO(cpovirk): GWT-enable BigIntegerMath 72 public void testConstantsHalfPowersOf10() { 73 for (int i = 0; i < IntMath.halfPowersOf10.length; i++) { 74 assert IntMath.halfPowersOf10[i] 75 == Math.min(Integer.MAX_VALUE, 76 BigIntegerMath.sqrt(BigInteger.TEN.pow(2 * i + 1), FLOOR).longValue()); 77 } 78 } 79 80 @GwtIncompatible("BigIntegerMath") // TODO(cpovirk): GWT-enable BigIntegerMath 81 public void testConstantsBiggestBinomials() { 82 for (int k = 0; k < IntMath.biggestBinomials.length; k++) { 83 assertTrue(fitsInInt(BigIntegerMath.binomial(IntMath.biggestBinomials[k], k))); 84 assertTrue(IntMath.biggestBinomials[k] == Integer.MAX_VALUE 85 || !fitsInInt(BigIntegerMath.binomial(IntMath.biggestBinomials[k] + 1, k))); 86 // In the first case, any int is valid; in the second, we want to test that the next-bigger 87 // int overflows. 88 } 89 assertFalse( 90 fitsInInt(BigIntegerMath.binomial( 91 2 * IntMath.biggestBinomials.length, IntMath.biggestBinomials.length))); 92 } 93 94 @GwtIncompatible("sqrt") 95 public void testPowersSqrtMaxInt() { 96 assertEquals(IntMath.sqrt(Integer.MAX_VALUE, FLOOR), IntMath.FLOOR_SQRT_MAX_INT); 97 } 98 99 @GwtIncompatible("java.math.BigInteger") 100 public void testIsPowerOfTwo() { 101 for (int x : ALL_INTEGER_CANDIDATES) { 102 // Checks for a single bit set. 103 BigInteger bigX = BigInteger.valueOf(x); 104 boolean expected = (bigX.signum() > 0) && (bigX.bitCount() == 1); 105 assertEquals(expected, IntMath.isPowerOfTwo(x)); 106 } 107 } 108 109 public void testLog2ZeroAlwaysThrows() { 110 for (RoundingMode mode : ALL_ROUNDING_MODES) { 111 try { 112 IntMath.log2(0, mode); 113 fail("Expected IllegalArgumentException"); 114 } catch (IllegalArgumentException expected) {} 115 } 116 } 117 118 public void testLog2NegativeAlwaysThrows() { 119 for (int x : NEGATIVE_INTEGER_CANDIDATES) { 120 for (RoundingMode mode : ALL_ROUNDING_MODES) { 121 try { 122 IntMath.log2(x, mode); 123 fail("Expected IllegalArgumentException"); 124 } catch (IllegalArgumentException expected) {} 125 } 126 } 127 } 128 129 // Relies on the correctness of BigIntegrerMath.log2 for all modes except UNNECESSARY. 130 public void testLog2MatchesBigInteger() { 131 for (int x : POSITIVE_INTEGER_CANDIDATES) { 132 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) { 133 assertEquals(BigIntegerMath.log2(valueOf(x), mode), IntMath.log2(x, mode)); 134 } 135 } 136 } 137 138 // Relies on the correctness of isPowerOfTwo(int). 139 public void testLog2Exact() { 140 for (int x : POSITIVE_INTEGER_CANDIDATES) { 141 // We only expect an exception if x was not a power of 2. 142 boolean isPowerOf2 = IntMath.isPowerOfTwo(x); 143 try { 144 assertEquals(x, 1 << IntMath.log2(x, UNNECESSARY)); 145 assertTrue(isPowerOf2); 146 } catch (ArithmeticException e) { 147 assertFalse(isPowerOf2); 148 } 149 } 150 } 151 152 @GwtIncompatible("log10") 153 public void testLog10ZeroAlwaysThrows() { 154 for (RoundingMode mode : ALL_ROUNDING_MODES) { 155 try { 156 IntMath.log10(0, mode); 157 fail("Expected IllegalArgumentException"); 158 } catch (IllegalArgumentException expected) {} 159 } 160 } 161 162 @GwtIncompatible("log10") 163 public void testLog10NegativeAlwaysThrows() { 164 for (int x : NEGATIVE_INTEGER_CANDIDATES) { 165 for (RoundingMode mode : ALL_ROUNDING_MODES) { 166 try { 167 IntMath.log10(x, mode); 168 fail("Expected IllegalArgumentException"); 169 } catch (IllegalArgumentException expected) {} 170 } 171 } 172 } 173 174 // Relies on the correctness of BigIntegerMath.log10 for all modes except UNNECESSARY. 175 @GwtIncompatible("BigIntegerMath") // TODO(cpovirk): GWT-enable BigIntegerMath 176 public void testLog10MatchesBigInteger() { 177 for (int x : POSITIVE_INTEGER_CANDIDATES) { 178 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) { 179 // The BigInteger implementation is tested separately, use it as the reference. 180 assertEquals(BigIntegerMath.log10(valueOf(x), mode), IntMath.log10(x, mode)); 181 } 182 } 183 } 184 185 // Relies on the correctness of log10(int, FLOOR) and of pow(int, int). 186 @GwtIncompatible("pow()") 187 public void testLog10Exact() { 188 for (int x : POSITIVE_INTEGER_CANDIDATES) { 189 int floor = IntMath.log10(x, FLOOR); 190 boolean expectSuccess = IntMath.pow(10, floor) == x; 191 try { 192 assertEquals(floor, IntMath.log10(x, UNNECESSARY)); 193 assertTrue(expectSuccess); 194 } catch (ArithmeticException e) { 195 assertFalse(expectSuccess); 196 } 197 } 198 } 199 200 @GwtIncompatible("log10") 201 public void testLog10TrivialOnPowerOfTen() { 202 int x = 1000000; 203 for (RoundingMode mode : ALL_ROUNDING_MODES) { 204 assertEquals(6, IntMath.log10(x, mode)); 205 } 206 } 207 208 // Simple test to cover sqrt(0) for all types and all modes. 209 @GwtIncompatible("sqrt") 210 public void testSqrtZeroAlwaysZero() { 211 for (RoundingMode mode : ALL_ROUNDING_MODES) { 212 assertEquals(0, IntMath.sqrt(0, mode)); 213 } 214 } 215 216 @GwtIncompatible("sqrt") 217 public void testSqrtNegativeAlwaysThrows() { 218 for (int x : NEGATIVE_INTEGER_CANDIDATES) { 219 for (RoundingMode mode : RoundingMode.values()) { 220 try { 221 IntMath.sqrt(x, mode); 222 fail("Expected IllegalArgumentException"); 223 } catch (IllegalArgumentException expected) {} 224 } 225 } 226 } 227 228 /* Relies on the correctness of BigIntegerMath.sqrt for all modes except UNNECESSARY. */ 229 @GwtIncompatible("BigIntegerMath") // TODO(cpovirk): GWT-enable BigIntegerMath 230 public void testSqrtMatchesBigInteger() { 231 for (int x : POSITIVE_INTEGER_CANDIDATES) { 232 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) { 233 // The BigInteger implementation is tested separately, use it as the reference. 234 // Promote the int value (rather than using intValue() on the expected value) to avoid 235 // any risk of truncation which could lead to a false positive. 236 assertEquals(BigIntegerMath.sqrt(valueOf(x), mode), valueOf(IntMath.sqrt(x, mode))); 237 } 238 } 239 } 240 241 /* Relies on the correctness of sqrt(int, FLOOR). */ 242 @GwtIncompatible("sqrt") 243 public void testSqrtExactMatchesFloorOrThrows() { 244 for (int x : POSITIVE_INTEGER_CANDIDATES) { 245 int floor = IntMath.sqrt(x, FLOOR); 246 // We only expect an exception if x was not a perfect square. 247 boolean isPerfectSquare = (floor * floor == x); 248 try { 249 assertEquals(floor, IntMath.sqrt(x, UNNECESSARY)); 250 assertTrue(isPerfectSquare); 251 } catch (ArithmeticException e) { 252 assertFalse(isPerfectSquare); 253 } 254 } 255 } 256 257 @GwtIncompatible("2147483646^2 expected=4") 258 public void testPow() { 259 for (int i : ALL_INTEGER_CANDIDATES) { 260 for (int pow : EXPONENTS) { 261 assertEquals(i + "^" + pow, BigInteger.valueOf(i).pow(pow).intValue(), IntMath.pow(i, pow)); 262 } 263 } 264 } 265 266 public void testDivNonZero() { 267 for (int p : NONZERO_INTEGER_CANDIDATES) { 268 for (int q : NONZERO_INTEGER_CANDIDATES) { 269 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) { 270 // Skip some tests that fail due to GWT's non-compliant int implementation. 271 // TODO(cpovirk): does this test fail for only some rounding modes or for all? 272 if (p == -2147483648 && q == -1 && intsCanGoOutOfRange()) { 273 continue; 274 } 275 int expected = 276 new BigDecimal(valueOf(p)).divide(new BigDecimal(valueOf(q)), 0, mode).intValue(); 277 assertEquals(p + "/" + q, force32(expected), IntMath.divide(p, q, mode)); 278 } 279 } 280 } 281 } 282 283 public void testDivNonZeroExact() { 284 for (int p : NONZERO_INTEGER_CANDIDATES) { 285 for (int q : NONZERO_INTEGER_CANDIDATES) { 286 // Skip some tests that fail due to GWT's non-compliant int implementation. 287 if (p == -2147483648 && q == -1 && intsCanGoOutOfRange()) { 288 continue; 289 } 290 boolean dividesEvenly = (p % q) == 0; 291 try { 292 assertEquals(p + "/" + q, p, IntMath.divide(p, q, UNNECESSARY) * q); 293 assertTrue(p + "/" + q + " not expected to divide evenly", dividesEvenly); 294 } catch (ArithmeticException e) { 295 assertFalse(p + "/" + q + " expected to divide evenly", dividesEvenly); 296 } 297 } 298 } 299 } 300 301 public void testZeroDivIsAlwaysZero() { 302 for (int q : NONZERO_INTEGER_CANDIDATES) { 303 for (RoundingMode mode : ALL_ROUNDING_MODES) { 304 assertEquals(0, IntMath.divide(0, q, mode)); 305 } 306 } 307 } 308 309 public void testDivByZeroAlwaysFails() { 310 for (int p : ALL_INTEGER_CANDIDATES) { 311 for (RoundingMode mode : ALL_ROUNDING_MODES) { 312 try { 313 IntMath.divide(p, 0, mode); 314 fail("Expected ArithmeticException"); 315 } catch (ArithmeticException expected) {} 316 } 317 } 318 } 319 320 public void testMod() { 321 for (int x : ALL_INTEGER_CANDIDATES) { 322 for (int m : POSITIVE_INTEGER_CANDIDATES) { 323 assertEquals(valueOf(x).mod(valueOf(m)).intValue(), IntMath.mod(x, m)); 324 } 325 } 326 } 327 328 public void testModNegativeModulusFails() { 329 for (int x : POSITIVE_INTEGER_CANDIDATES) { 330 for (int m : NEGATIVE_INTEGER_CANDIDATES) { 331 try { 332 IntMath.mod(x, m); 333 fail("Expected ArithmeticException"); 334 } catch (ArithmeticException expected) {} 335 } 336 } 337 } 338 339 public void testModZeroModulusFails() { 340 for (int x : ALL_INTEGER_CANDIDATES) { 341 try { 342 IntMath.mod(x, 0); 343 fail("Expected ArithmeticException"); 344 } catch (ArithmeticException expected) {} 345 } 346 } 347 348 public void testGCD() { 349 for (int a : POSITIVE_INTEGER_CANDIDATES) { 350 for (int b : POSITIVE_INTEGER_CANDIDATES) { 351 assertEquals(valueOf(a).gcd(valueOf(b)), valueOf(IntMath.gcd(a, b))); 352 } 353 } 354 } 355 356 public void testGCDZero() { 357 for (int a : POSITIVE_INTEGER_CANDIDATES) { 358 assertEquals(a, IntMath.gcd(a, 0)); 359 assertEquals(a, IntMath.gcd(0, a)); 360 } 361 assertEquals(0, IntMath.gcd(0, 0)); 362 } 363 364 public void testGCDNegativePositiveThrows() { 365 for (int a : NEGATIVE_INTEGER_CANDIDATES) { 366 try { 367 IntMath.gcd(a, 3); 368 fail("Expected IllegalArgumentException"); 369 } catch (IllegalArgumentException expected) {} 370 try { 371 IntMath.gcd(3, a); 372 fail("Expected IllegalArgumentException"); 373 } catch (IllegalArgumentException expected) {} 374 } 375 } 376 377 public void testGCDNegativeZeroThrows() { 378 for (int a : NEGATIVE_INTEGER_CANDIDATES) { 379 try { 380 IntMath.gcd(a, 0); 381 fail("Expected IllegalArgumentException"); 382 } catch (IllegalArgumentException expected) {} 383 try { 384 IntMath.gcd(0, a); 385 fail("Expected IllegalArgumentException"); 386 } catch (IllegalArgumentException expected) {} 387 } 388 } 389 390 public void testCheckedAdd() { 391 for (int a : ALL_INTEGER_CANDIDATES) { 392 for (int b : ALL_INTEGER_CANDIDATES) { 393 BigInteger expectedResult = valueOf(a).add(valueOf(b)); 394 boolean expectedSuccess = fitsInInt(expectedResult); 395 try { 396 assertEquals(a + b, IntMath.checkedAdd(a, b)); 397 assertTrue(expectedSuccess); 398 } catch (ArithmeticException e) { 399 assertFalse(expectedSuccess); 400 } 401 } 402 } 403 } 404 405 public void testCheckedSubtract() { 406 for (int a : ALL_INTEGER_CANDIDATES) { 407 for (int b : ALL_INTEGER_CANDIDATES) { 408 BigInteger expectedResult = valueOf(a).subtract(valueOf(b)); 409 boolean expectedSuccess = fitsInInt(expectedResult); 410 try { 411 assertEquals(a - b, IntMath.checkedSubtract(a, b)); 412 assertTrue(expectedSuccess); 413 } catch (ArithmeticException e) { 414 assertFalse(expectedSuccess); 415 } 416 } 417 } 418 } 419 420 public void testCheckedMultiply() { 421 for (int a : ALL_INTEGER_CANDIDATES) { 422 for (int b : ALL_INTEGER_CANDIDATES) { 423 BigInteger expectedResult = valueOf(a).multiply(valueOf(b)); 424 boolean expectedSuccess = fitsInInt(expectedResult); 425 try { 426 assertEquals(a * b, IntMath.checkedMultiply(a, b)); 427 assertTrue(expectedSuccess); 428 } catch (ArithmeticException e) { 429 assertFalse(expectedSuccess); 430 } 431 } 432 } 433 } 434 435 public void testCheckedPow() { 436 for (int b : ALL_INTEGER_CANDIDATES) { 437 for (int k : EXPONENTS) { 438 BigInteger expectedResult = valueOf(b).pow(k); 439 boolean expectedSuccess = fitsInInt(expectedResult); 440 try { 441 assertEquals(b + "^" + k, force32(expectedResult.intValue()), IntMath.checkedPow(b, k)); 442 assertTrue(b + "^" + k + " should have succeeded", expectedSuccess); 443 } catch (ArithmeticException e) { 444 assertFalse(b + "^" + k + " should have failed", expectedSuccess); 445 } 446 } 447 } 448 } 449 450 // Depends on the correctness of BigIntegerMath.factorial. 451 public void testFactorial() { 452 for (int n = 0; n <= 50; n++) { 453 BigInteger expectedBig = BigIntegerMath.factorial(n); 454 int expectedInt = fitsInInt(expectedBig) ? expectedBig.intValue() : Integer.MAX_VALUE; 455 assertEquals(expectedInt, IntMath.factorial(n)); 456 } 457 } 458 459 public void testFactorialNegative() { 460 for (int n : NEGATIVE_INTEGER_CANDIDATES) { 461 try { 462 IntMath.factorial(n); 463 fail("Expected IllegalArgumentException"); 464 } catch (IllegalArgumentException expected) {} 465 } 466 } 467 468 // Depends on the correctness of BigIntegerMath.binomial. 469 @GwtIncompatible("BigIntegerMath") // TODO(cpovirk): GWT-enable BigIntegerMath 470 public void testBinomial() { 471 for (int n = 0; n <= 50; n++) { 472 for (int k = 0; k <= n; k++) { 473 BigInteger expectedBig = BigIntegerMath.binomial(n, k); 474 int expectedInt = fitsInInt(expectedBig) ? expectedBig.intValue() : Integer.MAX_VALUE; 475 assertEquals(expectedInt, IntMath.binomial(n, k)); 476 } 477 } 478 } 479 480 @GwtIncompatible("binomial") 481 public void testBinomialOutside() { 482 for (int n = 0; n <= 50; n++) { 483 try { 484 IntMath.binomial(n, -1); 485 fail("Expected IllegalArgumentException"); 486 } catch (IllegalArgumentException expected) {} 487 try { 488 IntMath.binomial(n, n + 1); 489 fail("Expected IllegalArgumentException"); 490 } catch (IllegalArgumentException expected) {} 491 } 492 } 493 494 @GwtIncompatible("binomial") 495 public void testBinomialNegative() { 496 for (int n : NEGATIVE_INTEGER_CANDIDATES) { 497 try { 498 IntMath.binomial(n, 0); 499 fail("Expected IllegalArgumentException"); 500 } catch (IllegalArgumentException expected) {} 501 } 502 } 503 504 @GwtIncompatible("java.math.BigInteger") 505 public void testMean() { 506 // Odd-sized ranges have an obvious mean 507 assertMean(2, 1, 3); 508 509 assertMean(-2, -3, -1); 510 assertMean(0, -1, 1); 511 assertMean(1, -1, 3); 512 assertMean((1 << 30) - 1, -1, Integer.MAX_VALUE); 513 514 // Even-sized ranges should prefer the lower mean 515 assertMean(2, 1, 4); 516 assertMean(-3, -4, -1); 517 assertMean(0, -1, 2); 518 assertMean(0, Integer.MIN_VALUE + 2, Integer.MAX_VALUE); 519 assertMean(0, 0, 1); 520 assertMean(-1, -1, 0); 521 assertMean(-1, Integer.MIN_VALUE, Integer.MAX_VALUE); 522 523 // x == y == mean 524 assertMean(1, 1, 1); 525 assertMean(0, 0, 0); 526 assertMean(-1, -1, -1); 527 assertMean(Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE); 528 assertMean(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE); 529 530 // Exhaustive checks 531 for (int x : ALL_INTEGER_CANDIDATES) { 532 for (int y : ALL_INTEGER_CANDIDATES) { 533 assertMean(x, y); 534 } 535 } 536 } 537 538 /** 539 * Helper method that asserts the arithmetic mean of x and y is equal 540 * to the expectedMean. 541 */ 542 private static void assertMean(int expectedMean, int x, int y) { 543 assertEquals("The expectedMean should be the same as computeMeanSafely", 544 expectedMean, computeMeanSafely(x, y)); 545 assertMean(x, y); 546 } 547 548 /** 549 * Helper method that asserts the arithmetic mean of x and y is equal 550 * to the result of computeMeanSafely. 551 */ 552 private static void assertMean(int x, int y) { 553 int expectedMean = computeMeanSafely(x, y); 554 assertEquals(expectedMean, IntMath.mean(x, y)); 555 assertEquals("The mean of x and y should equal the mean of y and x", 556 expectedMean, IntMath.mean(y, x)); 557 } 558 559 /** 560 * Computes the mean in a way that is obvious and resilient to 561 * overflow by using BigInteger arithmetic. 562 */ 563 private static int computeMeanSafely(int x, int y) { 564 BigInteger bigX = BigInteger.valueOf(x); 565 BigInteger bigY = BigInteger.valueOf(y); 566 BigDecimal bigMean = new BigDecimal(bigX.add(bigY)) 567 .divide(BigDecimal.valueOf(2), BigDecimal.ROUND_FLOOR); 568 // parseInt blows up on overflow as opposed to intValue() which does not. 569 return Integer.parseInt(bigMean.toString()); 570 } 571 572 private static boolean fitsInInt(BigInteger big) { 573 return big.bitLength() <= 31; 574 } 575 576 @GwtIncompatible("NullPointerTester") 577 public void testNullPointers() { 578 NullPointerTester tester = new NullPointerTester(); 579 tester.setDefault(int.class, 1); 580 tester.testAllPublicStaticMethods(IntMath.class); 581 } 582 583 private static int force32(int value) { 584 // GWT doesn't consistently overflow values to make them 32-bit, so we need to force it. 585 return value & 0xffffffff; 586 } 587} 588