Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * 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 java.util.List;

A class for arithmetic on values of type 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 int and for long can be found in IntMath and LongMath respectively.

Author(s):
Louis Wasserman
Since:
11.0
 
 @GwtCompatible(emulated = true)
 public final class BigIntegerMath {
  
Returns true if 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 x, rounded according to the specified rounding mode.

 
   @SuppressWarnings("fallthrough")
   // TODO(kevinb): remove after this warning is disabled globally
   public static int log2(BigInteger xRoundingMode mode) {
     checkPositive("x"checkNotNull(x));
     int logFloor = x.bitLength() - 1;
     switch (mode) {
       case :
         checkRoundingUnnecessary(isPowerOfTwo(x)); // fall through
       case :
       case :
         return logFloor;
 
       case :
       case :
         return isPowerOfTwo(x) ? logFloor : logFloor + 1;
 
       case :
       case :
       case :
         if (logFloor < ) {
           BigInteger halfPower = .shiftRight(
                - 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;
      new BigInteger("16a09e667f3bcc908b2fb1366ea957d3e3adec17512775099da2f590b0667322a", 16);
  private static final double LN_10 = Math.log(10);
  private static final double LN_2 = Math.log(2);

  
Returns n!, that is, the product of the first n positive integers, or 1 if n == 0.

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).

  public static BigInteger factorial(int n) {
    checkNonNegative("n"n);
    // If the factorial is small enough, just use LongMath to do it.
    if (n < ..) {
      return BigInteger.valueOf(.[n]);
    }
    // Pre-allocate space for our list of intermediate BigIntegers.
    int approxSize = IntMath.divide(n * IntMath.log2(n), .);
    ArrayList<BigIntegerbignums = new ArrayList<BigInteger>(approxSize);
    // Start from the pre-computed maximum long factorial.
    int startingNumber = ..;
    long product = .[startingNumber - 1];
    // Strip off 2s from this value.
    int shift = Long.numberOfTrailingZeros(product);
    product >>= shift;
    // Use floor(log2(num)) + 1 to prevent overflow of multiplication.
    int productBits = LongMath.log2(product) + 1;
    int bits = LongMath.log2(startingNumber) + 1;
    // Check for the next power of two boundary, to save us a CLZ operation.
    int nextPowerOfTwo = 1 << (bits - 1);
    // Iteratively multiply the longs as big as they can go.
    for (long num = startingNumbernum <= nnum++) {
      // Check to see if the floor(log2(num)) + 1 has changed.
      if ((num & nextPowerOfTwo) != 0) {
        nextPowerOfTwo <<= 1;
        bits++;
      }
      // Get rid of the 2s in num.
      int tz = Long.numberOfTrailingZeros(num);
      long normalizedNum = num >> tz;
      shift += tz;
      // Adjust floor(log2(num)) + 1.
      int normalizedBits = bits - tz;
      // If it won't fit in a long, then we store off the intermediate product.
      if (normalizedBits + productBits >= .) {
        bignums.add(BigInteger.valueOf(product));
        product = 1;
        productBits = 0;
      }
      product *= normalizedNum;
      productBits = LongMath.log2(product) + 1;
    }
    // Check for leftovers.
    if (product > 1) {
      bignums.add(BigInteger.valueOf(product));
    }
    // Efficiently multiply all the intermediate products together.
    return listProduct(bignums).shiftLeft(shift);
  }
  static BigInteger listProduct(List<BigIntegernums) {
    return listProduct(nums, 0, nums.size());
  }
  static BigInteger listProduct(List<BigIntegernumsint startint end) {
    switch (end - start) {
      case 0:
        return .;
      case 1:
        return nums.get(start);
      case 2:
        return nums.get(start).multiply(nums.get(start + 1));
      case 3:
        return nums.get(start).multiply(nums.get(start + 1)).multiply(nums.get(start + 2));
      default:
        // Otherwise, split the list in half and recursively do this.
        int m = (end + start) >>> 1;
        return listProduct(numsstartm).multiply(listProduct(numsmend));
    }
  }

 
Returns n choose k, also known as the binomial coefficient of n and k, that is, n! / (k! (n - k)!).

Warning: the result can take as much as O(k log n) space.

Throws:
java.lang.IllegalArgumentException if n < 0, k < 0, or k > n
  public static BigInteger binomial(int nint k) {
    checkNonNegative("n"n);
    checkNonNegative("k"k);
    checkArgument(k <= n"k (%s) > n (%s)"kn);
    if (k > (n >> 1)) {
      k = n - k;
    }
    if (k < .. && n <= .[k]) {
      return BigInteger.valueOf(LongMath.binomial(nk));
    }
    BigInteger accum = .;
    long numeratorAccum = n;
    long denominatorAccum = 1;
    int bits = LongMath.log2(n.);
    int numeratorBits = bits;
    for (int i = 1; i < ki++) {
      int p = n - i;
      int q = i + 1;
      // log2(p) >= bits - 1, because p >= n/2
      if (numeratorBits + bits >= . - 1) {
        // The numerator is as big as it can get without risking overflow.
        // Multiply numeratorAccum / denominatorAccum into accum.
        accum = accum
            .multiply(BigInteger.valueOf(numeratorAccum))
            .divide(BigInteger.valueOf(denominatorAccum));
        numeratorAccum = p;
        denominatorAccum = q;
        numeratorBits = bits;
      } else {
        // We can definitely multiply into the long accumulators without overflowing them.
        numeratorAccum *= p;
        denominatorAccum *= q;
        numeratorBits += bits;
      }
    }
    return accum
        .multiply(BigInteger.valueOf(numeratorAccum))
        .divide(BigInteger.valueOf(denominatorAccum));
  }
  // Returns true if BigInteger.valueOf(x.longValue()).equals(x).
  private BigIntegerMath() {}
New to GrepCode? Check out our FAQ X