/* * Copyright (C) 2011 The Guava Authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package com.google.common.math; import static com.google.common.base.Preconditions.checkArgument; import static com.google.common.base.Preconditions.checkNotNull; import static com.google.common.math.MathPreconditions.checkNonNegative; import static com.google.common.math.MathPreconditions.checkPositive; import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary; import static java.math.RoundingMode.CEILING; import static java.math.RoundingMode.FLOOR; import static java.math.RoundingMode.HALF_EVEN; import com.google.common.annotations.Beta; import com.google.common.annotations.VisibleForTesting; import java.math.BigDecimal; import java.math.BigInteger; import java.math.RoundingMode; import java.util.ArrayList; import java.util.List; /** * A class for arithmetic on values of type {@code BigInteger}. * *
The implementations of many methods in this class are based on material from Henry S. Warren, * Jr.'s Hacker's Delight, (Addison Wesley, 2002). * *
Similar functionality for {@code int} and for {@code long} can be found in
* {@link IntMath} and {@link LongMath} respectively.
*
* @author Louis Wasserman
* @since 11.0
*/
@Beta
public final class BigIntegerMath {
/**
* Returns {@code true} if {@code x} represents a power of two.
*/
public static boolean isPowerOfTwo(BigInteger x) {
checkNotNull(x);
return x.signum() > 0 && x.getLowestSetBit() == x.bitLength() - 1;
}
/**
* Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode.
*
* @throws IllegalArgumentException if {@code x <= 0}
* @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
* is not a power of two
*/
@SuppressWarnings("fallthrough")
public static int log2(BigInteger x, RoundingMode mode) {
checkPositive("x", checkNotNull(x));
int logFloor = x.bitLength() - 1;
switch (mode) {
case UNNECESSARY:
checkRoundingUnnecessary(isPowerOfTwo(x)); // fall through
case DOWN:
case FLOOR:
return logFloor;
case UP:
case CEILING:
return isPowerOfTwo(x) ? logFloor : logFloor + 1;
case HALF_DOWN:
case HALF_UP:
case HALF_EVEN:
if (logFloor < SQRT2_PRECOMPUTE_THRESHOLD) {
BigInteger halfPower = SQRT2_PRECOMPUTED_BITS.shiftRight(
SQRT2_PRECOMPUTE_THRESHOLD - logFloor);
if (x.compareTo(halfPower) <= 0) {
return logFloor;
} else {
return logFloor + 1;
}
}
/*
* Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5
*
* To determine which side of logFloor.5 the logarithm is, we compare x^2 to 2^(2 *
* logFloor + 1).
*/
BigInteger x2 = x.pow(2);
int logX2Floor = x2.bitLength() - 1;
return (logX2Floor < 2 * logFloor + 1) ? logFloor : logFloor + 1;
default:
throw new AssertionError();
}
}
/*
* The maximum number of bits in a square root for which we'll precompute an explicit half power
* of two. This can be any value, but higher values incur more class load time and linearly
* increasing memory consumption.
*/
@VisibleForTesting static final int SQRT2_PRECOMPUTE_THRESHOLD = 256;
@VisibleForTesting static final BigInteger SQRT2_PRECOMPUTED_BITS =
new BigInteger("16a09e667f3bcc908b2fb1366ea957d3e3adec17512775099da2f590b0667322a", 16);
/**
* Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode.
*
* @throws IllegalArgumentException if {@code x <= 0}
* @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x}
* is not a power of ten
*/
@SuppressWarnings("fallthrough")
public static int log10(BigInteger x, RoundingMode mode) {
checkPositive("x", x);
if (fitsInLong(x)) {
return LongMath.log10(x.longValue(), mode);
}
// capacity of 10 suffices for all x <= 10^(2^10).
List Warning: the result takes O(n log n) space, so use cautiously.
*
* This uses an efficient binary recursive algorithm to compute the factorial
* with balanced multiplies. It also removes all the 2s from the intermediate
* products (shifting them back in at the end).
*
* @throws IllegalArgumentException if {@code n < 0}
*/
public static BigInteger factorial(int n) {
checkNonNegative("n", n);
// If the factorial is small enough, just use LongMath to do it.
if (n < LongMath.FACTORIALS.length) {
return BigInteger.valueOf(LongMath.FACTORIALS[n]);
}
// Pre-allocate space for our list of intermediate BigIntegers.
int approxSize = IntMath.divide(n * IntMath.log2(n, CEILING), Long.SIZE, CEILING);
ArrayList Warning: the result can take as much as O(k log n) space.
*
* @throws IllegalArgumentException if {@code n < 0}, {@code k < 0}, or {@code k > n}
*/
public static BigInteger binomial(int n, int k) {
checkNonNegative("n", n);
checkNonNegative("k", k);
checkArgument(k <= n, "k (%s) > n (%s)", k, n);
if (k > (n >> 1)) {
k = n - k;
}
if (k < LongMath.BIGGEST_BINOMIALS.length && n <= LongMath.BIGGEST_BINOMIALS[k]) {
return BigInteger.valueOf(LongMath.binomial(n, k));
}
BigInteger result = BigInteger.ONE;
for (int i = 0; i < k; i++) {
result = result.multiply(BigInteger.valueOf(n - i));
result = result.divide(BigInteger.valueOf(i + 1));
}
return result;
}
// Returns true if BigInteger.valueOf(x.longValue()).equals(x).
static boolean fitsInLong(BigInteger x) {
return x.bitLength() <= Long.SIZE - 1;
}
private BigIntegerMath() {}
}