11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.math; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.math.MathPreconditions.checkNoOverflow; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.math.MathPreconditions.checkNonNegative; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.math.MathPreconditions.checkPositive; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.math.MathPreconditions.checkRoundingUnnecessary; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static java.lang.Math.abs; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static java.math.RoundingMode.HALF_EVEN; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static java.math.RoundingMode.HALF_UP; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.VisibleForTesting; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.math.BigInteger; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.math.RoundingMode; 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A class for arithmetic on values of type {@code int}. Where possible, methods are defined and 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * named analogously to their {@code BigInteger} counterparts. 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The implementations of many methods in this class are based on material from Henry S. Warren, 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002). 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Similar functionality for {@code long} and for {@link BigInteger} can be found in 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link LongMath} and {@link BigIntegerMath} respectively. For other common operations on 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code int} values, see {@link com.google.common.primitives.Ints}. 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@Beta 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(emulated = true) 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic final class IntMath { 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, || 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code true} if {@code x} represents a power of two. 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This differs from {@code Integer.bitCount(x) == 1}, because 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Integer.bitCount(Integer.MIN_VALUE) == 1}, but {@link Integer#MIN_VALUE} is not a power 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of two. 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static boolean isPowerOfTwo(int x) { 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return x > 0 & (x & (x - 1)) == 0; 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode. 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code x <= 0} 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is not a power of two 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("need BigIntegerMath to adequately test") 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("fallthrough") 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int log2(int x, RoundingMode mode) { 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkPositive("x", x); 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (mode) { 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UNNECESSARY: 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkRoundingUnnecessary(isPowerOfTwo(x)); 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // fall through 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case DOWN: 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FLOOR: 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Integer.SIZE - 1) - Integer.numberOfLeadingZeros(x); 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UP: 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case CEILING: 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Integer.SIZE - Integer.numberOfLeadingZeros(x - 1); 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_DOWN: 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_UP: 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_EVEN: 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int leadingZeros = Integer.numberOfLeadingZeros(x); 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros; 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // floor(2^(logFloor + 0.5)) 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int logFloor = (Integer.SIZE - 1) - leadingZeros; 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (x <= cmp) ? logFloor : logFloor + 1; 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** The biggest half power of two that can fit in an unsigned int. */ 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting static final int MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333; 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode. 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code x <= 0} 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is not a power of ten 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("need BigIntegerMath to adequately test") 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("fallthrough") 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int log10(int x, RoundingMode mode) { 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkPositive("x", x); 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int logFloor = log10Floor(x); 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int floorPow = POWERS_OF_10[logFloor]; 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (mode) { 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UNNECESSARY: 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkRoundingUnnecessary(x == floorPow); 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // fall through 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FLOOR: 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case DOWN: 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return logFloor; 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case CEILING: 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UP: 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (x == floorPow) ? logFloor : logFloor + 1; 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_DOWN: 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_UP: 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_EVEN: 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // sqrt(10) is irrational, so log10(x) - logFloor is never exactly 0.5 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (x <= HALF_POWERS_OF_10[logFloor]) ? logFloor : logFloor + 1; 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static int log10Floor(int x) { 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 1; i < POWERS_OF_10.length; i++) { 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (x < POWERS_OF_10[i]) { 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return i - 1; 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return POWERS_OF_10.length - 1; 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting static final int[] POWERS_OF_10 = 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // HALF_POWERS_OF_10[i] = largest int less than 10^(i + 0.5) 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting static final int[] HALF_POWERS_OF_10 = 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert {3, 31, 316, 3162, 31622, 316227, 3162277, 31622776, 316227766, Integer.MAX_VALUE}; 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code BigInteger.valueOf(b).pow(k).intValue()}. This implementation runs in {@code O(log k)} 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * time. 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Compare {@link #checkedPow}, which throws an {@link ArithmeticException} upon overflow. 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code k < 0} 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("failing tests") 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int pow(int b, int k) { 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("exponent", k); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (b) { 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (k == 0) ? 1 : 0; 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1; 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case (-1): 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k & 1) == 0) ? 1 : -1; 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 2: 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (k < Integer.SIZE) ? (1 << k) : 0; 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case (-2): 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k < Integer.SIZE) { 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k & 1) == 0) ? (1 << k) : -(1 << k); 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int accum = 1;; k >>= 1) { 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (k) { 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return accum; 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return b * accum; 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert accum *= ((k & 1) == 0) ? 1 : b; 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert b *= b; 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the square root of {@code x}, rounded with the specified rounding mode. 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code x < 0} 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code sqrt(x)} is not an integer 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("need BigIntegerMath to adequately test") 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("fallthrough") 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int sqrt(int x, RoundingMode mode) { 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("x", x); 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int sqrtFloor = sqrtFloor(x); 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (mode) { 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UNNECESSARY: 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkRoundingUnnecessary(sqrtFloor * sqrtFloor == x); // fall through 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FLOOR: 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case DOWN: 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sqrtFloor; 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case CEILING: 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UP: 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (sqrtFloor * sqrtFloor == x) ? sqrtFloor : sqrtFloor + 1; 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_DOWN: 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_UP: 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_EVEN: 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int halfSquare = sqrtFloor * sqrtFloor + sqrtFloor; 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Since both x and halfSquare are integers, this is equivalent to testing whether or not 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * x <= halfSquare. (We have to deal with overflow, though.) 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (x <= halfSquare | halfSquare < 0) ? sqrtFloor : sqrtFloor + 1; 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static int sqrtFloor(int x) { 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // There is no loss of precision in converting an int to a double, according to 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // http://java.sun.com/docs/books/jls/third_edition/html/conversions.html#5.1.2 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (int) Math.sqrt(x); 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the result of dividing {@code p} by {@code q}, rounding using the specified 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code RoundingMode}. 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a} 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is not an integer multiple of {@code b} 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("failing tests") 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("fallthrough") 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int divide(int p, int q, RoundingMode mode) { 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(mode); 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (q == 0) { 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new ArithmeticException("/ by zero"); // for GWT 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int div = p / q; 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int rem = p - q * div; // equal to p % q 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (rem == 0) { 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return div; 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * p / q. 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise. 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int signum = 1 | ((p ^ q) >> (Integer.SIZE - 1)); 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert boolean increment; 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (mode) { 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UNNECESSARY: 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkRoundingUnnecessary(rem == 0); 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // fall through 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case DOWN: 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = false; 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UP: 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = true; 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case CEILING: 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = signum > 0; 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FLOOR: 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = signum < 0; 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_EVEN: 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_DOWN: 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_UP: 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int absRem = abs(rem); 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int cmpRemToHalfDivisor = absRem - (abs(q) - absRem); 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // subtracting two nonnegative ints can't overflow 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2). 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (cmpRemToHalfDivisor == 0) { // exactly on the half mark 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = (mode == HALF_UP || (mode == HALF_EVEN & (div & 1) != 0)); 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = cmpRemToHalfDivisor > 0; // closer to the UP value 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return increment ? div + signum : div; 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code x mod m}. This differs from {@code x % m} in that it always returns a 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * non-negative result. 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>For example:<pre> {@code 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(7, 4) == 3 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-7, 4) == 1 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-1, 4) == 3 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-8, 4) == 0 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(8, 4) == 0}</pre> 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code m <= 0} 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int mod(int x, int m) { 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (m <= 0) { 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new ArithmeticException("Modulus " + m + " must be > 0"); 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int result = x % m; 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (result >= 0) ? result : result + m; 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code a == 0 && b == 0}. 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0} 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int gcd(int a, int b) { 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The reason we require both arguments to be >= 0 is because otherwise, what do you return on 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * gcd(0, Integer.MIN_VALUE)? BigInteger.gcd would return positive 2^31, but positive 2^31 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * isn't an int. 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("a", a); 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("b", b); 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // The simple Euclidean algorithm is the fastest for ints, and is easily the most readable. 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (b != 0) { 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int t = b; 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert b = a % b; 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert a = t; 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return a; 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the sum of {@code a} and {@code b}, provided it does not overflow. 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code a + b} overflows in signed {@code int} arithmetic 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int checkedAdd(int a, int b) { 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = (long) a + b; 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(result == (int) result); 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (int) result; 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the difference of {@code a} and {@code b}, provided it does not overflow. 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code a - b} overflows in signed {@code int} arithmetic 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int checkedSubtract(int a, int b) { 3671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = (long) a - b; 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(result == (int) result); 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (int) result; 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the product of {@code a} and {@code b}, provided it does not overflow. 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code a * b} overflows in signed {@code int} arithmetic 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int checkedMultiply(int a, int b) { 3781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = (long) a * b; 3791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(result == (int) result); 3801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (int) result; 3811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the {@code b} to the {@code k}th power, provided it does not overflow. 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>{@link #pow} may be faster, but does not check for overflow. 3871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code int} arithmetic 3901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("failing tests") 3921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int checkedPow(int b, int k) { 3931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("exponent", k); 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (b) { 3951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 3961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (k == 0) ? 1 : 0; 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1; 3991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case (-1): 4001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k & 1) == 0) ? 1 : -1; 4011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 2: 4021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(k < Integer.SIZE - 1); 4031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1 << k; 4041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case (-2): 4051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(k < Integer.SIZE); 4061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k & 1) == 0) ? 1 << k : -1 << k; 4071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int accum = 1; 4091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 4101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (k) { 4111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 4121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return accum; 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return checkedMultiply(accum, b); 4151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if ((k & 1) != 0) { 4171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert accum = checkedMultiply(accum, b); 4181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k >>= 1; 4201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k > 0) { 4211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(-FLOOR_SQRT_MAX_INT <= b & b <= FLOOR_SQRT_MAX_INT); 4221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert b *= b; 4231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting static final int FLOOR_SQRT_MAX_INT = 46340; 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code n!}, that is, the product of the first {@code n} positive 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * integers, {@code 1} if {@code n == 0}, or {@link Integer#MAX_VALUE} if the 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * result does not fit in a {@code int}. 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code n < 0} 4361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("need BigIntegerMath to adequately test") 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int factorial(int n) { 4391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("n", n); 4401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (n < FACTORIALS.length) ? FACTORIALS[n] : Integer.MAX_VALUE; 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final int[] FACTORIALS = { 4441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1, 4451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1, 4461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2, 4471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3, 4481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4, 4491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4 * 5, 4501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4 * 5 * 6, 4511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4 * 5 * 6 * 7, 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8, 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9, 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10, 4551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11, 4561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12}; 4571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and 4601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code k}, or {@link Integer#MAX_VALUE} if the result does not fit in an {@code int}. 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0} or {@code k > n} 4631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("need BigIntegerMath to adequately test") 4651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int binomial(int n, int k) { 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("n", n); 4671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("k", k); 4681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(k <= n, "k (%s) > n (%s)", k, n); 4691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k > (n >> 1)) { 4701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k = n - k; 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k >= BIGGEST_BINOMIALS.length || n > BIGGEST_BINOMIALS[k]) { 4731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Integer.MAX_VALUE; 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (k) { 4761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1; 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return n; 4801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 4811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = 1; 4821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < k; i++) { 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert result *= n - i; 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert result /= i + 1; 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (int) result; 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // binomial(BIGGEST_BINOMIALS[k], k) fits in an int, but not binomial(BIGGEST_BINOMIALS[k]+1,k). 4911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting static int[] BIGGEST_BINOMIALS = { 4921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer.MAX_VALUE, 4931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer.MAX_VALUE, 4941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 65536, 4951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2345, 4961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 477, 4971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 193, 4981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 110, 4991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 75, 5001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 58, 5011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 49, 5021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 43, 5031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 39, 5041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 37, 5051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 35, 5061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 34, 5071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 34, 5081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 33 5091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 5101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private IntMath() {} 5121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 513