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_BIGINTEGER_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.NEGATIVE_BIGINTEGER_CANDIDATES;
23import static com.google.common.math.MathTesting.NEGATIVE_INTEGER_CANDIDATES;
24import static com.google.common.math.MathTesting.NONZERO_BIGINTEGER_CANDIDATES;
25import static com.google.common.math.MathTesting.POSITIVE_BIGINTEGER_CANDIDATES;
26import static java.math.BigInteger.ONE;
27import static java.math.BigInteger.TEN;
28import static java.math.BigInteger.ZERO;
29import static java.math.RoundingMode.CEILING;
30import static java.math.RoundingMode.DOWN;
31import static java.math.RoundingMode.FLOOR;
32import static java.math.RoundingMode.HALF_DOWN;
33import static java.math.RoundingMode.HALF_EVEN;
34import static java.math.RoundingMode.HALF_UP;
35import static java.math.RoundingMode.UNNECESSARY;
36import static java.math.RoundingMode.UP;
37import static java.util.Arrays.asList;
38
39import com.google.common.testing.NullPointerTester;
40
41import junit.framework.TestCase;
42
43import java.math.BigDecimal;
44import java.math.BigInteger;
45import java.math.RoundingMode;
46
47/**
48 * Tests for BigIntegerMath.
49 *
50 * @author Louis Wasserman
51 */
52public class BigIntegerMathTest extends TestCase {
53  public void testConstantSqrt2PrecomputedBits() {
54    assertEquals(BigIntegerMath.sqrt(
55        BigInteger.ZERO.setBit(2 * BigIntegerMath.SQRT2_PRECOMPUTE_THRESHOLD + 1), FLOOR),
56        BigIntegerMath.SQRT2_PRECOMPUTED_BITS);
57  }
58
59  public void testIsPowerOfTwo() {
60    for (BigInteger x : ALL_BIGINTEGER_CANDIDATES) {
61      // Checks for a single bit set.
62      boolean expected = x.signum() > 0 & x.and(x.subtract(ONE)).equals(ZERO);
63      assertEquals(expected, BigIntegerMath.isPowerOfTwo(x));
64    }
65  }
66
67  public void testLog2ZeroAlwaysThrows() {
68    for (RoundingMode mode : ALL_ROUNDING_MODES) {
69      try {
70        BigIntegerMath.log2(ZERO, mode);
71        fail("Expected IllegalArgumentException");
72      } catch (IllegalArgumentException expected) {}
73    }
74  }
75
76  public void testLog2NegativeAlwaysThrows() {
77    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
78      for (RoundingMode mode : ALL_ROUNDING_MODES) {
79        try {
80          BigIntegerMath.log2(x.negate(), mode);
81          fail("Expected IllegalArgumentException");
82        } catch (IllegalArgumentException expected) {}
83      }
84    }
85  }
86
87  public void testLog2Floor() {
88    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
89      for (RoundingMode mode : asList(FLOOR, DOWN)) {
90        int result = BigIntegerMath.log2(x, mode);
91        assertTrue(ZERO.setBit(result).compareTo(x) <= 0);
92        assertTrue(ZERO.setBit(result + 1).compareTo(x) > 0);
93      }
94    }
95  }
96
97  public void testLog2Ceiling() {
98    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
99      for (RoundingMode mode : asList(CEILING, UP)) {
100        int result = BigIntegerMath.log2(x, mode);
101        assertTrue(ZERO.setBit(result).compareTo(x) >= 0);
102        assertTrue(result == 0 || ZERO.setBit(result - 1).compareTo(x) < 0);
103      }
104    }
105  }
106
107  // Relies on the correctness of isPowerOfTwo(BigInteger).
108  public void testLog2Exact() {
109    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
110      // We only expect an exception if x was not a power of 2.
111      boolean isPowerOf2 = BigIntegerMath.isPowerOfTwo(x);
112      try {
113        assertEquals(x, ZERO.setBit(BigIntegerMath.log2(x, UNNECESSARY)));
114        assertTrue(isPowerOf2);
115      } catch (ArithmeticException e) {
116        assertFalse(isPowerOf2);
117      }
118    }
119  }
120
121  public void testLog2HalfUp() {
122    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
123      int result = BigIntegerMath.log2(x, HALF_UP);
124      BigInteger x2 = x.pow(2);
125      // x^2 < 2^(2 * result + 1), or else we would have rounded up
126      assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) > 0);
127      // x^2 >= 2^(2 * result - 1), or else we would have rounded down
128      assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) <= 0);
129    }
130  }
131
132  public void testLog2HalfDown() {
133    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
134      int result = BigIntegerMath.log2(x, HALF_DOWN);
135      BigInteger x2 = x.pow(2);
136      // x^2 <= 2^(2 * result + 1), or else we would have rounded up
137      assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) >= 0);
138      // x^2 > 2^(2 * result - 1), or else we would have rounded down
139      assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) < 0);
140    }
141  }
142
143  // Relies on the correctness of log2(BigInteger, {HALF_UP,HALF_DOWN}).
144  public void testLog2HalfEven() {
145    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
146      int halfEven = BigIntegerMath.log2(x, HALF_EVEN);
147      // Now figure out what rounding mode we should behave like (it depends if FLOOR was
148      // odd/even).
149      boolean floorWasEven = (BigIntegerMath.log2(x, FLOOR) & 1) == 0;
150      assertEquals(BigIntegerMath.log2(x, floorWasEven ? HALF_DOWN : HALF_UP), halfEven);
151    }
152  }
153
154  public void testLog10ZeroAlwaysThrows() {
155    for (RoundingMode mode : ALL_ROUNDING_MODES) {
156      try {
157        BigIntegerMath.log10(ZERO, mode);
158        fail("Expected IllegalArgumentException");
159      } catch (IllegalArgumentException expected) {}
160    }
161  }
162
163  public void testLog10NegativeAlwaysThrows() {
164    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
165      for (RoundingMode mode : ALL_ROUNDING_MODES) {
166        try {
167          BigIntegerMath.log10(x.negate(), mode);
168          fail("Expected IllegalArgumentException");
169        } catch (IllegalArgumentException expected) {}
170      }
171    }
172  }
173
174  public void testLog10Floor() {
175    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
176      for (RoundingMode mode : asList(FLOOR, DOWN)) {
177        int result = BigIntegerMath.log10(x, mode);
178        assertTrue(TEN.pow(result).compareTo(x) <= 0);
179        assertTrue(TEN.pow(result + 1).compareTo(x) > 0);
180      }
181    }
182  }
183
184  public void testLog10Ceiling() {
185    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
186      for (RoundingMode mode : asList(CEILING, UP)) {
187        int result = BigIntegerMath.log10(x, mode);
188        assertTrue(TEN.pow(result).compareTo(x) >= 0);
189        assertTrue(result == 0 || TEN.pow(result - 1).compareTo(x) < 0);
190      }
191    }
192  }
193
194  // Relies on the correctness of log10(BigInteger, FLOOR).
195  public void testLog10Exact() {
196    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
197      int logFloor = BigIntegerMath.log10(x, FLOOR);
198      boolean expectSuccess = TEN.pow(logFloor).equals(x);
199      try {
200        assertEquals(logFloor, BigIntegerMath.log10(x, UNNECESSARY));
201        assertTrue(expectSuccess);
202      } catch (ArithmeticException e) {
203        assertFalse(expectSuccess);
204      }
205    }
206  }
207
208  public void testLog10HalfUp() {
209    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
210      int result = BigIntegerMath.log10(x, HALF_UP);
211      BigInteger x2 = x.pow(2);
212      // x^2 < 10^(2 * result + 1), or else we would have rounded up
213      assertTrue(TEN.pow(2 * result + 1).compareTo(x2) > 0);
214      // x^2 >= 10^(2 * result - 1), or else we would have rounded down
215      assertTrue(result == 0 || TEN.pow(2 * result - 1).compareTo(x2) <= 0);
216    }
217  }
218
219  public void testLog10HalfDown() {
220    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
221      int result = BigIntegerMath.log10(x, HALF_DOWN);
222      BigInteger x2 = x.pow(2);
223      // x^2 <= 10^(2 * result + 1), or else we would have rounded up
224      assertTrue(TEN.pow(2 * result + 1).compareTo(x2) >= 0);
225      // x^2 > 10^(2 * result - 1), or else we would have rounded down
226      assertTrue(result == 0 || TEN.pow(2 * result - 1).compareTo(x2) < 0);
227    }
228  }
229
230  // Relies on the correctness of log10(BigInteger, {HALF_UP,HALF_DOWN}).
231  public void testLog10HalfEven() {
232    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
233      int halfEven = BigIntegerMath.log10(x, HALF_EVEN);
234      // Now figure out what rounding mode we should behave like (it depends if FLOOR was
235      // odd/even).
236      boolean floorWasEven = (BigIntegerMath.log10(x, FLOOR) & 1) == 0;
237      assertEquals(BigIntegerMath.log10(x, floorWasEven ? HALF_DOWN : HALF_UP), halfEven);
238    }
239  }
240
241  public void testLog10TrivialOnPowerOf10() {
242    BigInteger x = BigInteger.TEN.pow(100);
243    for (RoundingMode mode : ALL_ROUNDING_MODES) {
244      assertEquals(100, BigIntegerMath.log10(x, mode));
245    }
246  }
247
248  public void testSqrtZeroAlwaysZero() {
249    for (RoundingMode mode : ALL_ROUNDING_MODES) {
250      assertEquals(ZERO, BigIntegerMath.sqrt(ZERO, mode));
251    }
252  }
253
254  public void testSqrtNegativeAlwaysThrows() {
255    for (BigInteger x : NEGATIVE_BIGINTEGER_CANDIDATES) {
256      for (RoundingMode mode : ALL_ROUNDING_MODES) {
257        try {
258          BigIntegerMath.sqrt(x, mode);
259          fail("Expected IllegalArgumentException");
260        } catch (IllegalArgumentException expected) {}
261      }
262    }
263  }
264
265  public void testSqrtFloor() {
266    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
267      for (RoundingMode mode : asList(FLOOR, DOWN)) {
268        BigInteger result = BigIntegerMath.sqrt(x, mode);
269        assertTrue(result.compareTo(ZERO) > 0);
270        assertTrue(result.pow(2).compareTo(x) <= 0);
271        assertTrue(result.add(ONE).pow(2).compareTo(x) > 0);
272      }
273    }
274  }
275
276  public void testSqrtCeiling() {
277    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
278      for (RoundingMode mode : asList(CEILING, UP)) {
279        BigInteger result = BigIntegerMath.sqrt(x, mode);
280        assertTrue(result.compareTo(ZERO) > 0);
281        assertTrue(result.pow(2).compareTo(x) >= 0);
282        assertTrue(result.signum() == 0 || result.subtract(ONE).pow(2).compareTo(x) < 0);
283      }
284    }
285  }
286
287  // Relies on the correctness of sqrt(BigInteger, FLOOR).
288  public void testSqrtExact() {
289    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
290      BigInteger floor = BigIntegerMath.sqrt(x, FLOOR);
291      // We only expect an exception if x was not a perfect square.
292      boolean isPerfectSquare = floor.pow(2).equals(x);
293      try {
294        assertEquals(floor, BigIntegerMath.sqrt(x, UNNECESSARY));
295        assertTrue(isPerfectSquare);
296      } catch (ArithmeticException e) {
297        assertFalse(isPerfectSquare);
298      }
299    }
300  }
301
302  public void testSqrtHalfUp() {
303    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
304      BigInteger result = BigIntegerMath.sqrt(x, HALF_UP);
305      BigInteger plusHalfSquared = result.pow(2).add(result).shiftLeft(2).add(ONE);
306      BigInteger x4 = x.shiftLeft(2);
307      // sqrt(x) < result + 0.5, so 4 * x < (result + 0.5)^2 * 4
308      // (result + 0.5)^2 * 4 = (result^2 + result)*4 + 1
309      assertTrue(x4.compareTo(plusHalfSquared) < 0);
310      BigInteger minusHalfSquared = result.pow(2).subtract(result).shiftLeft(2).add(ONE);
311      // sqrt(x) > result - 0.5, so 4 * x > (result - 0.5)^2 * 4
312      // (result - 0.5)^2 * 4 = (result^2 - result)*4 + 1
313      assertTrue(result.equals(ZERO) || x4.compareTo(minusHalfSquared) >= 0);
314    }
315  }
316
317  public void testSqrtHalfDown() {
318    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
319      BigInteger result = BigIntegerMath.sqrt(x, HALF_DOWN);
320      BigInteger plusHalfSquared = result.pow(2).add(result).shiftLeft(2).add(ONE);
321      BigInteger x4 = x.shiftLeft(2);
322      // sqrt(x) <= result + 0.5, so 4 * x <= (result + 0.5)^2 * 4
323      // (result + 0.5)^2 * 4 = (result^2 + result)*4 + 1
324      assertTrue(x4.compareTo(plusHalfSquared) <= 0);
325      BigInteger minusHalfSquared = result.pow(2).subtract(result).shiftLeft(2).add(ONE);
326      // sqrt(x) > result - 0.5, so 4 * x > (result - 0.5)^2 * 4
327      // (result - 0.5)^2 * 4 = (result^2 - result)*4 + 1
328      assertTrue(result.equals(ZERO) || x4.compareTo(minusHalfSquared) > 0);
329    }
330  }
331
332  // Relies on the correctness of sqrt(BigInteger, {HALF_UP,HALF_DOWN}).
333  public void testSqrtHalfEven() {
334    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
335      BigInteger halfEven = BigIntegerMath.sqrt(x, HALF_EVEN);
336      // Now figure out what rounding mode we should behave like (it depends if FLOOR was
337      // odd/even).
338      boolean floorWasOdd = BigIntegerMath.sqrt(x, FLOOR).testBit(0);
339      assertEquals(BigIntegerMath.sqrt(x, floorWasOdd ? HALF_UP : HALF_DOWN), halfEven);
340    }
341  }
342
343  public void testDivNonZero() {
344    for (BigInteger p : NONZERO_BIGINTEGER_CANDIDATES) {
345      for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) {
346        for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) {
347          BigInteger expected =
348              new BigDecimal(p).divide(new BigDecimal(q), 0, mode).toBigIntegerExact();
349          assertEquals(expected, BigIntegerMath.divide(p, q, mode));
350        }
351      }
352    }
353  }
354
355  public void testDivNonZeroExact() {
356    for (BigInteger p : NONZERO_BIGINTEGER_CANDIDATES) {
357      for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) {
358        boolean dividesEvenly = p.remainder(q).equals(ZERO);
359
360        try {
361          assertEquals(p, BigIntegerMath.divide(p, q, UNNECESSARY).multiply(q));
362          assertTrue(dividesEvenly);
363        } catch (ArithmeticException e) {
364          assertFalse(dividesEvenly);
365        }
366      }
367    }
368  }
369
370  public void testZeroDivIsAlwaysZero() {
371    for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) {
372      for (RoundingMode mode : ALL_ROUNDING_MODES) {
373        assertEquals(ZERO, BigIntegerMath.divide(ZERO, q, mode));
374      }
375    }
376  }
377
378  public void testDivByZeroAlwaysFails() {
379    for (BigInteger p : ALL_BIGINTEGER_CANDIDATES) {
380      for (RoundingMode mode : ALL_ROUNDING_MODES) {
381        try {
382          BigIntegerMath.divide(p, ZERO, mode);
383          fail("Expected ArithmeticException");
384        } catch (ArithmeticException expected) {}
385      }
386    }
387  }
388
389  public void testFactorial() {
390    BigInteger expected = BigInteger.ONE;
391    for (int i = 1; i <= 300; i++) {
392      expected = expected.multiply(BigInteger.valueOf(i));
393      assertEquals(expected, BigIntegerMath.factorial(i));
394    }
395  }
396
397  public void testFactorial0() {
398    assertEquals(BigInteger.ONE, BigIntegerMath.factorial(0));
399  }
400
401  public void testFactorialNegative() {
402    for (int n : NEGATIVE_INTEGER_CANDIDATES) {
403      try {
404        BigIntegerMath.factorial(n);
405        fail("Expected IllegalArgumentException");
406      } catch (IllegalArgumentException expected) {}
407    }
408  }
409
410  // Depends on the correctness of BigIntegerMath.factorial
411  public void testBinomial() {
412    for (int n = 0; n <= 50; n++) {
413      for (int k = 0; k <= n; k++) {
414        BigInteger expected = BigIntegerMath
415            .factorial(n)
416            .divide(BigIntegerMath.factorial(k))
417            .divide(BigIntegerMath.factorial(n - k));
418        assertEquals(expected, BigIntegerMath.binomial(n, k));
419      }
420    }
421  }
422
423  public void testBinomialOutside() {
424    for (int n = 0; n <= 50; n++) {
425      try {
426        BigIntegerMath.binomial(n, -1);
427        fail("Expected IllegalArgumentException");
428      } catch (IllegalArgumentException expected) {}
429      try {
430        BigIntegerMath.binomial(n, n + 1);
431        fail("Expected IllegalArgumentException");
432      } catch (IllegalArgumentException expected) {}
433    }
434  }
435
436  public void testNullPointers() throws Exception {
437    NullPointerTester tester = new NullPointerTester();
438    tester.setDefault(BigInteger.class, ONE);
439    tester.setDefault(RoundingMode.class, FLOOR);
440    tester.setDefault(int.class, 1);
441    tester.setDefault(long.class, 1L);
442    tester.testAllPublicStaticMethods(BigIntegerMath.class);
443  }
444}
445