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_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
43
44
45
46 @GwtCompatible(emulated = true)
47 public class BigIntegerMathTest extends TestCase {
48
49 public void testIsPowerOfTwo() {
50 for (BigInteger x : ALL_BIGINTEGER_CANDIDATES) {
51
52 boolean expected = x.signum() > 0 & x.and(x.subtract(ONE)).equals(ZERO);
53 assertEquals(expected, BigIntegerMath.isPowerOfTwo(x));
54 }
55 }
56
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
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
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
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
96 public void testLog2Exact() {
97 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
98
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
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
114 assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) > 0);
115
116 assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) <= 0);
117 }
118 }
119
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
125 assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) >= 0);
126
127 assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) < 0);
128 }
129 }
130
131
132 public void testLog2HalfEven() {
133 for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) {
134 int halfEven = BigIntegerMath.log2(x, HALF_EVEN);
135
136
137 boolean floorWasEven = (BigIntegerMath.log2(x, FLOOR) & 1) == 0;
138 assertEquals(BigIntegerMath.log2(x, floorWasEven ? HALF_DOWN : HALF_UP), halfEven);
139 }
140 }
141
142
143
144
145
146
147
148
149
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
158 public void testFactorial0() {
159 assertEquals(BigInteger.ONE, BigIntegerMath.factorial(0));
160 }
161
162 public void testFactorialNegative() {
163 try {
164 BigIntegerMath.factorial(-1);
165 fail("Expected IllegalArgumentException");
166 } catch (IllegalArgumentException expected) {}
167 }
168
169 public void testBinomialSmall() {
170 runBinomialTest(0, 30);
171 }
172
173
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
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