/*
 * 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 java.math.BigInteger;

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;

Some useful, arithmetics related, additions to the built-in functions in Math. /**
 * Some useful, arithmetics related, additions to the built-in functions in
 * {@link Math}.
 *
 */
public final class ArithmeticUtils {

    
Private constructor. /** Private constructor. */
    private ArithmeticUtils() {
        super();
    }

    
Add two integers, checking for overflow.
Params:
x – an addend
y – an addend
Throws:
MathArithmeticException – if the result can not be represented as an int.
Returns:
the sum x+y
Since:
1.1/**
     * 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.
Params:
a – an addend
b – an addend
Throws:
MathArithmeticException – if the result can not be represented as an long
Returns:
the sum a+b
Since:
1.2/**
     * 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  Binomial
Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set. 

Preconditions:

 0 <= k <= n  (otherwise IllegalArgumentException is thrown)
 The result is small enough to fit into a long. The largest value of n for which all coefficients are  < Long.MAX_VALUE is 66. If the computed value exceeds Long.MAX_VALUE an ArithMeticException is thrown.

Params:
n – the size of the set
k – the size of the subsets to be counted
Throws:
NotPositiveException – if n < 0.
NumberIsTooLargeException – if k > n.
MathArithmeticException – if the result is too large to be
represented by a long integer.
Returns:
n choose k
Deprecated:
use CombinatoricsUtils.binomialCoefficient(int, int)/**
     * 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>
     * <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.</li>
     * </ul></p>
     *
     * @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 double representation of the  Binomial
Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set. 

Preconditions:

 0 <= k <= n  (otherwise IllegalArgumentException is thrown)
 The result is small enough to fit into a double. The largest value of n for which all coefficients are < Double.MAX_VALUE is 1029. If the computed value exceeds Double.MAX_VALUE, Double.POSITIVE_INFINITY is returned

Params:
n – the size of the set
k – the size of the subsets to be counted
Throws:
NotPositiveException – if n < 0.
NumberIsTooLargeException – if k > n.
MathArithmeticException – if the result is too large to be
represented by a long integer.
Returns:
n choose k
Deprecated:
use CombinatoricsUtils.binomialCoefficientDouble(int, int)/**
     * 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>
     * <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</li>
     * </ul></p>
     *
     * @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 log of the  Binomial
Coefficient, "n choose k", the number of k-element subsets that can be selected from an n-element set. 

Preconditions:

 0 <= k <= n  (otherwise IllegalArgumentException is thrown)

Params:
n – the size of the set
k – the size of the subsets to be counted
Throws:
NotPositiveException – if n < 0.
NumberIsTooLargeException – if k > n.
MathArithmeticException – if the result is too large to be
represented by a long integer.
Returns:
n choose k
Deprecated:
use CombinatoricsUtils.binomialCoefficientLog(int, int)/**
     * 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)</li>
     * </ul></p>
     *
     * @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 n  Factorial, the product of the numbers 1,...,n. 

Preconditions:

 n >= 0 (otherwise IllegalArgumentException is thrown)
 The result is small enough to fit into a long. The largest value of n for which n! < Long.MAX_VALUE} is 20. If the computed value exceeds Long.MAX_VALUE an ArithMeticException  is thrown.


Params:
n – argument
Throws:
MathArithmeticException – if the result is too large to be represented by a long.
NotPositiveException – if n < 0.
MathArithmeticException – if n > 20: The factorial value is too large to fit in a long.
Returns:
n!
Deprecated:
use CombinatoricsUtils.factorial(int)/**
     * 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>
     * <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.</li>
     * </ul>
     * </p>
     *
     * @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
factorial of n (the product of the numbers 1 to n), as a double. The result should be small enough to fit into a double: The largest n for which n! < Double.MAX_VALUE is 170. If the computed value exceeds Double.MAX_VALUE, Double.POSITIVE_INFINITY is returned. 
Params:
n – Argument.
Throws:
NotPositiveException – if n < 0.
Returns:
n!
Deprecated:
use CombinatoricsUtils.factorialDouble(int)/**
     * 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 n. 
Params:
n – Argument.
Throws:
NotPositiveException – if n < 0.
Returns:
n!
Deprecated:
use CombinatoricsUtils.factorialLog(int)/**
     * 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).


Special cases:

 
The invocations gcd(Integer.MIN_VALUE, Integer.MIN_VALUE), gcd(Integer.MIN_VALUE, 0) and gcd(0, Integer.MIN_VALUE) throw an ArithmeticException, because the result would be 2^31, which is too large for an int value.
 
The result of gcd(x, x), gcd(0, x) and gcd(x, 0) is the absolute value of x, except for the special cases above.
 
The invocation gcd(0, 0) is the only one which returns 0.

Params:
p – Number.
q – Number.
Throws:
MathArithmeticException – if the result cannot be represented as a non-negative int value.
Returns:
the greatest common divisor (never negative).
Since:
1.1/**
     * 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>
     *  <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>
     *  <li>The invocation {@code gcd(0, 0)} is the only one which returns
     *   {@code 0}.</li>
     * </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 positive numbers
(this precondition is not 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).


Special cases:

 
The result of gcd(x, x), gcd(0, x) and gcd(x, 0) is the value of x.
 
The invocation gcd(0, 0) is the only one which returns 0.

Params:
a – Positive number.
b – Positive number.
Returns:
the greatest common divisor./**
     * 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>
     *  <li>The invocation {@code gcd(0, 0)} is the only one which returns
     *   {@code 0}.</li>
     * </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:

The invocations gcd(Long.MIN_VALUE, Long.MIN_VALUE), gcd(Long.MIN_VALUE, 0L) and gcd(0L, Long.MIN_VALUE) throw an ArithmeticException, because the result would be 2^63, which is too large for a long value.
The result of gcd(x, x), gcd(0L, x) and gcd(x, 0L) is the absolute value of x, except for the special cases above. 
The invocation gcd(0L, 0L) is the only one which returns 0L.

Params:
p – Number.
q – Number.
Throws:
MathArithmeticException – if the result cannot be represented as a non-negative long value.
Returns:
the greatest common divisor, never negative.
Since:
2.1/**
     * <p>
     * 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).
     * </p>
     * 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>
     * <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}.</li>
     * </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 lcm(a,b) = (a / gcd(a,b)) * b. 
Special cases:

The invocations lcm(Integer.MIN_VALUE, n) and lcm(n, Integer.MIN_VALUE), where abs(n) is a power of 2, throw an ArithmeticException, because the result would be 2^31, which is too large for an int value.
The result of lcm(0, x) and lcm(x, 0) is 0 for any x. 
Params:
a – Number.
b – Number.
Throws:
MathArithmeticException – if the result cannot be represented as a non-negative int value.
Returns:
the least common multiple, never negative.
Since:
1.1/**
     * <p>
     * Returns the least common multiple of the absolute value of two numbers,
     * using the formula {@code lcm(a,b) = (a / gcd(a,b)) * b}.
     * </p>
     * 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>
     * <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 lcm(a,b) = (a / gcd(a,b)) * b. 
Special cases:

The invocations lcm(Long.MIN_VALUE, n) and lcm(n, Long.MIN_VALUE), where abs(n) is a power of 2, throw an ArithmeticException, because the result would be 2^63, which is too large for an int value.
The result of lcm(0L, x) and lcm(x, 0L) is 0L for any x. 
Params:
a – Number.
b – Number.
Throws:
MathArithmeticException – if the result cannot be represented as a non-negative long value.
Returns:
the least common multiple, never negative.
Since:
2.1/**
     * <p>
     * Returns the least common multiple of the absolute value of two numbers,
     * using the formula {@code lcm(a,b) = (a / gcd(a,b)) * b}.
     * </p>
     * 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>
     * <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.
Params:
x – Factor.
y – Factor.
Throws:
MathArithmeticException – if the result can not be represented as an int.
Returns:
the product x * y.
Since:
1.1/**
     * 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.
Params:
a – Factor.
b – Factor.
Throws:
MathArithmeticException – if the result can not be represented as a long.
Returns:
the product a * b.
Since:
1.2/**
     * 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.
Params:
x – Minuend.
y – Subtrahend.
Throws:
MathArithmeticException – if the result can not be represented as an int.
Returns:
the difference x - y.
Since:
1.1/**
     * 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.
Params:
a – Value.
b – Value.
Throws:
MathArithmeticException – if the result can not be represented as a long.
Returns:
the difference a - b.
Since:
1.2/**
     * 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.
Params:
k – Number to raise.
e – Exponent (must be positive or zero).
Throws:
NotPositiveException – if e < 0.
MathArithmeticException – if the result would overflow.
Returns:
\( k^e \)/**
     * 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.
Params:
k – Number to raise.
e – Exponent (must be positive or zero).
Throws:
NotPositiveException – if e < 0.
Returns:
ke
Deprecated:
As of 3.3. Please use pow(int, int) instead./**
     * 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.
Params:
k – Number to raise.
e – Exponent (must be positive or zero).
Throws:
NotPositiveException – if e < 0.
MathArithmeticException – if the result would overflow.
Returns:
\( k^e \)/**
     * 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.
Params:
k – Number to raise.
e – Exponent (must be positive or zero).
Throws:
NotPositiveException – if e < 0.
Returns:
ke
Deprecated:
As of 3.3. Please use pow(long, int) instead./**
     * 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.
Params:
k – Number to raise.
e – Exponent (must be positive or zero).
Throws:
NotPositiveException – if e < 0.
Returns:
ke/**
     * 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.
Params:
k – Number to raise.
e – Exponent (must be positive or zero).
Throws:
NotPositiveException – if e < 0.
Returns:
ke/**
     * 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.
Params:
k – Number to raise.
e – Exponent (must be positive or zero).
Throws:
NotPositiveException – if e < 0.
Returns:
ke/**
     * 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 
Stirling number of the second kind, "S(n,k)", the number of ways of partitioning an n-element set into k non-empty subsets. 
 The preconditions are 0 <= k <= n  (otherwise NotPositiveException is thrown) 
Params:
n – the size of the set
k – the number of non-empty subsets
Throws:
NotPositiveException – if k < 0.
NumberIsTooLargeException – if k > n.
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)
Returns:
S(n,k)
Since:
3.1
Deprecated:
use CombinatoricsUtils.stirlingS2(int, int)/**
     * 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)
     * </p>
     * @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.
Params:
a – Addend.
b – Addend.
pattern – Pattern to use for any thrown exception.
Throws:
MathArithmeticException – if the result cannot be represented as a long.
Returns:
the sum a + b.
Since:
1.2/**
     * 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.
Params:
n – the number to test
Returns:
true if the argument is a power of two/**
     * 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);
    }
}