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.lang.Math.min; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static java.math.RoundingMode.HALF_EVEN; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static java.math.RoundingMode.HALF_UP; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.VisibleForTesting; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.math.BigInteger; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.math.RoundingMode; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A class for arithmetic on values of type {@code long}. Where possible, methods are defined and 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * named analogously to their {@code BigInteger} counterparts. 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The implementations of many methods in this class are based on material from Henry S. Warren, 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Jr.'s <i>Hacker's Delight</i>, (Addison Wesley, 2002). 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Similar functionality for {@code int} and for {@link BigInteger} can be found in 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link IntMath} and {@link BigIntegerMath} respectively. For other common operations on 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code long} values, see {@link com.google.common.primitives.Longs}. 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@Beta 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic final class LongMath { 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, || 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code true} if {@code x} represents a power of two. 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This differs from {@code Long.bitCount(x) == 1}, because 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Long.bitCount(Long.MIN_VALUE) == 1}, but {@link Long#MIN_VALUE} is not a power of two. 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static boolean isPowerOfTwo(long x) { 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return x > 0 & (x & (x - 1)) == 0; 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the base-2 logarithm of {@code x}, rounded according to the specified rounding mode. 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code x <= 0} 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is not a power of two 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("fallthrough") 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int log2(long x, RoundingMode mode) { 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkPositive("x", x); 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (mode) { 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UNNECESSARY: 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkRoundingUnnecessary(isPowerOfTwo(x)); 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // fall through 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case DOWN: 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FLOOR: 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Long.SIZE - 1) - Long.numberOfLeadingZeros(x); 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UP: 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case CEILING: 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Long.SIZE - Long.numberOfLeadingZeros(x - 1); 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_DOWN: 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_UP: 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_EVEN: 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Since sqrt(2) is irrational, log2(x) - logFloor cannot be exactly 0.5 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int leadingZeros = Long.numberOfLeadingZeros(x); 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long cmp = MAX_POWER_OF_SQRT2_UNSIGNED >>> leadingZeros; 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // floor(2^(logFloor + 0.5)) 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int logFloor = (Long.SIZE - 1) - leadingZeros; 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (x <= cmp) ? logFloor : logFloor + 1; 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError("impossible"); 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** The biggest half power of two that fits into an unsigned long */ 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting static final long MAX_POWER_OF_SQRT2_UNSIGNED = 0xB504F333F9DE6484L; 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the base-10 logarithm of {@code x}, rounded according to the specified rounding mode. 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code x <= 0} 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and {@code x} 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is not a power of ten 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("fallthrough") 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int log10(long x, RoundingMode mode) { 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkPositive("x", x); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (fitsInInt(x)) { 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return IntMath.log10((int) x, mode); 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int logFloor = log10Floor(x); 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long floorPow = POWERS_OF_10[logFloor]; 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (mode) { 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UNNECESSARY: 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkRoundingUnnecessary(x == floorPow); 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // fall through 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FLOOR: 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case DOWN: 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return logFloor; 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case CEILING: 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UP: 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (x == floorPow) ? logFloor : logFloor + 1; 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_DOWN: 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_UP: 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_EVEN: 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // sqrt(10) is irrational, so log10(x)-logFloor is never exactly 0.5 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (x <= HALF_POWERS_OF_10[logFloor]) ? logFloor : logFloor + 1; 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static int log10Floor(long x) { 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 1; i < POWERS_OF_10.length; i++) { 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (x < POWERS_OF_10[i]) { 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return i - 1; 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return POWERS_OF_10.length - 1; 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final long[] POWERS_OF_10 = { 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L, 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10L, 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 100L, 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1000L, 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10000L, 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 100000L, 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1000000L, 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10000000L, 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 100000000L, 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1000000000L, 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10000000000L, 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 100000000000L, 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1000000000000L, 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10000000000000L, 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 100000000000000L, 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1000000000000000L, 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10000000000000000L, 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 100000000000000000L, 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1000000000000000000L 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // HALF_POWERS_OF_10[i] = largest long less than 10^(i + 0.5) 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final long[] HALF_POWERS_OF_10 = { 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3L, 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 31L, 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 316L, 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3162L, 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 31622L, 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 316227L, 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3162277L, 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 31622776L, 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 316227766L, 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3162277660L, 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 31622776601L, 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 316227766016L, 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3162277660168L, 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 31622776601683L, 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 316227766016837L, 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3162277660168379L, 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 31622776601683793L, 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 316227766016837933L, 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3162277660168379331L 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code b} to the {@code k}th power. Even if the result overflows, it will be equal to 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code BigInteger.valueOf(b).pow(k).longValue()}. This implementation runs in {@code O(log k)} 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * time. 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code k < 0} 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long pow(long b, int k) { 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("exponent", k); 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (-2 <= b && b <= 2) { 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch ((int) b) { 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (k == 0) ? 1 : 0; 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1; 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case (-1): 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k & 1) == 0) ? 1 : -1; 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 2: 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (k < Long.SIZE) ? 1L << k : 0; 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case (-2): 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k < Long.SIZE) { 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k & 1) == 0) ? 1L << k : -(1L << k); 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (long accum = 1;; k >>= 1) { 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (k) { 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return accum; 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return accum * b; 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert accum *= ((k & 1) == 0) ? 1 : b; 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert b *= b; 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the square root of {@code x}, rounded with the specified rounding mode. 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code x < 0} 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code mode} is {@link RoundingMode#UNNECESSARY} and 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code sqrt(x)} is not an integer 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("fallthrough") 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long sqrt(long x, RoundingMode mode) { 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("x", x); 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (fitsInInt(x)) { 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return IntMath.sqrt((int) x, mode); 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long sqrtFloor = sqrtFloor(x); 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (mode) { 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UNNECESSARY: 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkRoundingUnnecessary(sqrtFloor * sqrtFloor == x); // fall through 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FLOOR: 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case DOWN: 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sqrtFloor; 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case CEILING: 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UP: 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (sqrtFloor * sqrtFloor == x) ? sqrtFloor : sqrtFloor + 1; 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_DOWN: 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_UP: 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_EVEN: 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long halfSquare = sqrtFloor * sqrtFloor + sqrtFloor; 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * We wish to test whether or not x <= (sqrtFloor + 0.5)^2 = halfSquare + 0.25. Since both 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * x and halfSquare are integers, this is equivalent to testing whether or not x <= 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * halfSquare. (We have to deal with overflow, though.) 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (halfSquare >= x | halfSquare < 0) ? sqrtFloor : sqrtFloor + 1; 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static long sqrtFloor(long x) { 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Hackers's Delight, Figure 11-1 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long sqrt0 = (long) Math.sqrt(x); 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Precision can be lost in the cast to double, so we use this as a starting estimate. 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long sqrt1 = (sqrt0 + (x / sqrt0)) >> 1; 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (sqrt1 == sqrt0) { 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sqrt0; 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert do { 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sqrt0 = sqrt1; 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sqrt1 = (sqrt0 + (x / sqrt0)) >> 1; 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } while (sqrt1 < sqrt0); 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sqrt0; 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the result of dividing {@code p} by {@code q}, rounding using the specified 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code RoundingMode}. 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code q == 0}, or if {@code mode == UNNECESSARY} and {@code a} 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is not an integer multiple of {@code b} 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("fallthrough") 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long divide(long p, long q, RoundingMode mode) { 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(mode); 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long div = p / q; // throws if q == 0 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long rem = p - q * div; // equals p % q 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (rem == 0) { 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return div; 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Normal Java division rounds towards 0, consistently with RoundingMode.DOWN. We just have to 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * deal with the cases where rounding towards 0 is wrong, which typically depends on the sign of 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * p / q. 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * signum is 1 if p and q are both nonnegative or both negative, and -1 otherwise. 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int signum = 1 | (int) ((p ^ q) >> (Long.SIZE - 1)); 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert boolean increment; 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (mode) { 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UNNECESSARY: 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkRoundingUnnecessary(rem == 0); 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // fall through 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case DOWN: 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = false; 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case UP: 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = true; 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case CEILING: 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = signum > 0; 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case FLOOR: 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = signum < 0; 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_EVEN: 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_DOWN: 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case HALF_UP: 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long absRem = abs(rem); 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long cmpRemToHalfDivisor = absRem - (abs(q) - absRem); 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // subtracting two nonnegative longs can't overflow 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // cmpRemToHalfDivisor has the same sign as compare(abs(rem), abs(q) / 2). 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (cmpRemToHalfDivisor == 0) { // exactly on the half mark 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = (mode == HALF_UP | (mode == HALF_EVEN & (div & 1) != 0)); 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert increment = cmpRemToHalfDivisor > 0; // closer to the UP value 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new AssertionError(); 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return increment ? div + signum : div; 3471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code x mod m}. This differs from {@code x % m} in that it always returns a 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * non-negative result. 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>For example: 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <pre> {@code 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(7, 4) == 3 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-7, 4) == 1 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-1, 4) == 3 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-8, 4) == 0 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(8, 4) == 0}</pre> 3621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code m <= 0} 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int mod(long x, int m) { 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Cast is safe because the result is guaranteed in the range [0, m) 3671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (int) mod(x, (long) m); 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code x mod m}. This differs from {@code x % m} in that it always returns a 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * non-negative result. 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>For example: 3751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <pre> {@code 3771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(7, 4) == 3 3791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-7, 4) == 1 3801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-1, 4) == 3 3811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(-8, 4) == 0 3821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * mod(8, 4) == 0}</pre> 3831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code m <= 0} 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long mod(long x, long m) { 3871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (m <= 0) { 3881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new ArithmeticException("Modulus " + m + " must be > 0"); 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = x % m; 3911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (result >= 0) ? result : result + m; 3921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the greatest common divisor of {@code a, b}. Returns {@code 0} if 3961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code a == 0 && b == 0}. 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code a < 0} or {@code b < 0} 3991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long gcd(long a, long b) { 4011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 4021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The reason we require both arguments to be >= 0 is because otherwise, what do you return on 4031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * gcd(0, Long.MIN_VALUE)? BigInteger.gcd would return positive 2^63, but positive 2^63 isn't 4041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * an int. 4051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("a", a); 4071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("b", b); 4081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (a == 0 | b == 0) { 4091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return a | b; 4101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 4121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * This is over 40% faster than the Euclidean algorithm in benchmarks. 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int aTwos = Long.numberOfTrailingZeros(a); 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert a >>= aTwos; // divide out all 2s 4171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int bTwos = Long.numberOfTrailingZeros(b); 4181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert b >>= bTwos; // divide out all 2s 4191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (a != b) { // both a, b are odd 4201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (a < b) { // swap a, b 4211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long t = b; 4221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert b = a; 4231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert a = t; 4241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert a -= b; // a is now positive and even 4261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert a >>= Long.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return a << min(aTwos, bTwos); 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the sum of {@code a} and {@code b}, provided it does not overflow. 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code a + b} overflows in signed {@code long} arithmetic 4351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long checkedAdd(long a, long b) { 4371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = a + b; 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow((a ^ b) < 0 | (a ^ result) >= 0); 4391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 4401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the difference of {@code a} and {@code b}, provided it does not overflow. 4441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code a - b} overflows in signed {@code long} arithmetic 4461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long checkedSubtract(long a, long b) { 4481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = a - b; 4491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow((a ^ b) >= 0 | (a ^ result) >= 0); 4501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 4511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the product of {@code a} and {@code b}, provided it does not overflow. 4551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code a * b} overflows in signed {@code long} arithmetic 4571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long checkedMultiply(long a, long b) { 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Hacker's Delight, Section 2-12 4601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int leadingZeros = Long.numberOfLeadingZeros(a) + Long.numberOfLeadingZeros(~a) 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert + Long.numberOfLeadingZeros(b) + Long.numberOfLeadingZeros(~b); 4621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 4631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * If leadingZeros > Long.SIZE + 1 it's definitely fine, if it's < Long.SIZE it's definitely 4641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * bad. We do the leadingZeros check to avoid the division below if at all possible. 4651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Otherwise, if b == Long.MIN_VALUE, then the only allowed values of a are 0 and 1. We take 4671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * care of all a < 0 with their own check, because in particular, the case a == -1 will 4681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * incorrectly pass the division check below. 4691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * In all other cases, we check that either a is 0 or the result is consistent with division. 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (leadingZeros > Long.SIZE + 1) { 4731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return a * b; 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(leadingZeros >= Long.SIZE); 4761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(a >= 0 | b != Long.MIN_VALUE); 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = a * b; 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(a == 0 || result / a == b); 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 4801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the {@code b} to the {@code k}th power, provided it does not overflow. 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws ArithmeticException if {@code b} to the {@code k}th power overflows in signed 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code long} arithmetic 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long checkedPow(long b, int k) { 4891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("exponent", k); 4901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (b >= -2 & b <= 2) { 4911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch ((int) b) { 4921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 4931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (k == 0) ? 1 : 0; 4941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 4951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1; 4961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case (-1): 4971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k & 1) == 0) ? 1 : -1; 4981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 2: 4991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(k < Long.SIZE - 1); 5001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 1L << k; 5011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case (-2): 5021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(k < Long.SIZE); 5031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((k & 1) == 0) ? (1L << k) : (-1L << k); 5041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long accum = 1; 5071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 5081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (k) { 5091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 0: 5101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return accum; 5111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 5121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return checkedMultiply(accum, b); 5131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 5141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if ((k & 1) != 0) { 5151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert accum = checkedMultiply(accum, b); 5161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k >>= 1; 5181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k > 0) { 5191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNoOverflow(b <= FLOOR_SQRT_MAX_LONG); 5201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert b *= b; 5211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting static final long FLOOR_SQRT_MAX_LONG = 3037000499L; 5271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code n!}, that is, the product of the first {@code n} positive 5301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * integers, {@code 1} if {@code n == 0}, or {@link Long#MAX_VALUE} if the 5311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * result does not fit in a {@code long}. 5321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code n < 0} 5341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long factorial(int n) { 5361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("n", n); 5371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (n < FACTORIALS.length) ? FACTORIALS[n] : Long.MAX_VALUE; 5381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final long[] FACTORIALS = { 5411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L, 5421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L, 5431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2, 5441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3, 5451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4, 5461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5, 5471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6, 5481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7, 5491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8, 5501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9, 5511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10, 5521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11, 5531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12, 5541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13, 5551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14, 5561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15, 5571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16, 5581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17, 5591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18, 5601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19, 5611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1L * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 * 17 * 18 * 19 * 20 5621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 5631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code n} choose {@code k}, also known as the binomial coefficient of {@code n} and 5661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code k}, or {@link Long#MAX_VALUE} if the result does not fit in a {@code long}. 5671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0}, or {@code k > n} 5691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static long binomial(int n, int k) { 5711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("n", n); 5721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonNegative("k", k); 5731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(k <= n, "k (%s) > n (%s)", k, n); 5741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k > (n >> 1)) { 5751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k = n - k; 5761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k >= BIGGEST_BINOMIALS.length || n > BIGGEST_BINOMIALS[k]) { 5781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Long.MAX_VALUE; 5791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long result = 1; 5811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (k < BIGGEST_SIMPLE_BINOMIALS.length && n <= BIGGEST_SIMPLE_BINOMIALS[k]) { 5821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // guaranteed not to overflow 5831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < k; i++) { 5841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert result *= n - i; 5851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert result /= i + 1; 5861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 5881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // We want to do this in long math for speed, but want to avoid overflow. 5891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Dividing by the GCD suffices to avoid overflow in all the remaining cases. 5901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 1; i <= k; i++, n--) { 5911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int d = IntMath.gcd(n, i); 5921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert result /= i / d; // (i/d) is guaranteed to divide result 5931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert result *= n / d; 5941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 5971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 6001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * binomial(BIGGEST_BINOMIALS[k], k) fits in a long, but not 6011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * binomial(BIGGEST_BINOMIALS[k] + 1, k). 6021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 6031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final int[] BIGGEST_BINOMIALS = 6041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 3810779, 121977, 16175, 4337, 1733, 6051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 887, 534, 361, 265, 206, 169, 143, 125, 111, 101, 94, 88, 83, 79, 76, 74, 72, 70, 69, 68, 6061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 67, 67, 66, 66, 66, 66}; 6071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 6091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * binomial(BIGGEST_SIMPLE_BINOMIALS[k], k) doesn't need to use the slower GCD-based impl, 6101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * but binomial(BIGGEST_SIMPLE_BINOMIALS[k] + 1, k) does. 6111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 6121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting static final int[] BIGGEST_SIMPLE_BINOMIALS = 6131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 2642246, 86251, 11724, 3218, 1313, 6141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 684, 419, 287, 214, 169, 139, 119, 105, 95, 87, 81, 76, 73, 70, 68, 66, 64, 63, 62, 62, 6151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 61, 61, 61}; 6161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // These values were generated by using checkedMultiply to see when the simple multiply/divide 6171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // algorithm would lead to an overflow. 6181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static boolean fitsInInt(long x) { 6201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (int) x == x; 6211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private LongMath() {} 6241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 625