12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/* 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Copyright (C) 2011 The Guava Authors 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Licensed under the Apache License, Version 2.0 (the "License"); 52a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * you may not use this file except in compliance with the License. 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * You may obtain a copy of the License at 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * http://www.apache.org/licenses/LICENSE-2.0 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * 101320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci * Unless required by applicable law or agreed to in writing, software 112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * distributed under the License is distributed on an "AS IS" BASIS, 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * See the License for the specific language governing permissions and 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * limitations under the License. 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) */ 165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)package com.google.common.math; 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static com.google.common.math.MathTesting.ALL_BIGINTEGER_CANDIDATES; 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static com.google.common.math.MathTesting.ALL_ROUNDING_MODES; 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static com.google.common.math.MathTesting.ALL_SAFE_ROUNDING_MODES; 22f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)import static com.google.common.math.MathTesting.NEGATIVE_BIGINTEGER_CANDIDATES; 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static com.google.common.math.MathTesting.NEGATIVE_INTEGER_CANDIDATES; 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static com.google.common.math.MathTesting.NONZERO_BIGINTEGER_CANDIDATES; 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static com.google.common.math.MathTesting.POSITIVE_BIGINTEGER_CANDIDATES; 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.BigInteger.ONE; 27f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)import static java.math.BigInteger.TEN; 28a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)import static java.math.BigInteger.ZERO; 292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.RoundingMode.CEILING; 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.RoundingMode.DOWN; 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.RoundingMode.FLOOR; 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.RoundingMode.HALF_DOWN; 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.RoundingMode.HALF_EVEN; 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.RoundingMode.HALF_UP; 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.RoundingMode.UNNECESSARY; 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.math.RoundingMode.UP; 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import static java.util.Arrays.asList; 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import com.google.common.testing.NullPointerTester; 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import junit.framework.TestCase; 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import java.math.BigDecimal; 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import java.math.BigInteger; 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)import java.math.RoundingMode; 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)/** 482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * Tests for BigIntegerMath. 492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * 502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) * @author Louis Wasserman 512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) */ 522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)public class BigIntegerMathTest extends TestCase { 532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public void testConstantSqrt2PrecomputedBits() { 542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertEquals(BigIntegerMath.sqrt( 552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BigInteger.ZERO.setBit(2 * BigIntegerMath.SQRT2_PRECOMPUTE_THRESHOLD + 1), FLOOR), 562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BigIntegerMath.SQRT2_PRECOMPUTED_BITS); 572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public void testIsPowerOfTwo() { 602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (BigInteger x : ALL_BIGINTEGER_CANDIDATES) { 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Checks for a single bit set. 622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) boolean expected = x.signum() > 0 & x.and(x.subtract(ONE)).equals(ZERO); 632a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertEquals(expected, BigIntegerMath.isPowerOfTwo(x)); 642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public void testLog2ZeroAlwaysThrows() { 682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (RoundingMode mode : ALL_ROUNDING_MODES) { 692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) try { 702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BigIntegerMath.log2(ZERO, mode); 712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) fail("Expected IllegalArgumentException"); 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } catch (IllegalArgumentException expected) {} 73f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 74f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 76f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) public void testLog2NegativeAlwaysThrows() { 77f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 782a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (RoundingMode mode : ALL_ROUNDING_MODES) { 792a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) try { 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BigIntegerMath.log2(x.negate(), mode); 812a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) fail("Expected IllegalArgumentException"); 822a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } catch (IllegalArgumentException expected) {} 83f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) } 842a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 86f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 872a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public void testLog2Floor() { 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (RoundingMode mode : asList(FLOOR, DOWN)) { 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int result = BigIntegerMath.log2(x, mode); 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(ZERO.setBit(result).compareTo(x) <= 0); 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(ZERO.setBit(result + 1).compareTo(x) > 0); 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public void testLog2Ceiling() { 982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (RoundingMode mode : asList(CEILING, UP)) { 1002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int result = BigIntegerMath.log2(x, mode); 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(ZERO.setBit(result).compareTo(x) >= 0); 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(result == 0 || ZERO.setBit(result - 1).compareTo(x) < 0); 1032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Relies on the correctness of isPowerOfTwo(BigInteger). 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public void testLog2Exact() { 1092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 1102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // We only expect an exception if x was not a power of 2. 1112a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) boolean isPowerOf2 = BigIntegerMath.isPowerOfTwo(x); 1122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) try { 1132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertEquals(x, ZERO.setBit(BigIntegerMath.log2(x, UNNECESSARY))); 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(isPowerOf2); 1152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } catch (ArithmeticException e) { 1162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertFalse(isPowerOf2); 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) public void testLog2HalfUp() { 1222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 1232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int result = BigIntegerMath.log2(x, HALF_UP); 1242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BigInteger x2 = x.pow(2); 1252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // x^2 < 2^(2 * result + 1), or else we would have rounded up 1262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) > 0); 1272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // x^2 >= 2^(2 * result - 1), or else we would have rounded down 1282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) <= 0); 1292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 1312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) public void testLog2HalfDown() { 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (BigInteger x : POSITIVE_BIGINTEGER_CANDIDATES) { 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int result = BigIntegerMath.log2(x, HALF_DOWN); 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) BigInteger x2 = x.pow(2); 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // x^2 <= 2^(2 * result + 1), or else we would have rounded up 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(ZERO.setBit(2 * result + 1).compareTo(x2) >= 0); 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // x^2 > 2^(2 * result - 1), or else we would have rounded down 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assertTrue(result == 0 || ZERO.setBit(2 * result - 1).compareTo(x2) < 0); 1402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 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