diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java')
| -rw-r--r-- | src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java | 845 |
1 files changed, 845 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java b/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java new file mode 100644 index 0000000..8f07818 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java @@ -0,0 +1,845 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.util; + +import org.apache.commons.math3.exception.MathArithmeticException; +import org.apache.commons.math3.exception.NotPositiveException; +import org.apache.commons.math3.exception.NumberIsTooLargeException; +import org.apache.commons.math3.exception.util.Localizable; +import org.apache.commons.math3.exception.util.LocalizedFormats; + +import java.math.BigInteger; + +/** Some useful, arithmetics related, additions to the built-in functions in {@link Math}. */ +public final class ArithmeticUtils { + + /** Private constructor. */ + private ArithmeticUtils() { + super(); + } + + /** + * Add two integers, checking for overflow. + * + * @param x an addend + * @param y an addend + * @return the sum {@code x+y} + * @throws MathArithmeticException if the result can not be represented as an {@code int}. + * @since 1.1 + */ + public static int addAndCheck(int x, int y) throws MathArithmeticException { + long s = (long) x + (long) y; + if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) { + throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_ADDITION, x, y); + } + return (int) s; + } + + /** + * Add two long integers, checking for overflow. + * + * @param a an addend + * @param b an addend + * @return the sum {@code a+b} + * @throws MathArithmeticException if the result can not be represented as an long + * @since 1.2 + */ + public static long addAndCheck(long a, long b) throws MathArithmeticException { + return addAndCheck(a, b, LocalizedFormats.OVERFLOW_IN_ADDITION); + } + + /** + * Returns an exact representation of the <a + * href="http://mathworld.wolfram.com/BinomialCoefficient.html">Binomial Coefficient</a>, + * "{@code n choose k}", the number of {@code k}-element subsets that can be selected from an + * {@code n}-element set. + * + * <p><Strong>Preconditions</strong>: + * + * <ul> + * <li>{@code 0 <= k <= n } (otherwise {@code IllegalArgumentException} is thrown) + * <li>The result is small enough to fit into a {@code long}. The largest value of {@code n} + * for which all coefficients are {@code < Long.MAX_VALUE} is 66. If the computed value + * exceeds {@code Long.MAX_VALUE} an {@code ArithMeticException} is thrown. + * </ul> + * + * @param n the size of the set + * @param k the size of the subsets to be counted + * @return {@code n choose k} + * @throws NotPositiveException if {@code n < 0}. + * @throws NumberIsTooLargeException if {@code k > n}. + * @throws MathArithmeticException if the result is too large to be represented by a long + * integer. + * @deprecated use {@link CombinatoricsUtils#binomialCoefficient(int, int)} + */ + @Deprecated + public static long binomialCoefficient(final int n, final int k) + throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { + return CombinatoricsUtils.binomialCoefficient(n, k); + } + + /** + * Returns a {@code double} representation of the <a + * href="http://mathworld.wolfram.com/BinomialCoefficient.html">Binomial Coefficient</a>, + * "{@code n choose k}", the number of {@code k}-element subsets that can be selected from an + * {@code n}-element set. + * + * <p><Strong>Preconditions</strong>: + * + * <ul> + * <li>{@code 0 <= k <= n } (otherwise {@code IllegalArgumentException} is thrown) + * <li>The result is small enough to fit into a {@code double}. The largest value of {@code n} + * for which all coefficients are < Double.MAX_VALUE is 1029. If the computed value + * exceeds Double.MAX_VALUE, Double.POSITIVE_INFINITY is returned + * </ul> + * + * @param n the size of the set + * @param k the size of the subsets to be counted + * @return {@code n choose k} + * @throws NotPositiveException if {@code n < 0}. + * @throws NumberIsTooLargeException if {@code k > n}. + * @throws MathArithmeticException if the result is too large to be represented by a long + * integer. + * @deprecated use {@link CombinatoricsUtils#binomialCoefficientDouble(int, int)} + */ + @Deprecated + public static double binomialCoefficientDouble(final int n, final int k) + throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { + return CombinatoricsUtils.binomialCoefficientDouble(n, k); + } + + /** + * Returns the natural {@code log} of the <a + * href="http://mathworld.wolfram.com/BinomialCoefficient.html">Binomial Coefficient</a>, + * "{@code n choose k}", the number of {@code k}-element subsets that can be selected from an + * {@code n}-element set. + * + * <p><Strong>Preconditions</strong>: + * + * <ul> + * <li>{@code 0 <= k <= n } (otherwise {@code IllegalArgumentException} is thrown) + * </ul> + * + * @param n the size of the set + * @param k the size of the subsets to be counted + * @return {@code n choose k} + * @throws NotPositiveException if {@code n < 0}. + * @throws NumberIsTooLargeException if {@code k > n}. + * @throws MathArithmeticException if the result is too large to be represented by a long + * integer. + * @deprecated use {@link CombinatoricsUtils#binomialCoefficientLog(int, int)} + */ + @Deprecated + public static double binomialCoefficientLog(final int n, final int k) + throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { + return CombinatoricsUtils.binomialCoefficientLog(n, k); + } + + /** + * Returns n!. Shorthand for {@code n} <a href="http://mathworld.wolfram.com/Factorial.html"> + * Factorial</a>, the product of the numbers {@code 1,...,n}. + * + * <p><Strong>Preconditions</strong>: + * + * <ul> + * <li>{@code n >= 0} (otherwise {@code IllegalArgumentException} is thrown) + * <li>The result is small enough to fit into a {@code long}. The largest value of {@code n} + * for which {@code n!} < Long.MAX_VALUE} is 20. If the computed value exceeds {@code + * Long.MAX_VALUE} an {@code ArithMeticException } is thrown. + * </ul> + * + * @param n argument + * @return {@code n!} + * @throws MathArithmeticException if the result is too large to be represented by a {@code + * long}. + * @throws NotPositiveException if {@code n < 0}. + * @throws MathArithmeticException if {@code n > 20}: The factorial value is too large to fit in + * a {@code long}. + * @deprecated use {@link CombinatoricsUtils#factorial(int)} + */ + @Deprecated + public static long factorial(final int n) throws NotPositiveException, MathArithmeticException { + return CombinatoricsUtils.factorial(n); + } + + /** + * Compute n!, the<a href="http://mathworld.wolfram.com/Factorial.html">factorial</a> of {@code + * n} (the product of the numbers 1 to n), as a {@code double}. The result should be small + * enough to fit into a {@code double}: The largest {@code n} for which {@code n! < + * Double.MAX_VALUE} is 170. If the computed value exceeds {@code Double.MAX_VALUE}, {@code + * Double.POSITIVE_INFINITY} is returned. + * + * @param n Argument. + * @return {@code n!} + * @throws NotPositiveException if {@code n < 0}. + * @deprecated use {@link CombinatoricsUtils#factorialDouble(int)} + */ + @Deprecated + public static double factorialDouble(final int n) throws NotPositiveException { + return CombinatoricsUtils.factorialDouble(n); + } + + /** + * Compute the natural logarithm of the factorial of {@code n}. + * + * @param n Argument. + * @return {@code n!} + * @throws NotPositiveException if {@code n < 0}. + * @deprecated use {@link CombinatoricsUtils#factorialLog(int)} + */ + @Deprecated + public static double factorialLog(final int n) throws NotPositiveException { + return CombinatoricsUtils.factorialLog(n); + } + + /** + * Computes the greatest common divisor of the absolute value of two numbers, using a modified + * version of the "binary gcd" method. See Knuth 4.5.2 algorithm B. The algorithm is due to + * Josef Stein (1961). <br> + * Special cases: + * + * <ul> + * <li>The invocations {@code gcd(Integer.MIN_VALUE, Integer.MIN_VALUE)}, {@code + * gcd(Integer.MIN_VALUE, 0)} and {@code gcd(0, Integer.MIN_VALUE)} throw an {@code + * ArithmeticException}, because the result would be 2^31, which is too large for an int + * value. + * <li>The result of {@code gcd(x, x)}, {@code gcd(0, x)} and {@code gcd(x, 0)} is the + * absolute value of {@code x}, except for the special cases above. + * <li>The invocation {@code gcd(0, 0)} is the only one which returns {@code 0}. + * </ul> + * + * @param p Number. + * @param q Number. + * @return the greatest common divisor (never negative). + * @throws MathArithmeticException if the result cannot be represented as a non-negative {@code + * int} value. + * @since 1.1 + */ + public static int gcd(int p, int q) throws MathArithmeticException { + int a = p; + int b = q; + if (a == 0 || b == 0) { + if (a == Integer.MIN_VALUE || b == Integer.MIN_VALUE) { + throw new MathArithmeticException(LocalizedFormats.GCD_OVERFLOW_32_BITS, p, q); + } + return FastMath.abs(a + b); + } + + long al = a; + long bl = b; + boolean useLong = false; + if (a < 0) { + if (Integer.MIN_VALUE == a) { + useLong = true; + } else { + a = -a; + } + al = -al; + } + if (b < 0) { + if (Integer.MIN_VALUE == b) { + useLong = true; + } else { + b = -b; + } + bl = -bl; + } + if (useLong) { + if (al == bl) { + throw new MathArithmeticException(LocalizedFormats.GCD_OVERFLOW_32_BITS, p, q); + } + long blbu = bl; + bl = al; + al = blbu % al; + if (al == 0) { + if (bl > Integer.MAX_VALUE) { + throw new MathArithmeticException(LocalizedFormats.GCD_OVERFLOW_32_BITS, p, q); + } + return (int) bl; + } + blbu = bl; + + // Now "al" and "bl" fit in an "int". + b = (int) al; + a = (int) (blbu % al); + } + + return gcdPositive(a, b); + } + + /** + * Computes the greatest common divisor of two <em>positive</em> numbers (this precondition is + * <em>not</em> checked and the result is undefined if not fulfilled) using the "binary gcd" + * method which avoids division and modulo operations. See Knuth 4.5.2 algorithm B. The + * algorithm is due to Josef Stein (1961). <br> + * Special cases: + * + * <ul> + * <li>The result of {@code gcd(x, x)}, {@code gcd(0, x)} and {@code gcd(x, 0)} is the value + * of {@code x}. + * <li>The invocation {@code gcd(0, 0)} is the only one which returns {@code 0}. + * </ul> + * + * @param a Positive number. + * @param b Positive number. + * @return the greatest common divisor. + */ + private static int gcdPositive(int a, int b) { + if (a == 0) { + return b; + } else if (b == 0) { + return a; + } + + // Make "a" and "b" odd, keeping track of common power of 2. + final int aTwos = Integer.numberOfTrailingZeros(a); + a >>= aTwos; + final int bTwos = Integer.numberOfTrailingZeros(b); + b >>= bTwos; + final int shift = FastMath.min(aTwos, bTwos); + + // "a" and "b" are positive. + // If a > b then "gdc(a, b)" is equal to "gcd(a - b, b)". + // If a < b then "gcd(a, b)" is equal to "gcd(b - a, a)". + // Hence, in the successive iterations: + // "a" becomes the absolute difference of the current values, + // "b" becomes the minimum of the current values. + while (a != b) { + final int delta = a - b; + b = Math.min(a, b); + a = Math.abs(delta); + + // Remove any power of 2 in "a" ("b" is guaranteed to be odd). + a >>= Integer.numberOfTrailingZeros(a); + } + + // Recover the common power of 2. + return a << shift; + } + + /** + * Gets the greatest common divisor of the absolute value of two numbers, using the "binary gcd" + * method which avoids division and modulo operations. See Knuth 4.5.2 algorithm B. This + * algorithm is due to Josef Stein (1961). Special cases: + * + * <ul> + * <li>The invocations {@code gcd(Long.MIN_VALUE, Long.MIN_VALUE)}, {@code gcd(Long.MIN_VALUE, + * 0L)} and {@code gcd(0L, Long.MIN_VALUE)} throw an {@code ArithmeticException}, because + * the result would be 2^63, which is too large for a long value. + * <li>The result of {@code gcd(x, x)}, {@code gcd(0L, x)} and {@code gcd(x, 0L)} is the + * absolute value of {@code x}, except for the special cases above. + * <li>The invocation {@code gcd(0L, 0L)} is the only one which returns {@code 0L}. + * </ul> + * + * @param p Number. + * @param q Number. + * @return the greatest common divisor, never negative. + * @throws MathArithmeticException if the result cannot be represented as a non-negative {@code + * long} value. + * @since 2.1 + */ + public static long gcd(final long p, final long q) throws MathArithmeticException { + long u = p; + long v = q; + if ((u == 0) || (v == 0)) { + if ((u == Long.MIN_VALUE) || (v == Long.MIN_VALUE)) { + throw new MathArithmeticException(LocalizedFormats.GCD_OVERFLOW_64_BITS, p, q); + } + return FastMath.abs(u) + FastMath.abs(v); + } + // keep u and v negative, as negative integers range down to + // -2^63, while positive numbers can only be as large as 2^63-1 + // (i.e. we can't necessarily negate a negative number without + // overflow) + /* assert u!=0 && v!=0; */ + if (u > 0) { + u = -u; + } // make u negative + if (v > 0) { + v = -v; + } // make v negative + // B1. [Find power of 2] + int k = 0; + while ((u & 1) == 0 && (v & 1) == 0 && k < 63) { // while u and v are + // both even... + u /= 2; + v /= 2; + k++; // cast out twos. + } + if (k == 63) { + throw new MathArithmeticException(LocalizedFormats.GCD_OVERFLOW_64_BITS, p, q); + } + // B2. Initialize: u and v have been divided by 2^k and at least + // one is odd. + long t = ((u & 1) == 1) ? v : -(u / 2) /* B3 */; + // t negative: u was odd, v may be even (t replaces v) + // t positive: u was even, v is odd (t replaces u) + do { + /* assert u<0 && v<0; */ + // B4/B3: cast out twos from t. + while ((t & 1) == 0) { // while t is even.. + t /= 2; // cast out twos + } + // B5 [reset max(u,v)] + if (t > 0) { + u = -t; + } else { + v = t; + } + // B6/B3. at this point both u and v should be odd. + t = (v - u) / 2; + // |u| larger: t positive (replace u) + // |v| larger: t negative (replace v) + } while (t != 0); + return -u * (1L << k); // gcd is u*2^k + } + + /** + * Returns the least common multiple of the absolute value of two numbers, using the formula + * {@code lcm(a,b) = (a / gcd(a,b)) * b}. Special cases: + * + * <ul> + * <li>The invocations {@code lcm(Integer.MIN_VALUE, n)} and {@code lcm(n, + * Integer.MIN_VALUE)}, where {@code abs(n)} is a power of 2, throw an {@code + * ArithmeticException}, because the result would be 2^31, which is too large for an int + * value. + * <li>The result of {@code lcm(0, x)} and {@code lcm(x, 0)} is {@code 0} for any {@code x}. + * </ul> + * + * @param a Number. + * @param b Number. + * @return the least common multiple, never negative. + * @throws MathArithmeticException if the result cannot be represented as a non-negative {@code + * int} value. + * @since 1.1 + */ + public static int lcm(int a, int b) throws MathArithmeticException { + if (a == 0 || b == 0) { + return 0; + } + int lcm = FastMath.abs(ArithmeticUtils.mulAndCheck(a / gcd(a, b), b)); + if (lcm == Integer.MIN_VALUE) { + throw new MathArithmeticException(LocalizedFormats.LCM_OVERFLOW_32_BITS, a, b); + } + return lcm; + } + + /** + * Returns the least common multiple of the absolute value of two numbers, using the formula + * {@code lcm(a,b) = (a / gcd(a,b)) * b}. Special cases: + * + * <ul> + * <li>The invocations {@code lcm(Long.MIN_VALUE, n)} and {@code lcm(n, Long.MIN_VALUE)}, + * where {@code abs(n)} is a power of 2, throw an {@code ArithmeticException}, because the + * result would be 2^63, which is too large for an int value. + * <li>The result of {@code lcm(0L, x)} and {@code lcm(x, 0L)} is {@code 0L} for any {@code + * x}. + * </ul> + * + * @param a Number. + * @param b Number. + * @return the least common multiple, never negative. + * @throws MathArithmeticException if the result cannot be represented as a non-negative {@code + * long} value. + * @since 2.1 + */ + public static long lcm(long a, long b) throws MathArithmeticException { + if (a == 0 || b == 0) { + return 0; + } + long lcm = FastMath.abs(ArithmeticUtils.mulAndCheck(a / gcd(a, b), b)); + if (lcm == Long.MIN_VALUE) { + throw new MathArithmeticException(LocalizedFormats.LCM_OVERFLOW_64_BITS, a, b); + } + return lcm; + } + + /** + * Multiply two integers, checking for overflow. + * + * @param x Factor. + * @param y Factor. + * @return the product {@code x * y}. + * @throws MathArithmeticException if the result can not be represented as an {@code int}. + * @since 1.1 + */ + public static int mulAndCheck(int x, int y) throws MathArithmeticException { + long m = ((long) x) * ((long) y); + if (m < Integer.MIN_VALUE || m > Integer.MAX_VALUE) { + throw new MathArithmeticException(); + } + return (int) m; + } + + /** + * Multiply two long integers, checking for overflow. + * + * @param a Factor. + * @param b Factor. + * @return the product {@code a * b}. + * @throws MathArithmeticException if the result can not be represented as a {@code long}. + * @since 1.2 + */ + public static long mulAndCheck(long a, long b) throws MathArithmeticException { + long ret; + if (a > b) { + // use symmetry to reduce boundary cases + ret = mulAndCheck(b, a); + } else { + if (a < 0) { + if (b < 0) { + // check for positive overflow with negative a, negative b + if (a >= Long.MAX_VALUE / b) { + ret = a * b; + } else { + throw new MathArithmeticException(); + } + } else if (b > 0) { + // check for negative overflow with negative a, positive b + if (Long.MIN_VALUE / b <= a) { + ret = a * b; + } else { + throw new MathArithmeticException(); + } + } else { + // assert b == 0 + ret = 0; + } + } else if (a > 0) { + // assert a > 0 + // assert b > 0 + + // check for positive overflow with positive a, positive b + if (a <= Long.MAX_VALUE / b) { + ret = a * b; + } else { + throw new MathArithmeticException(); + } + } else { + // assert a == 0 + ret = 0; + } + } + return ret; + } + + /** + * Subtract two integers, checking for overflow. + * + * @param x Minuend. + * @param y Subtrahend. + * @return the difference {@code x - y}. + * @throws MathArithmeticException if the result can not be represented as an {@code int}. + * @since 1.1 + */ + public static int subAndCheck(int x, int y) throws MathArithmeticException { + long s = (long) x - (long) y; + if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) { + throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_SUBTRACTION, x, y); + } + return (int) s; + } + + /** + * Subtract two long integers, checking for overflow. + * + * @param a Value. + * @param b Value. + * @return the difference {@code a - b}. + * @throws MathArithmeticException if the result can not be represented as a {@code long}. + * @since 1.2 + */ + public static long subAndCheck(long a, long b) throws MathArithmeticException { + long ret; + if (b == Long.MIN_VALUE) { + if (a < 0) { + ret = a - b; + } else { + throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_ADDITION, a, -b); + } + } else { + // use additive inverse + ret = addAndCheck(a, -b, LocalizedFormats.OVERFLOW_IN_ADDITION); + } + return ret; + } + + /** + * Raise an int to an int power. + * + * @param k Number to raise. + * @param e Exponent (must be positive or zero). + * @return \( k^e \) + * @throws NotPositiveException if {@code e < 0}. + * @throws MathArithmeticException if the result would overflow. + */ + public static int pow(final int k, final int e) + throws NotPositiveException, MathArithmeticException { + if (e < 0) { + throw new NotPositiveException(LocalizedFormats.EXPONENT, e); + } + + try { + int exp = e; + int result = 1; + int k2p = k; + while (true) { + if ((exp & 0x1) != 0) { + result = mulAndCheck(result, k2p); + } + + exp >>= 1; + if (exp == 0) { + break; + } + + k2p = mulAndCheck(k2p, k2p); + } + + return result; + } catch (MathArithmeticException mae) { + // Add context information. + mae.getContext().addMessage(LocalizedFormats.OVERFLOW); + mae.getContext().addMessage(LocalizedFormats.BASE, k); + mae.getContext().addMessage(LocalizedFormats.EXPONENT, e); + + // Rethrow. + throw mae; + } + } + + /** + * Raise an int to a long power. + * + * @param k Number to raise. + * @param e Exponent (must be positive or zero). + * @return k<sup>e</sup> + * @throws NotPositiveException if {@code e < 0}. + * @deprecated As of 3.3. Please use {@link #pow(int,int)} instead. + */ + @Deprecated + public static int pow(final int k, long e) throws NotPositiveException { + if (e < 0) { + throw new NotPositiveException(LocalizedFormats.EXPONENT, e); + } + + int result = 1; + int k2p = k; + while (e != 0) { + if ((e & 0x1) != 0) { + result *= k2p; + } + k2p *= k2p; + e >>= 1; + } + + return result; + } + + /** + * Raise a long to an int power. + * + * @param k Number to raise. + * @param e Exponent (must be positive or zero). + * @return \( k^e \) + * @throws NotPositiveException if {@code e < 0}. + * @throws MathArithmeticException if the result would overflow. + */ + public static long pow(final long k, final int e) + throws NotPositiveException, MathArithmeticException { + if (e < 0) { + throw new NotPositiveException(LocalizedFormats.EXPONENT, e); + } + + try { + int exp = e; + long result = 1; + long k2p = k; + while (true) { + if ((exp & 0x1) != 0) { + result = mulAndCheck(result, k2p); + } + + exp >>= 1; + if (exp == 0) { + break; + } + + k2p = mulAndCheck(k2p, k2p); + } + + return result; + } catch (MathArithmeticException mae) { + // Add context information. + mae.getContext().addMessage(LocalizedFormats.OVERFLOW); + mae.getContext().addMessage(LocalizedFormats.BASE, k); + mae.getContext().addMessage(LocalizedFormats.EXPONENT, e); + + // Rethrow. + throw mae; + } + } + + /** + * Raise a long to a long power. + * + * @param k Number to raise. + * @param e Exponent (must be positive or zero). + * @return k<sup>e</sup> + * @throws NotPositiveException if {@code e < 0}. + * @deprecated As of 3.3. Please use {@link #pow(long,int)} instead. + */ + @Deprecated + public static long pow(final long k, long e) throws NotPositiveException { + if (e < 0) { + throw new NotPositiveException(LocalizedFormats.EXPONENT, e); + } + + long result = 1l; + long k2p = k; + while (e != 0) { + if ((e & 0x1) != 0) { + result *= k2p; + } + k2p *= k2p; + e >>= 1; + } + + return result; + } + + /** + * Raise a BigInteger to an int power. + * + * @param k Number to raise. + * @param e Exponent (must be positive or zero). + * @return k<sup>e</sup> + * @throws NotPositiveException if {@code e < 0}. + */ + public static BigInteger pow(final BigInteger k, int e) throws NotPositiveException { + if (e < 0) { + throw new NotPositiveException(LocalizedFormats.EXPONENT, e); + } + + return k.pow(e); + } + + /** + * Raise a BigInteger to a long power. + * + * @param k Number to raise. + * @param e Exponent (must be positive or zero). + * @return k<sup>e</sup> + * @throws NotPositiveException if {@code e < 0}. + */ + public static BigInteger pow(final BigInteger k, long e) throws NotPositiveException { + if (e < 0) { + throw new NotPositiveException(LocalizedFormats.EXPONENT, e); + } + + BigInteger result = BigInteger.ONE; + BigInteger k2p = k; + while (e != 0) { + if ((e & 0x1) != 0) { + result = result.multiply(k2p); + } + k2p = k2p.multiply(k2p); + e >>= 1; + } + + return result; + } + + /** + * Raise a BigInteger to a BigInteger power. + * + * @param k Number to raise. + * @param e Exponent (must be positive or zero). + * @return k<sup>e</sup> + * @throws NotPositiveException if {@code e < 0}. + */ + public static BigInteger pow(final BigInteger k, BigInteger e) throws NotPositiveException { + if (e.compareTo(BigInteger.ZERO) < 0) { + throw new NotPositiveException(LocalizedFormats.EXPONENT, e); + } + + BigInteger result = BigInteger.ONE; + BigInteger k2p = k; + while (!BigInteger.ZERO.equals(e)) { + if (e.testBit(0)) { + result = result.multiply(k2p); + } + k2p = k2p.multiply(k2p); + e = e.shiftRight(1); + } + + return result; + } + + /** + * Returns the <a href="http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html"> + * Stirling number of the second kind</a>, "{@code S(n,k)}", the number of ways of partitioning + * an {@code n}-element set into {@code k} non-empty subsets. + * + * <p>The preconditions are {@code 0 <= k <= n } (otherwise {@code NotPositiveException} is + * thrown) + * + * @param n the size of the set + * @param k the number of non-empty subsets + * @return {@code S(n,k)} + * @throws NotPositiveException if {@code k < 0}. + * @throws NumberIsTooLargeException if {@code k > n}. + * @throws MathArithmeticException if some overflow happens, typically for n exceeding 25 and k + * between 20 and n-2 (S(n,n-1) is handled specifically and does not overflow) + * @since 3.1 + * @deprecated use {@link CombinatoricsUtils#stirlingS2(int, int)} + */ + @Deprecated + public static long stirlingS2(final int n, final int k) + throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { + return CombinatoricsUtils.stirlingS2(n, k); + } + + /** + * Add two long integers, checking for overflow. + * + * @param a Addend. + * @param b Addend. + * @param pattern Pattern to use for any thrown exception. + * @return the sum {@code a + b}. + * @throws MathArithmeticException if the result cannot be represented as a {@code long}. + * @since 1.2 + */ + private static long addAndCheck(long a, long b, Localizable pattern) + throws MathArithmeticException { + final long result = a + b; + if (!((a ^ b) < 0 | (a ^ result) >= 0)) { + throw new MathArithmeticException(pattern, a, b); + } + return result; + } + + /** + * Returns true if the argument is a power of two. + * + * @param n the number to test + * @return true if the argument is a power of two + */ + public static boolean isPowerOfTwo(long n) { + return (n > 0) && ((n & (n - 1)) == 0); + } +} |