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.POSITIVE_BIGINTEGER_CANDIDATES;
22 import static java.math.BigInteger.ONE;
23 import static java.math.BigInteger.ZERO;
24 import static java.math.RoundingMode.CEILING;
25 import static java.math.RoundingMode.DOWN;
26 import static java.math.RoundingMode.FLOOR;
27 import static java.math.RoundingMode.HALF_DOWN;
28 import static java.math.RoundingMode.HALF_EVEN;
29 import static java.math.RoundingMode.HALF_UP;
30 import static java.math.RoundingMode.UNNECESSARY;
31 import static java.math.RoundingMode.UP;
32 import static java.util.Arrays.asList;
33 
34 import com.google.common.annotations.GwtCompatible;
35 
36 import junit.framework.TestCase;
37 
38 import java.math.BigInteger;
39 import java.math.RoundingMode;
40 
41 /**
42  * Tests for BigIntegerMath.
43  *
44  * @author Louis Wasserman
45  */
46 @GwtCompatible(emulated = true)
47 public class BigIntegerMathTest extends TestCase {
48 
testIsPowerOfTwo()49   public void testIsPowerOfTwo() {
50     for (BigInteger x : ALL_BIGINTEGER_CANDIDATES) {
51       // Checks for a single bit set.
52       boolean expected = x.signum() > 0 & x.and(x.subtract(ONE)).equals(ZERO);
53       assertEquals(expected, BigIntegerMath.isPowerOfTwo(x));
54     }
55   }
56 
testLog2ZeroAlwaysThrows()57   public void testLog2ZeroAlwaysThrows() {
58     for (RoundingMode mode : ALL_ROUNDING_MODES) {
59       try {
60         BigIntegerMath.log2(ZERO, mode);
61         fail("Expected IllegalArgumentException");
62       } catch (IllegalArgumentException expected) {}
63     }
64   }
65 
testLog2NegativeAlwaysThrows()66   public void testLog2NegativeAlwaysThrows() {
67     for (RoundingMode mode : ALL_ROUNDING_MODES) {
68       try {
69         BigIntegerMath.log2(BigInteger.valueOf(-1), mode);
70         fail("Expected IllegalArgumentException");
71       } catch (IllegalArgumentException expected) {}
72     }
73   }
74 
testLog2Floor()75   public void testLog2Floor() {
76     for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
77       for (RoundingMode mode : asList(FLOOR, DOWN)) {
78         int result = BigIntegerMath.log2(x, mode);
79         assertTrue(ZERO.setBit(result).compareTo(x) <= 0);
80         assertTrue(ZERO.setBit(result + 1).compareTo(x) > 0);
81       }
82     }
83   }
84 
testLog2Ceiling()85   public void testLog2Ceiling() {
86     for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
87       for (RoundingMode mode : asList(CEILING, UP)) {
88         int result = BigIntegerMath.log2(x, mode);
89         assertTrue(ZERO.setBit(result).compareTo(x) >= 0);
90         assertTrue(result == 0 || ZERO.setBit(result - 1).compareTo(x) < 0);
91       }
92     }
93   }
94 
95   // Relies on the correctness of isPowerOfTwo(BigInteger).
testLog2Exact()96   public void testLog2Exact() {
97     for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
98       // We only expect an exception if x was not a power of 2.
99       boolean isPowerOf2 = BigIntegerMath.isPowerOfTwo(x);
100       try {
101         assertEquals(x, ZERO.setBit(BigIntegerMath.log2(x, UNNECESSARY)));
102         assertTrue(isPowerOf2);
103       } catch (ArithmeticException e) {
104         assertFalse(isPowerOf2);
105       }
106     }
107   }
108 
testLog2HalfUp()109   public void testLog2HalfUp() {
110     for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
111       int result = BigIntegerMath.log2(x, HALF_UP);
112       BigInteger x2 = x.pow(2);
113       // x^2 < 2^(2 * result + 1), or else we would have rounded up
114       assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) > 0);
115       // x^2 >= 2^(2 * result - 1), or else we would have rounded down
116       assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) <= 0);
117     }
118   }
119 
testLog2HalfDown()120   public void testLog2HalfDown() {
121     for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
122       int result = BigIntegerMath.log2(x, HALF_DOWN);
123       BigInteger x2 = x.pow(2);
124       // x^2 <= 2^(2 * result + 1), or else we would have rounded up
125       assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) >= 0);
126       // x^2 > 2^(2 * result - 1), or else we would have rounded down
127       assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) < 0);
128     }
129   }
130 
131   // Relies on the correctness of log2(BigInteger, {HALF_UP,HALF_DOWN}).
testLog2HalfEven()132   public void testLog2HalfEven() {
133     for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
134       int halfEven = BigIntegerMath.log2(x, HALF_EVEN);
135       // Now figure out what rounding mode we should behave like (it depends if FLOOR was
136       // odd/even).
137       boolean floorWasEven = (BigIntegerMath.log2(x, FLOOR) & 1) == 0;
138       assertEquals(BigIntegerMath.log2(x, floorWasEven ? HALF_DOWN : HALF_UP), halfEven);
139     }
140   }
141 
142   // Relies on the correctness of log10(BigInteger, FLOOR).
143 
144   // Relies on the correctness of log10(BigInteger, {HALF_UP,HALF_DOWN}).
145 
146   // Relies on the correctness of sqrt(BigInteger, FLOOR).
147 
148   // Relies on the correctness of sqrt(BigInteger, {HALF_UP,HALF_DOWN}).
149 
testFactorial()150   public void testFactorial() {
151     BigInteger expected = BigInteger.ONE;
152     for (int i = 1; i <= 200; i++) {
153       expected = expected.multiply(BigInteger.valueOf(i));
154       assertEquals(expected, BigIntegerMath.factorial(i));
155     }
156   }
157 
testFactorial0()158   public void testFactorial0() {
159     assertEquals(BigInteger.ONE, BigIntegerMath.factorial(0));
160   }
161 
testFactorialNegative()162   public void testFactorialNegative() {
163     try {
164       BigIntegerMath.factorial(-1);
165       fail("Expected IllegalArgumentException");
166     } catch (IllegalArgumentException expected) {}
167   }
168 
testBinomialSmall()169   public void testBinomialSmall() {
170     runBinomialTest(0, 30);
171   }
172 
173   // Depends on the correctness of BigIntegerMath.factorial
runBinomialTest(int firstN, int lastN)174   private static void runBinomialTest(int firstN, int lastN) {
175     for (int n = firstN; n <= lastN; n++) {
176       for (int k = 0; k <= n; k++) {
177         BigInteger expected = BigIntegerMath
178             .factorial(n)
179             .divide(BigIntegerMath.factorial(k))
180             .divide(BigIntegerMath.factorial(n - k));
181         assertEquals(expected, BigIntegerMath.binomial(n, k));
182       }
183     }
184   }
185 
testBinomialOutside()186   public void testBinomialOutside() {
187     for (int n = 0; n <= 50; n++) {
188       try {
189         BigIntegerMath.binomial(n, -1);
190         fail("Expected IllegalArgumentException");
191       } catch (IllegalArgumentException expected) {}
192       try {
193         BigIntegerMath.binomial(n, n + 1);
194         fail("Expected IllegalArgumentException");
195       } catch (IllegalArgumentException expected) {}
196     }
197   }
198 }
199 
200