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.NONZERO_BIGINTEGER_CANDIDATES;
23import static com.google.common.math.MathTesting.POSITIVE_BIGINTEGER_CANDIDATES;
24import static java.math.BigInteger.ONE;
25import static java.math.BigInteger.TEN;
26import static java.math.BigInteger.ZERO;
27import static java.math.RoundingMode.CEILING;
28import static java.math.RoundingMode.DOWN;
29import static java.math.RoundingMode.FLOOR;
30import static java.math.RoundingMode.HALF_DOWN;
31import static java.math.RoundingMode.HALF_EVEN;
32import static java.math.RoundingMode.HALF_UP;
33import static java.math.RoundingMode.UNNECESSARY;
34import static java.math.RoundingMode.UP;
35import static java.util.Arrays.asList;
36
37import com.google.common.annotations.GwtCompatible;
38import com.google.common.annotations.GwtIncompatible;
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 */
52@GwtCompatible(emulated = true)
53public class BigIntegerMathTest extends TestCase {
54  @GwtIncompatible("TODO")
55  public void testConstantSqrt2PrecomputedBits() {
56    assertEquals(BigIntegerMath.sqrt(
57        BigInteger.ZERO.setBit(2 * BigIntegerMath.SQRT2_PRECOMPUTE_THRESHOLD + 1), FLOOR),
58        BigIntegerMath.SQRT2_PRECOMPUTED_BITS);
59  }
60
61  public void testIsPowerOfTwo() {
62    for (BigInteger x : ALL_BIGINTEGER_CANDIDATES) {
63      // Checks for a single bit set.
64      boolean expected = x.signum() > 0 & x.and(x.subtract(ONE)).equals(ZERO);
65      assertEquals(expected, BigIntegerMath.isPowerOfTwo(x));
66    }
67  }
68
69  public void testLog2ZeroAlwaysThrows() {
70    for (RoundingMode mode : ALL_ROUNDING_MODES) {
71      try {
72        BigIntegerMath.log2(ZERO, mode);
73        fail("Expected IllegalArgumentException");
74      } catch (IllegalArgumentException expected) {}
75    }
76  }
77
78  public void testLog2NegativeAlwaysThrows() {
79    for (RoundingMode mode : ALL_ROUNDING_MODES) {
80      try {
81        BigIntegerMath.log2(BigInteger.valueOf(-1), mode);
82        fail("Expected IllegalArgumentException");
83      } catch (IllegalArgumentException expected) {}
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  @GwtIncompatible("TODO")
155  public void testLog10ZeroAlwaysThrows() {
156    for (RoundingMode mode : ALL_ROUNDING_MODES) {
157      try {
158        BigIntegerMath.log10(ZERO, mode);
159        fail("Expected IllegalArgumentException");
160      } catch (IllegalArgumentException expected) {}
161    }
162  }
163
164  @GwtIncompatible("TODO")
165  public void testLog10NegativeAlwaysThrows() {
166    for (RoundingMode mode : ALL_ROUNDING_MODES) {
167      try {
168        BigIntegerMath.log10(BigInteger.valueOf(-1), mode);
169        fail("Expected IllegalArgumentException");
170      } catch (IllegalArgumentException expected) {}
171    }
172  }
173
174  @GwtIncompatible("TODO")
175  public void testLog10Floor() {
176    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
177      for (RoundingMode mode : asList(FLOOR, DOWN)) {
178        int result = BigIntegerMath.log10(x, mode);
179        assertTrue(TEN.pow(result).compareTo(x) <= 0);
180        assertTrue(TEN.pow(result + 1).compareTo(x) > 0);
181      }
182    }
183  }
184
185  @GwtIncompatible("TODO")
186  public void testLog10Ceiling() {
187    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
188      for (RoundingMode mode : asList(CEILING, UP)) {
189        int result = BigIntegerMath.log10(x, mode);
190        assertTrue(TEN.pow(result).compareTo(x) >= 0);
191        assertTrue(result == 0 || TEN.pow(result - 1).compareTo(x) < 0);
192      }
193    }
194  }
195
196  // Relies on the correctness of log10(BigInteger, FLOOR).
197  @GwtIncompatible("TODO")
198  public void testLog10Exact() {
199    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
200      int logFloor = BigIntegerMath.log10(x, FLOOR);
201      boolean expectSuccess = TEN.pow(logFloor).equals(x);
202      try {
203        assertEquals(logFloor, BigIntegerMath.log10(x, UNNECESSARY));
204        assertTrue(expectSuccess);
205      } catch (ArithmeticException e) {
206        assertFalse(expectSuccess);
207      }
208    }
209  }
210
211  @GwtIncompatible("TODO")
212  public void testLog10HalfUp() {
213    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
214      int result = BigIntegerMath.log10(x, HALF_UP);
215      BigInteger x2 = x.pow(2);
216      // x^2 < 10^(2 * result + 1), or else we would have rounded up
217      assertTrue(TEN.pow(2 * result + 1).compareTo(x2) > 0);
218      // x^2 >= 10^(2 * result - 1), or else we would have rounded down
219      assertTrue(result == 0 || TEN.pow(2 * result - 1).compareTo(x2) <= 0);
220    }
221  }
222
223  @GwtIncompatible("TODO")
224  public void testLog10HalfDown() {
225    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
226      int result = BigIntegerMath.log10(x, HALF_DOWN);
227      BigInteger x2 = x.pow(2);
228      // x^2 <= 10^(2 * result + 1), or else we would have rounded up
229      assertTrue(TEN.pow(2 * result + 1).compareTo(x2) >= 0);
230      // x^2 > 10^(2 * result - 1), or else we would have rounded down
231      assertTrue(result == 0 || TEN.pow(2 * result - 1).compareTo(x2) < 0);
232    }
233  }
234
235  // Relies on the correctness of log10(BigInteger, {HALF_UP,HALF_DOWN}).
236  @GwtIncompatible("TODO")
237  public void testLog10HalfEven() {
238    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
239      int halfEven = BigIntegerMath.log10(x, HALF_EVEN);
240      // Now figure out what rounding mode we should behave like (it depends if FLOOR was
241      // odd/even).
242      boolean floorWasEven = (BigIntegerMath.log10(x, FLOOR) & 1) == 0;
243      assertEquals(BigIntegerMath.log10(x, floorWasEven ? HALF_DOWN : HALF_UP), halfEven);
244    }
245  }
246
247  @GwtIncompatible("TODO")
248  public void testLog10TrivialOnPowerOf10() {
249    BigInteger x = BigInteger.TEN.pow(100);
250    for (RoundingMode mode : ALL_ROUNDING_MODES) {
251      assertEquals(100, BigIntegerMath.log10(x, mode));
252    }
253  }
254
255  @GwtIncompatible("TODO")
256  public void testSqrtZeroAlwaysZero() {
257    for (RoundingMode mode : ALL_ROUNDING_MODES) {
258      assertEquals(ZERO, BigIntegerMath.sqrt(ZERO, mode));
259    }
260  }
261
262  @GwtIncompatible("TODO")
263  public void testSqrtNegativeAlwaysThrows() {
264    for (RoundingMode mode : ALL_ROUNDING_MODES) {
265      try {
266        BigIntegerMath.sqrt(BigInteger.valueOf(-1), mode);
267        fail("Expected IllegalArgumentException");
268      } catch (IllegalArgumentException expected) {}
269    }
270  }
271
272  @GwtIncompatible("TODO")
273  public void testSqrtFloor() {
274    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
275      for (RoundingMode mode : asList(FLOOR, DOWN)) {
276        BigInteger result = BigIntegerMath.sqrt(x, mode);
277        assertTrue(result.compareTo(ZERO) > 0);
278        assertTrue(result.pow(2).compareTo(x) <= 0);
279        assertTrue(result.add(ONE).pow(2).compareTo(x) > 0);
280      }
281    }
282  }
283
284  @GwtIncompatible("TODO")
285  public void testSqrtCeiling() {
286    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
287      for (RoundingMode mode : asList(CEILING, UP)) {
288        BigInteger result = BigIntegerMath.sqrt(x, mode);
289        assertTrue(result.compareTo(ZERO) > 0);
290        assertTrue(result.pow(2).compareTo(x) >= 0);
291        assertTrue(result.signum() == 0 || result.subtract(ONE).pow(2).compareTo(x) < 0);
292      }
293    }
294  }
295
296  // Relies on the correctness of sqrt(BigInteger, FLOOR).
297  @GwtIncompatible("TODO")
298  public void testSqrtExact() {
299    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
300      BigInteger floor = BigIntegerMath.sqrt(x, FLOOR);
301      // We only expect an exception if x was not a perfect square.
302      boolean isPerfectSquare = floor.pow(2).equals(x);
303      try {
304        assertEquals(floor, BigIntegerMath.sqrt(x, UNNECESSARY));
305        assertTrue(isPerfectSquare);
306      } catch (ArithmeticException e) {
307        assertFalse(isPerfectSquare);
308      }
309    }
310  }
311
312  @GwtIncompatible("TODO")
313  public void testSqrtHalfUp() {
314    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
315      BigInteger result = BigIntegerMath.sqrt(x, HALF_UP);
316      BigInteger plusHalfSquared = result.pow(2).add(result).shiftLeft(2).add(ONE);
317      BigInteger x4 = x.shiftLeft(2);
318      // sqrt(x) < result + 0.5, so 4 * x < (result + 0.5)^2 * 4
319      // (result + 0.5)^2 * 4 = (result^2 + result)*4 + 1
320      assertTrue(x4.compareTo(plusHalfSquared) < 0);
321      BigInteger minusHalfSquared = result.pow(2).subtract(result).shiftLeft(2).add(ONE);
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(result.equals(ZERO) || x4.compareTo(minusHalfSquared) >= 0);
325    }
326  }
327
328  @GwtIncompatible("TODO")
329  public void testSqrtHalfDown() {
330    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
331      BigInteger result = BigIntegerMath.sqrt(x, HALF_DOWN);
332      BigInteger plusHalfSquared = result.pow(2).add(result).shiftLeft(2).add(ONE);
333      BigInteger x4 = x.shiftLeft(2);
334      // sqrt(x) <= result + 0.5, so 4 * x <= (result + 0.5)^2 * 4
335      // (result + 0.5)^2 * 4 = (result^2 + result)*4 + 1
336      assertTrue(x4.compareTo(plusHalfSquared) <= 0);
337      BigInteger minusHalfSquared = result.pow(2).subtract(result).shiftLeft(2).add(ONE);
338      // sqrt(x) > result - 0.5, so 4 * x > (result - 0.5)^2 * 4
339      // (result - 0.5)^2 * 4 = (result^2 - result)*4 + 1
340      assertTrue(result.equals(ZERO) || x4.compareTo(minusHalfSquared) > 0);
341    }
342  }
343
344  // Relies on the correctness of sqrt(BigInteger, {HALF_UP,HALF_DOWN}).
345  @GwtIncompatible("TODO")
346  public void testSqrtHalfEven() {
347    for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
348      BigInteger halfEven = BigIntegerMath.sqrt(x, HALF_EVEN);
349      // Now figure out what rounding mode we should behave like (it depends if FLOOR was
350      // odd/even).
351      boolean floorWasOdd = BigIntegerMath.sqrt(x, FLOOR).testBit(0);
352      assertEquals(BigIntegerMath.sqrt(x, floorWasOdd ? HALF_UP : HALF_DOWN), halfEven);
353    }
354  }
355
356  @GwtIncompatible("TODO")
357  public void testDivNonZero() {
358    for (BigInteger p : NONZERO_BIGINTEGER_CANDIDATES) {
359      for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) {
360        for (RoundingMode mode : ALL_SAFE_ROUNDING_MODES) {
361          BigInteger expected =
362              new BigDecimal(p).divide(new BigDecimal(q), 0, mode).toBigIntegerExact();
363          assertEquals(expected, BigIntegerMath.divide(p, q, mode));
364        }
365      }
366    }
367  }
368
369  @GwtIncompatible("TODO")
370  public void testDivNonZeroExact() {
371    for (BigInteger p : NONZERO_BIGINTEGER_CANDIDATES) {
372      for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) {
373        boolean dividesEvenly = p.remainder(q).equals(ZERO);
374
375        try {
376          assertEquals(p, BigIntegerMath.divide(p, q, UNNECESSARY).multiply(q));
377          assertTrue(dividesEvenly);
378        } catch (ArithmeticException e) {
379          assertFalse(dividesEvenly);
380        }
381      }
382    }
383  }
384
385  @GwtIncompatible("TODO")
386  public void testZeroDivIsAlwaysZero() {
387    for (BigInteger q : NONZERO_BIGINTEGER_CANDIDATES) {
388      for (RoundingMode mode : ALL_ROUNDING_MODES) {
389        assertEquals(ZERO, BigIntegerMath.divide(ZERO, q, mode));
390      }
391    }
392  }
393
394  @GwtIncompatible("TODO")
395  public void testDivByZeroAlwaysFails() {
396    for (BigInteger p : ALL_BIGINTEGER_CANDIDATES) {
397      for (RoundingMode mode : ALL_ROUNDING_MODES) {
398        try {
399          BigIntegerMath.divide(p, ZERO, mode);
400          fail("Expected ArithmeticException");
401        } catch (ArithmeticException expected) {}
402      }
403    }
404  }
405
406  public void testFactorial() {
407    BigInteger expected = BigInteger.ONE;
408    for (int i = 1; i <= 200; i++) {
409      expected = expected.multiply(BigInteger.valueOf(i));
410      assertEquals(expected, BigIntegerMath.factorial(i));
411    }
412  }
413
414  public void testFactorial0() {
415    assertEquals(BigInteger.ONE, BigIntegerMath.factorial(0));
416  }
417
418  public void testFactorialNegative() {
419    try {
420      BigIntegerMath.factorial(-1);
421      fail("Expected IllegalArgumentException");
422    } catch (IllegalArgumentException expected) {}
423  }
424
425  public void testBinomialSmall() {
426    runBinomialTest(0, 30);
427  }
428
429  @GwtIncompatible("too slow")
430  public void testBinomialLarge() {
431    runBinomialTest(31, 100);
432  }
433
434  // Depends on the correctness of BigIntegerMath.factorial
435  private static void runBinomialTest(int firstN, int lastN) {
436    for (int n = firstN; n <= lastN; n++) {
437      for (int k = 0; k <= n; k++) {
438        BigInteger expected = BigIntegerMath
439            .factorial(n)
440            .divide(BigIntegerMath.factorial(k))
441            .divide(BigIntegerMath.factorial(n - k));
442        assertEquals(expected, BigIntegerMath.binomial(n, k));
443      }
444    }
445  }
446
447  public void testBinomialOutside() {
448    for (int n = 0; n <= 50; n++) {
449      try {
450        BigIntegerMath.binomial(n, -1);
451        fail("Expected IllegalArgumentException");
452      } catch (IllegalArgumentException expected) {}
453      try {
454        BigIntegerMath.binomial(n, n + 1);
455        fail("Expected IllegalArgumentException");
456      } catch (IllegalArgumentException expected) {}
457    }
458  }
459
460  @GwtIncompatible("NullPointerTester")
461  public void testNullPointers() {
462    NullPointerTester tester = new NullPointerTester();
463    tester.setDefault(BigInteger.class, ONE);
464    tester.setDefault(int.class, 1);
465    tester.setDefault(long.class, 1L);
466    tester.testAllPublicStaticMethods(BigIntegerMath.class);
467  }
468}
469