1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package com.google.common.math;
18
19 import static com.google.common.math.MathTesting.ALL_INTEGER_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.EXPONENTS;
23 import static com.google.common.math.MathTesting.NEGATIVE_INTEGER_CANDIDATES;
24 import static com.google.common.math.MathTesting.NONZERO_INTEGER_CANDIDATES;
25 import static com.google.common.math.MathTesting.POSITIVE_INTEGER_CANDIDATES;
26 import static com.google.common.math.TestPlatform.intsCanGoOutOfRange;
27 import static java.math.BigInteger.valueOf;
28 import static java.math.RoundingMode.FLOOR;
29 import static java.math.RoundingMode.UNNECESSARY;
30
31 import com.google.common.annotations.GwtCompatible;
32 import com.google.common.annotations.GwtIncompatible;
33 import com.google.common.testing.NullPointerTester;
34
35 import junit.framework.TestCase;
36
37 import java.math.BigDecimal;
38 import java.math.BigInteger;
39 import java.math.RoundingMode;
40
41
42
43
44
45
46 @GwtCompatible(emulated = true)
47 public class IntMathTest extends TestCase {
48 @GwtIncompatible("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")
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")
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")
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
87
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 public void testLessThanBranchFree() {
100 for (int x : ALL_INTEGER_CANDIDATES) {
101 for (int y : ALL_INTEGER_CANDIDATES) {
102 if (LongMath.fitsInInt((long) x - y)) {
103 int expected = (x < y) ? 1 : 0;
104 int actual = IntMath.lessThanBranchFree(x, y);
105 assertEquals(expected, actual);
106 }
107 }
108 }
109 }
110
111 @GwtIncompatible("java.math.BigInteger")
112 public void testIsPowerOfTwo() {
113 for (int x : ALL_INTEGER_CANDIDATES) {
114
115 BigInteger bigX = BigInteger.valueOf(x);
116 boolean expected = (bigX.signum() > 0) && (bigX.bitCount() == 1);
117 assertEquals(expected, IntMath.isPowerOfTwo(x));
118 }
119 }
120
121 public void testLog2ZeroAlwaysThrows() {
122 for (RoundingMode mode : ALL_ROUNDING_MODES) {
123 try {
124 IntMath.log2(0, mode);
125 fail("Expected IllegalArgumentException");
126 } catch (IllegalArgumentException expected) {}
127 }
128 }
129
130 public void testLog2NegativeAlwaysThrows() {
131 for (int x : NEGATIVE_INTEGER_CANDIDATES) {
132 for (RoundingMode mode : ALL_ROUNDING_MODES) {
133 try {
134 IntMath.log2(x, mode);
135 fail("Expected IllegalArgumentException");
136 } catch (IllegalArgumentException expected) {}
137 }
138 }
139 }
140
141
142 public void testLog2MatchesBigInteger() {
143 for (int x : POSITIVE_INTEGER_CANDIDATES) {
144 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) {
145 assertEquals(BigIntegerMath.log2(valueOf(x), mode), IntMath.log2(x, mode));
146 }
147 }
148 }
149
150
151 public void testLog2Exact() {
152 for (int x : POSITIVE_INTEGER_CANDIDATES) {
153
154 boolean isPowerOf2 = IntMath.isPowerOfTwo(x);
155 try {
156 assertEquals(x, 1 << IntMath.log2(x, UNNECESSARY));
157 assertTrue(isPowerOf2);
158 } catch (ArithmeticException e) {
159 assertFalse(isPowerOf2);
160 }
161 }
162 }
163
164 @GwtIncompatible("log10")
165 public void testLog10ZeroAlwaysThrows() {
166 for (RoundingMode mode : ALL_ROUNDING_MODES) {
167 try {
168 IntMath.log10(0, mode);
169 fail("Expected IllegalArgumentException");
170 } catch (IllegalArgumentException expected) {}
171 }
172 }
173
174 @GwtIncompatible("log10")
175 public void testLog10NegativeAlwaysThrows() {
176 for (int x : NEGATIVE_INTEGER_CANDIDATES) {
177 for (RoundingMode mode : ALL_ROUNDING_MODES) {
178 try {
179 IntMath.log10(x, mode);
180 fail("Expected IllegalArgumentException");
181 } catch (IllegalArgumentException expected) {}
182 }
183 }
184 }
185
186
187 @GwtIncompatible("BigIntegerMath")
188 public void testLog10MatchesBigInteger() {
189 for (int x : POSITIVE_INTEGER_CANDIDATES) {
190 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) {
191
192 assertEquals(BigIntegerMath.log10(valueOf(x), mode), IntMath.log10(x, mode));
193 }
194 }
195 }
196
197
198 @GwtIncompatible("pow()")
199 public void testLog10Exact() {
200 for (int x : POSITIVE_INTEGER_CANDIDATES) {
201 int floor = IntMath.log10(x, FLOOR);
202 boolean expectSuccess = IntMath.pow(10, floor) == x;
203 try {
204 assertEquals(floor, IntMath.log10(x, UNNECESSARY));
205 assertTrue(expectSuccess);
206 } catch (ArithmeticException e) {
207 assertFalse(expectSuccess);
208 }
209 }
210 }
211
212 @GwtIncompatible("log10")
213 public void testLog10TrivialOnPowerOfTen() {
214 int x = 1000000;
215 for (RoundingMode mode : ALL_ROUNDING_MODES) {
216 assertEquals(6, IntMath.log10(x, mode));
217 }
218 }
219
220
221 @GwtIncompatible("sqrt")
222 public void testSqrtZeroAlwaysZero() {
223 for (RoundingMode mode : ALL_ROUNDING_MODES) {
224 assertEquals(0, IntMath.sqrt(0, mode));
225 }
226 }
227
228 @GwtIncompatible("sqrt")
229 public void testSqrtNegativeAlwaysThrows() {
230 for (int x : NEGATIVE_INTEGER_CANDIDATES) {
231 for (RoundingMode mode : RoundingMode.values()) {
232 try {
233 IntMath.sqrt(x, mode);
234 fail("Expected IllegalArgumentException");
235 } catch (IllegalArgumentException expected) {}
236 }
237 }
238 }
239
240
241 @GwtIncompatible("BigIntegerMath")
242 public void testSqrtMatchesBigInteger() {
243 for (int x : POSITIVE_INTEGER_CANDIDATES) {
244 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) {
245
246
247
248 assertEquals(BigIntegerMath.sqrt(valueOf(x), mode), valueOf(IntMath.sqrt(x, mode)));
249 }
250 }
251 }
252
253
254 @GwtIncompatible("sqrt")
255 public void testSqrtExactMatchesFloorOrThrows() {
256 for (int x : POSITIVE_INTEGER_CANDIDATES) {
257 int floor = IntMath.sqrt(x, FLOOR);
258
259 boolean isPerfectSquare = (floor * floor == x);
260 try {
261 assertEquals(floor, IntMath.sqrt(x, UNNECESSARY));
262 assertTrue(isPerfectSquare);
263 } catch (ArithmeticException e) {
264 assertFalse(isPerfectSquare);
265 }
266 }
267 }
268
269 @GwtIncompatible("2147483646^2 expected=4")
270 public void testPow() {
271 for (int i : ALL_INTEGER_CANDIDATES) {
272 for (int pow : EXPONENTS) {
273 assertEquals(i + "^" + pow, BigInteger.valueOf(i).pow(pow).intValue(), IntMath.pow(i, pow));
274 }
275 }
276 }
277
278 public void testDivNonZero() {
279 for (int p : NONZERO_INTEGER_CANDIDATES) {
280 for (int q : NONZERO_INTEGER_CANDIDATES) {
281 for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) {
282
283
284 if (p == -2147483648 && q == -1 && intsCanGoOutOfRange()) {
285 continue;
286 }
287 int expected =
288 new BigDecimal(valueOf(p)).divide(new BigDecimal(valueOf(q)), 0, mode).intValue();
289 assertEquals(p + "/" + q, force32(expected), IntMath.divide(p, q, mode));
290 }
291 }
292 }
293 }
294
295 public void testDivNonZeroExact() {
296 for (int p : NONZERO_INTEGER_CANDIDATES) {
297 for (int q : NONZERO_INTEGER_CANDIDATES) {
298
299 if (p == -2147483648 && q == -1 && intsCanGoOutOfRange()) {
300 continue;
301 }
302 boolean dividesEvenly = (p % q) == 0;
303 try {
304 assertEquals(p + "/" + q, p, IntMath.divide(p, q, UNNECESSARY) * q);
305 assertTrue(p + "/" + q + " not expected to divide evenly", dividesEvenly);
306 } catch (ArithmeticException e) {
307 assertFalse(p + "/" + q + " expected to divide evenly", dividesEvenly);
308 }
309 }
310 }
311 }
312
313 public void testZeroDivIsAlwaysZero() {
314 for (int q : NONZERO_INTEGER_CANDIDATES) {
315 for (RoundingMode mode : ALL_ROUNDING_MODES) {
316 assertEquals(0, IntMath.divide(0, q, mode));
317 }
318 }
319 }
320
321 public void testDivByZeroAlwaysFails() {
322 for (int p : ALL_INTEGER_CANDIDATES) {
323 for (RoundingMode mode : ALL_ROUNDING_MODES) {
324 try {
325 IntMath.divide(p, 0, mode);
326 fail("Expected ArithmeticException");
327 } catch (ArithmeticException expected) {}
328 }
329 }
330 }
331
332 public void testMod() {
333 for (int x : ALL_INTEGER_CANDIDATES) {
334 for (int m : POSITIVE_INTEGER_CANDIDATES) {
335 assertEquals(valueOf(x).mod(valueOf(m)).intValue(), IntMath.mod(x, m));
336 }
337 }
338 }
339
340 public void testModNegativeModulusFails() {
341 for (int x : POSITIVE_INTEGER_CANDIDATES) {
342 for (int m : NEGATIVE_INTEGER_CANDIDATES) {
343 try {
344 IntMath.mod(x, m);
345 fail("Expected ArithmeticException");
346 } catch (ArithmeticException expected) {}
347 }
348 }
349 }
350
351 public void testModZeroModulusFails() {
352 for (int x : ALL_INTEGER_CANDIDATES) {
353 try {
354 IntMath.mod(x, 0);
355 fail("Expected ArithmeticException");
356 } catch (ArithmeticException expected) {}
357 }
358 }
359
360 public void testGCD() {
361 for (int a : POSITIVE_INTEGER_CANDIDATES) {
362 for (int b : POSITIVE_INTEGER_CANDIDATES) {
363 assertEquals(valueOf(a).gcd(valueOf(b)), valueOf(IntMath.gcd(a, b)));
364 }
365 }
366 }
367
368 public void testGCDZero() {
369 for (int a : POSITIVE_INTEGER_CANDIDATES) {
370 assertEquals(a, IntMath.gcd(a, 0));
371 assertEquals(a, IntMath.gcd(0, a));
372 }
373 assertEquals(0, IntMath.gcd(0, 0));
374 }
375
376 public void testGCDNegativePositiveThrows() {
377 for (int a : NEGATIVE_INTEGER_CANDIDATES) {
378 try {
379 IntMath.gcd(a, 3);
380 fail("Expected IllegalArgumentException");
381 } catch (IllegalArgumentException expected) {}
382 try {
383 IntMath.gcd(3, a);
384 fail("Expected IllegalArgumentException");
385 } catch (IllegalArgumentException expected) {}
386 }
387 }
388
389 public void testGCDNegativeZeroThrows() {
390 for (int a : NEGATIVE_INTEGER_CANDIDATES) {
391 try {
392 IntMath.gcd(a, 0);
393 fail("Expected IllegalArgumentException");
394 } catch (IllegalArgumentException expected) {}
395 try {
396 IntMath.gcd(0, a);
397 fail("Expected IllegalArgumentException");
398 } catch (IllegalArgumentException expected) {}
399 }
400 }
401
402 public void testCheckedAdd() {
403 for (int a : ALL_INTEGER_CANDIDATES) {
404 for (int b : ALL_INTEGER_CANDIDATES) {
405 BigInteger expectedResult = valueOf(a).add(valueOf(b));
406 boolean expectedSuccess = fitsInInt(expectedResult);
407 try {
408 assertEquals(a + b, IntMath.checkedAdd(a, b));
409 assertTrue(expectedSuccess);
410 } catch (ArithmeticException e) {
411 assertFalse(expectedSuccess);
412 }
413 }
414 }
415 }
416
417 public void testCheckedSubtract() {
418 for (int a : ALL_INTEGER_CANDIDATES) {
419 for (int b : ALL_INTEGER_CANDIDATES) {
420 BigInteger expectedResult = valueOf(a).subtract(valueOf(b));
421 boolean expectedSuccess = fitsInInt(expectedResult);
422 try {
423 assertEquals(a - b, IntMath.checkedSubtract(a, b));
424 assertTrue(expectedSuccess);
425 } catch (ArithmeticException e) {
426 assertFalse(expectedSuccess);
427 }
428 }
429 }
430 }
431
432 public void testCheckedMultiply() {
433 for (int a : ALL_INTEGER_CANDIDATES) {
434 for (int b : ALL_INTEGER_CANDIDATES) {
435 BigInteger expectedResult = valueOf(a).multiply(valueOf(b));
436 boolean expectedSuccess = fitsInInt(expectedResult);
437 try {
438 assertEquals(a * b, IntMath.checkedMultiply(a, b));
439 assertTrue(expectedSuccess);
440 } catch (ArithmeticException e) {
441 assertFalse(expectedSuccess);
442 }
443 }
444 }
445 }
446
447 public void testCheckedPow() {
448 for (int b : ALL_INTEGER_CANDIDATES) {
449 for (int k : EXPONENTS) {
450 BigInteger expectedResult = valueOf(b).pow(k);
451 boolean expectedSuccess = fitsInInt(expectedResult);
452 try {
453 assertEquals(b + "^" + k, force32(expectedResult.intValue()), IntMath.checkedPow(b, k));
454 assertTrue(b + "^" + k + " should have succeeded", expectedSuccess);
455 } catch (ArithmeticException e) {
456 assertFalse(b + "^" + k + " should have failed", expectedSuccess);
457 }
458 }
459 }
460 }
461
462
463 public void testFactorial() {
464 for (int n = 0; n <= 50; n++) {
465 BigInteger expectedBig = BigIntegerMath.factorial(n);
466 int expectedInt = fitsInInt(expectedBig) ? expectedBig.intValue() : Integer.MAX_VALUE;
467 assertEquals(expectedInt, IntMath.factorial(n));
468 }
469 }
470
471 public void testFactorialNegative() {
472 for (int n : NEGATIVE_INTEGER_CANDIDATES) {
473 try {
474 IntMath.factorial(n);
475 fail("Expected IllegalArgumentException");
476 } catch (IllegalArgumentException expected) {}
477 }
478 }
479
480
481 @GwtIncompatible("BigIntegerMath")
482 public void testBinomial() {
483 for (int n = 0; n <= 50; n++) {
484 for (int k = 0; k <= n; k++) {
485 BigInteger expectedBig = BigIntegerMath.binomial(n, k);
486 int expectedInt = fitsInInt(expectedBig) ? expectedBig.intValue() : Integer.MAX_VALUE;
487 assertEquals(expectedInt, IntMath.binomial(n, k));
488 }
489 }
490 }
491
492 @GwtIncompatible("binomial")
493 public void testBinomialOutside() {
494 for (int n = 0; n <= 50; n++) {
495 try {
496 IntMath.binomial(n, -1);
497 fail("Expected IllegalArgumentException");
498 } catch (IllegalArgumentException expected) {}
499 try {
500 IntMath.binomial(n, n + 1);
501 fail("Expected IllegalArgumentException");
502 } catch (IllegalArgumentException expected) {}
503 }
504 }
505
506 @GwtIncompatible("binomial")
507 public void testBinomialNegative() {
508 for (int n : NEGATIVE_INTEGER_CANDIDATES) {
509 try {
510 IntMath.binomial(n, 0);
511 fail("Expected IllegalArgumentException");
512 } catch (IllegalArgumentException expected) {}
513 }
514 }
515
516 @GwtIncompatible("java.math.BigInteger")
517 public void testMean() {
518
519 assertMean(2, 1, 3);
520
521 assertMean(-2, -3, -1);
522 assertMean(0, -1, 1);
523 assertMean(1, -1, 3);
524 assertMean((1 << 30) - 1, -1, Integer.MAX_VALUE);
525
526
527 assertMean(2, 1, 4);
528 assertMean(-3, -4, -1);
529 assertMean(0, -1, 2);
530 assertMean(0, Integer.MIN_VALUE + 2, Integer.MAX_VALUE);
531 assertMean(0, 0, 1);
532 assertMean(-1, -1, 0);
533 assertMean(-1, Integer.MIN_VALUE, Integer.MAX_VALUE);
534
535
536 assertMean(1, 1, 1);
537 assertMean(0, 0, 0);
538 assertMean(-1, -1, -1);
539 assertMean(Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE);
540 assertMean(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE);
541
542
543 for (int x : ALL_INTEGER_CANDIDATES) {
544 for (int y : ALL_INTEGER_CANDIDATES) {
545 assertMean(x, y);
546 }
547 }
548 }
549
550
551
552
553
554 private static void assertMean(int expectedMean, int x, int y) {
555 assertEquals("The expectedMean should be the same as computeMeanSafely",
556 expectedMean, computeMeanSafely(x, y));
557 assertMean(x, y);
558 }
559
560
561
562
563
564 private static void assertMean(int x, int y) {
565 int expectedMean = computeMeanSafely(x, y);
566 assertEquals(expectedMean, IntMath.mean(x, y));
567 assertEquals("The mean of x and y should equal the mean of y and x",
568 expectedMean, IntMath.mean(y, x));
569 }
570
571
572
573
574
575 private static int computeMeanSafely(int x, int y) {
576 BigInteger bigX = BigInteger.valueOf(x);
577 BigInteger bigY = BigInteger.valueOf(y);
578 BigDecimal bigMean = new BigDecimal(bigX.add(bigY))
579 .divide(BigDecimal.valueOf(2), BigDecimal.ROUND_FLOOR);
580
581 return Integer.parseInt(bigMean.toString());
582 }
583
584 private static boolean fitsInInt(BigInteger big) {
585 return big.bitLength() <= 31;
586 }
587
588 @GwtIncompatible("NullPointerTester")
589 public void testNullPointers() {
590 NullPointerTester tester = new NullPointerTester();
591 tester.setDefault(int.class, 1);
592 tester.testAllPublicStaticMethods(IntMath.class);
593 }
594
595 private static int force32(int value) {
596
597 return value & 0xffffffff;
598 }
599 }