/*
 * 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.numbers.fraction;

import java.io.Serializable;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.Objects;
import org.apache.commons.numbers.core.ArithmeticUtils;
import org.apache.commons.numbers.core.NativeOperators;

/**
 * Representation of a rational number using arbitrary precision.
 *
 * <p>The number is expressed as the quotient {@code p/q} of two {@link BigInteger}s,
 * a numerator {@code p} and a non-zero denominator {@code q}.
 *
 * <p>This class is immutable.
 *
 * <a href="https://en.wikipedia.org/wiki/Rational_number">Rational number</a>
 */
public final class BigFraction
    extends Number
    implements Comparable<BigFraction>,
               NativeOperators<BigFraction>,
               Serializable {
    /** A fraction representing "0". */
    public static final BigFraction ZERO = of(0);

    /** A fraction representing "1". */
    public static final BigFraction ONE = of(1);

    /** Serializable version identifier. */
    private static final long serialVersionUID = 20190701L;

    /** Message for non-finite input double argument to factory constructors. */
    private static final String NOT_FINITE = "Not finite: ";

    /** The numerator of this fraction reduced to lowest terms. */
    private final BigInteger numerator;

    /** The denominator of this fraction reduced to lowest terms. */
    private final BigInteger denominator;

    /**
     * Private constructor: Instances are created using factory methods.
     *
     * @param num Numerator, must not be {@code null}.
     * @param den Denominator, must not be {@code null}.
     * @throws ArithmeticException if the denominator is zero.
     */
    private BigFraction(BigInteger num, BigInteger den) {
        if (den.signum() == 0) {
            throw new FractionException(FractionException.ERROR_ZERO_DENOMINATOR);
        }

        // reduce numerator and denominator by greatest common denominator
        final BigInteger gcd = num.gcd(den);
        if (BigInteger.ONE.compareTo(gcd) < 0) {
            numerator = num.divide(gcd);
            denominator = den.divide(gcd);
        } else {
            numerator = num;
            denominator = den;
        }
    }

    /**
     * Private constructor: Instances are created using factory methods.
     *
     * <p>This sets the denominator to 1.
     *
     * @param num Numerator (must not be null).
     */
    private BigFraction(BigInteger num) {
        numerator = num;
        denominator = BigInteger.ONE;
    }

    /**
     * Create a fraction given the double value and either the maximum
     * error allowed or the maximum number of denominator digits.
     *
     * <p>
     * NOTE: This method is called with:
     * </p>
     * <ul>
     *  <li>EITHER a valid epsilon value and the maxDenominator set to
     *      Integer.MAX_VALUE (that way the maxDenominator has no effect)
     *  <li>OR a valid maxDenominator value and the epsilon value set to
     *      zero (that way epsilon only has effect if there is an exact
     *      match before the maxDenominator value is reached).
     * </ul>
     * <p>
     * It has been done this way so that the same code can be reused for
     * both scenarios. However this could be confusing to users if it
     * were part of the public API and this method should therefore remain
     * PRIVATE.
     * </p>
     *
     * <p>
     * See JIRA issue ticket MATH-181 for more details:
     *     https://issues.apache.org/jira/browse/MATH-181
     * </p>
     *
     * @param value Value to convert to a fraction.
     * @param epsilon Maximum error allowed.
     * The resulting fraction is within {@code epsilon} of {@code value},
     * in absolute terms.
     * @param maxDenominator Maximum denominator value allowed.
     * @param maxIterations Maximum number of convergents.
     * @return a new instance.
     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
     * @throws ArithmeticException if the continued fraction failed to converge.
     */
    private static BigFraction from(final double value,
                                    final double epsilon,
                                    final int maxDenominator,
                                    final int maxIterations) {
        if (!Double.isFinite(value)) {
            throw new IllegalArgumentException(NOT_FINITE + value);
        }

        final long overflow = Integer.MAX_VALUE;
        double r0 = value;
        long a0 = (long) Math.floor(r0);

        if (Math.abs(a0) > overflow) {
            throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, a0, 1L);
        }

        // check for (almost) integer arguments, which should not go
        // to iterations.
        if (Math.abs(a0 - value) < epsilon) {
            return new BigFraction(BigInteger.valueOf(a0),
                                   BigInteger.ONE);
        }

        long p0 = 1;
        long q0 = 0;
        long p1 = a0;
        long q1 = 1;

        long p2 = 0;
        long q2 = 1;

        int n = 0;
        boolean stop = false;
        do {
            ++n;
            final double r1 = 1d / (r0 - a0);
            final long a1 = (long) Math.floor(r1);
            p2 = (a1 * p1) + p0;
            q2 = (a1 * q1) + q0;
            if (p2 > overflow ||
                q2 > overflow) {
                // in maxDenominator mode, if the last fraction was very close to the actual value
                // q2 may overflow in the next iteration; in this case return the last one.
                if (epsilon == 0 &&
                    Math.abs(q1) < maxDenominator) {
                    break;
                }
                throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, p2, q2);
            }

            final double convergent = (double) p2 / (double) q2;
            if (n < maxIterations &&
                Math.abs(convergent - value) > epsilon &&
                q2 < maxDenominator) {
                p0 = p1;
                p1 = p2;
                q0 = q1;
                q1 = q2;
                a0 = a1;
                r0 = r1;
            } else {
                stop = true;
            }
        } while (!stop);

        if (n >= maxIterations) {
            throw new FractionException(FractionException.ERROR_CONVERSION, value, maxIterations);
        }

        return q2 < maxDenominator ?
            new BigFraction(BigInteger.valueOf(p2),
                            BigInteger.valueOf(q2)) :
            new BigFraction(BigInteger.valueOf(p1),
                            BigInteger.valueOf(q1));
    }

    /**
     * Create a fraction given the double value.
     * <p>
     * This factory method behaves <em>differently</em> to the method
     * {@link #from(double, double, int)}. It converts the double value
     * exactly, considering its internal bits representation. This works for all
     * values except NaN and infinities and does not requires any loop or
     * convergence threshold.
     * </p>
     * <p>
     * Since this conversion is exact and since double numbers are sometimes
     * approximated, the fraction created may seem strange in some cases. For example,
     * calling {@code from(1.0 / 3.0)} does <em>not</em> create
     * the fraction \( \frac{1}{3} \), but the fraction \( \frac{6004799503160661}{18014398509481984} \)
     * because the double number passed to the method is not exactly \( \frac{1}{3} \)
     * (which cannot be represented exactly in IEEE754).
     * </p>
     *
     * @param value Value to convert to a fraction.
     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
     * @return a new instance.
     *
     * @see #from(double,double,int)
     */
    public static BigFraction from(final double value) {
        if (!Double.isFinite(value)) {
            throw new IllegalArgumentException(NOT_FINITE + value);
        }

        final long bits = Double.doubleToLongBits(value);
        final long sign = bits & 0x8000000000000000L;
        final long exponent = bits & 0x7ff0000000000000L;
        final long mantissa = bits & 0x000fffffffffffffL;

        // Compute m and k such that value = m * 2^k
        long m;
        int k;

        if (exponent == 0) {
            m = mantissa;
            k = 0; // For simplicity, when number is 0.
            if (m != 0) {
                // Subnormal number, the effective exponent bias is 1022, not 1023.
                k = -1074;
            }
        } else {
            // Normalized number: Add the implicit most significant bit.
            m = mantissa | 0x0010000000000000L;
            k = ((int) (exponent >> 52)) - 1075; // Exponent bias is 1023.
        }
        if (sign != 0) {
            m = -m;
        }
        while ((m & 0x001ffffffffffffeL) != 0 &&
               (m & 0x1) == 0) {
            m >>= 1;
            ++k;
        }

        return k < 0 ?
            new BigFraction(BigInteger.valueOf(m),
                            BigInteger.ZERO.flipBit(-k)) :
            new BigFraction(BigInteger.valueOf(m).multiply(BigInteger.ZERO.flipBit(k)),
                            BigInteger.ONE);
    }

    /**
     * Create a fraction given the double value and maximum error allowed.
     * <p>
     * References:
     * <ul>
     * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
     * Continued Fraction</a> equations (11) and (22)-(26)</li>
     * </ul>
     *
     * @param value Value to convert to a fraction.
     * @param epsilon Maximum error allowed. The resulting fraction is within
     * {@code epsilon} of {@code value}, in absolute terms.
     * @param maxIterations Maximum number of convergents.
     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
     * @throws ArithmeticException if the continued fraction failed to converge.
     * @return a new instance.
     */
    public static BigFraction from(final double value,
                                   final double epsilon,
                                   final int maxIterations) {
        return from(value, epsilon, Integer.MAX_VALUE, maxIterations);
    }

    /**
     * Create a fraction given the double value and maximum denominator.
     * <p>
     * References:
     * <ul>
     * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
     * Continued Fraction</a> equations (11) and (22)-(26)</li>
     * </ul>
     *
     * @param value Value to convert to a fraction.
     * @param maxDenominator Maximum allowed value for denominator.
     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
     * @throws ArithmeticException if the continued fraction failed to converge.
     * @return a new instance.
     */
    public static BigFraction from(final double value,
                                   final int maxDenominator) {
        return from(value, 0, maxDenominator, 100);
    }

    /**
     * Create a fraction given the numerator. The denominator is {@code 1}.
     *
     * @param num
     *            the numerator.
     * @return a new instance.
     */
    public static BigFraction of(final int num) {
        return new BigFraction(BigInteger.valueOf(num));
    }

    /**
     * Create a fraction given the numerator. The denominator is {@code 1}.
     *
     * @param num Numerator.
     * @return a new instance.
     */
    public static BigFraction of(final long num) {
        return new BigFraction(BigInteger.valueOf(num));
    }

    /**
     * Create a fraction given the numerator. The denominator is {@code 1}.
     *
     * @param num Numerator.
     * @return a new instance.
     * @throws NullPointerException if numerator is null.
     */
    public static BigFraction of(final BigInteger num) {
        Objects.requireNonNull(num, "numerator");
        return new BigFraction(num);
    }

    /**
     * Create a fraction given the numerator and denominator.
     * The fraction is reduced to lowest terms.
     *
     * @param num Numerator.
     * @param den Denominator.
     * @return a new instance.
     * @throws ArithmeticException if {@code den} is zero.
     */
    public static BigFraction of(final int num, final int den) {
        return new BigFraction(BigInteger.valueOf(num), BigInteger.valueOf(den));
    }

    /**
     * Create a fraction given the numerator and denominator.
     * The fraction is reduced to lowest terms.
     *
     * @param num Numerator.
     * @param den Denominator.
     * @return a new instance.
     * @throws ArithmeticException if {@code den} is zero.
     */
    public static BigFraction of(final long num, final long den) {
        return new BigFraction(BigInteger.valueOf(num), BigInteger.valueOf(den));
    }

    /**
     * Create a fraction given the numerator and denominator.
     * The fraction is reduced to lowest terms.
     *
     * @param num Numerator.
     * @param den Denominator.
     * @return a new instance.
     * @throws NullPointerException if numerator or denominator are null.
     * @throws ArithmeticException if the denominator is zero.
     */
    public static BigFraction of(final BigInteger num, final BigInteger den) {
        return new BigFraction(num, den);
    }

    /**
     * Returns a {@code BigFraction} instance representing the specified string {@code s}.
     *
     * <p>If {@code s} is {@code null}, then a {@code NullPointerException} is thrown.
     *
     * <p>The string must be in a format compatible with that produced by
     * {@link #toString() BigFraction.toString()}.
     * The format expects an integer optionally followed by a {@code '/'} character and
     * and second integer. Leading and trailing spaces are allowed around each numeric part.
     * Each numeric part is parsed using {@link BigInteger#BigInteger(String)}. The parts
     * are interpreted as the numerator and optional denominator of the fraction. If absent
     * the denominator is assumed to be "1".
     *
     * <p>Examples of valid strings and the equivalent {@code BigFraction} are shown below:
     *
     * <pre>
     * "0"                 = BigFraction.of(0)
     * "42"                = BigFraction.of(42)
     * "0 / 1"             = BigFraction.of(0, 1)
     * "1 / 3"             = BigFraction.of(1, 3)
     * "-4 / 13"           = BigFraction.of(-4, 13)</pre>
     *
     * <p>Note: The fraction is returned in reduced form and the numerator and denominator
     * may not match the values in the input string. For this reason the result of
     * {@code BigFraction.parse(s).toString().equals(s)} may not be {@code true}.
     *
     * @param s String representation.
     * @return an instance.
     * @throws NullPointerException if the string is null.
     * @throws NumberFormatException if the string does not contain a parsable fraction.
     * @see BigInteger#BigInteger(String)
     * @see #toString()
     */
    public static BigFraction parse(String s) {
        final String stripped = s.replace(",", "");
        final int slashLoc = stripped.indexOf('/');
        // if no slash, parse as single number
        if (slashLoc == -1) {
            return BigFraction.of(new BigInteger(stripped.trim()));
        }
        final BigInteger num = new BigInteger(stripped.substring(0, slashLoc).trim());
        final BigInteger denom = new BigInteger(stripped.substring(slashLoc + 1).trim());
        return of(num, denom);
    }

    @Override
    public BigFraction zero() {
        return ZERO;
    }

    @Override
    public BigFraction one() {
        return ONE;
    }

    /**
     * Access the numerator as a {@code BigInteger}.
     *
     * @return the numerator as a {@code BigInteger}.
     */
    public BigInteger getNumerator() {
        return numerator;
    }

    /**
     * Access the numerator as an {@code int}.
     *
     * @return the numerator as an {@code int}.
     */
    public int getNumeratorAsInt() {
        return numerator.intValue();
    }

    /**
     * Access the numerator as a {@code long}.
     *
     * @return the numerator as a {@code long}.
     */
    public long getNumeratorAsLong() {
        return numerator.longValue();
    }

    /**
     * Access the denominator as a {@code BigInteger}.
     *
     * @return the denominator as a {@code BigInteger}.
     */
    public BigInteger getDenominator() {
        return denominator;
    }

    /**
     * Access the denominator as an {@code int}.
     *
     * @return the denominator as an {@code int}.
     */
    public int getDenominatorAsInt() {
        return denominator.intValue();
    }

    /**
     * Access the denominator as a {@code long}.
     *
     * @return the denominator as a {@code long}.
     */
    public long getDenominatorAsLong() {
        return denominator.longValue();
    }

    /**
     * Retrieves the sign of this fraction.
     *
     * @return -1 if the value is strictly negative, 1 if it is strictly
     * positive, 0 if it is 0.
     */
    public int signum() {
        return numerator.signum() * denominator.signum();
    }

    /**
     * Returns the absolute value of this fraction.
     *
     * @return the absolute value.
     */
    public BigFraction abs() {
        return signum() >= 0 ?
            this :
            negate();
    }

    @Override
    public BigFraction negate() {
        return new BigFraction(numerator.negate(), denominator);
    }

    /**
     * {@inheritDoc}
     *
     * <p>Raises an exception if the fraction is equal to zero.
     *
     * @throws ArithmeticException if the current numerator is {@code zero}
     */
    @Override
    public BigFraction reciprocal() {
        return new BigFraction(denominator, numerator);
    }

    /**
     * Returns the {@code double} value closest to this fraction.
     *
     * @return the fraction as a {@code double}.
     */
    @Override
    public double doubleValue() {
        return Double.longBitsToDouble(toFloatingPointBits(11, 52));
    }

    /**
     * Returns the {@code float} value closest to this fraction.
     *
     * @return the fraction as a {@code double}.
     */
    @Override
    public float floatValue() {
        return Float.intBitsToFloat((int) toFloatingPointBits(8, 23));
    }

    /**
     * Returns the whole number part of the fraction.
     *
     * @return the largest {@code int} value that is not larger than this fraction.
     */
    @Override
    public int intValue() {
        return numerator.divide(denominator).intValue();
    }

    /**
     * Returns the whole number part of the fraction.
     *
     * @return the largest {@code long} value that is not larger than this fraction.
     */
    @Override
    public long longValue() {
        return numerator.divide(denominator).longValue();
    }

    /**
     * Returns the {@code BigDecimal} representation of this fraction.
     * This calculates the fraction as numerator divided by denominator.
     *
     * @return the fraction as a {@code BigDecimal}.
     * @throws ArithmeticException
     *             if the exact quotient does not have a terminating decimal
     *             expansion.
     * @see BigDecimal
     */
    public BigDecimal bigDecimalValue() {
        return new BigDecimal(numerator).divide(new BigDecimal(denominator));
    }

    /**
     * Returns the {@code BigDecimal} representation of this fraction.
     * This calculates the fraction as numerator divided by denominator
     * following the passed rounding mode.
     *
     * @param roundingMode Rounding mode to apply.
     * @return the fraction as a {@code BigDecimal}.
     * @see BigDecimal
     */
    public BigDecimal bigDecimalValue(RoundingMode roundingMode) {
        return new BigDecimal(numerator).divide(new BigDecimal(denominator), roundingMode);
    }

    /**
     * Returns the {@code BigDecimal} representation of this fraction.
     * This calculates the fraction as numerator divided by denominator
     * following the passed scale and rounding mode.
     *
     * @param scale
     *            scale of the {@code BigDecimal} quotient to be returned.
     *            see {@link BigDecimal} for more information.
     * @param roundingMode Rounding mode to apply.
     * @return the fraction as a {@code BigDecimal}.
     * @throws ArithmeticException if {@code roundingMode} == {@link RoundingMode#UNNECESSARY} and
     *      the specified scale is insufficient to represent the result of the division exactly.
     * @see BigDecimal
     */
    public BigDecimal bigDecimalValue(final int scale, RoundingMode roundingMode) {
        return new BigDecimal(numerator).divide(new BigDecimal(denominator), scale, roundingMode);
    }

    /**
     * Adds the specified {@code value} to this fraction, returning
     * the result in reduced form.
     *
     * @param value Value to add.
     * @return {@code this + value}.
     */
    public BigFraction add(final int value) {
        return add(BigInteger.valueOf(value));
    }

    /**
     * Adds the specified {@code value} to this fraction, returning
     * the result in reduced form.
     *
     * @param value Value to add.
     * @return {@code this + value}.
     */
    public BigFraction add(final long value) {
        return add(BigInteger.valueOf(value));
    }

    /**
     * Adds the specified {@code value} to this fraction, returning
     * the result in reduced form.
     *
     * @param value Value to add.
     * @return {@code this + value}.
     */
    public BigFraction add(final BigInteger value) {
        if (value.signum() == 0) {
            return this;
        }
        if (isZero()) {
            return of(value);
        }

        return new BigFraction(numerator.add(denominator.multiply(value)), denominator);
    }

    /**
     * Adds the specified {@code value} to this fraction, returning
     * the result in reduced form.
     *
     * @param value Value to add.
     * @return {@code this + value}.
     */
    @Override
    public BigFraction add(final BigFraction value) {
        if (value.isZero()) {
            return this;
        }
        if (isZero()) {
            return value;
        }

        final BigInteger num;
        final BigInteger den;

        if (denominator.equals(value.denominator)) {
            num = numerator.add(value.numerator);
            den = denominator;
        } else {
            num = (numerator.multiply(value.denominator)).add((value.numerator).multiply(denominator));
            den = denominator.multiply(value.denominator);
        }

        if (num.signum() == 0) {
            return ZERO;
        }

        return new BigFraction(num, den);
    }

    /**
     * Subtracts the specified {@code value} from this fraction, returning
     * the result in reduced form.
     *
     * @param value Value to subtract.
     * @return {@code this - value}.
     */
    public BigFraction subtract(final int value) {
        return subtract(BigInteger.valueOf(value));
    }

    /**
     * Subtracts the specified {@code value} from this fraction, returning
     * the result in reduced form.
     *
     * @param value Value to subtract.
     * @return {@code this - value}.
     */
    public BigFraction subtract(final long value) {
        return subtract(BigInteger.valueOf(value));
    }

    /**
     * Subtracts the specified {@code value} from this fraction, returning
     * the result in reduced form.
     *
     * @param value Value to subtract.
     * @return {@code this - value}.
     */
    public BigFraction subtract(final BigInteger value) {
        if (value.signum() == 0) {
            return this;
        }
        if (isZero()) {
            return of(value.negate());
        }

        return new BigFraction(numerator.subtract(denominator.multiply(value)), denominator);
    }

    /**
     * Subtracts the specified {@code value} from this fraction, returning
     * the result in reduced form.
     *
     * @param value Value to subtract.
     * @return {@code this - value}.
     */
    @Override
    public BigFraction subtract(final BigFraction value) {
        if (value.isZero()) {
            return this;
        }
        if (isZero()) {
            return value.negate();
        }

        final BigInteger num;
        final BigInteger den;
        if (denominator.equals(value.denominator)) {
            num = numerator.subtract(value.numerator);
            den = denominator;
        } else {
            num = (numerator.multiply(value.denominator)).subtract((value.numerator).multiply(denominator));
            den = denominator.multiply(value.denominator);
        }
        return new BigFraction(num, den);
    }

    /**
     * Multiply this fraction by the passed {@code value}, returning
     * the result in reduced form.
     *
     * @param value Value to multiply by.
     * @return {@code this * value}.
     */
    @Override
    public BigFraction multiply(final int value) {
        if (value == 0 || isZero()) {
            return ZERO;
        }

        return multiply(BigInteger.valueOf(value));
    }

    /**
     * Multiply this fraction by the passed {@code value}, returning
     * the result in reduced form.
     *
     * @param value Value to multiply by.
     * @return {@code this * value}.
     */
    public BigFraction multiply(final long value) {
        if (value == 0 || isZero()) {
            return ZERO;
        }

        return multiply(BigInteger.valueOf(value));
    }

    /**
     * Multiply this fraction by the passed {@code value}, returning
     * the result in reduced form.
     *
     * @param value Value to multiply by.
     * @return {@code this * value}.
     */
    public BigFraction multiply(final BigInteger value) {
        if (value.signum() == 0 || isZero()) {
            return ZERO;
        }
        return new BigFraction(value.multiply(numerator), denominator);
    }

    /**
     * Multiply this fraction by the passed {@code value}, returning
     * the result in reduced form.
     *
     * @param value Value to multiply by.
     * @return {@code this * value}.
     */
    @Override
    public BigFraction multiply(final BigFraction value) {
        if (value.isZero() || isZero()) {
            return ZERO;
        }
        return new BigFraction(numerator.multiply(value.numerator),
                               denominator.multiply(value.denominator));
    }

    /**
     * Divide this fraction by the passed {@code value}, returning
     * the result in reduced form.
     *
     * @param value Value to divide by
     * @return {@code this / value}.
     * @throws ArithmeticException if the value to divide by is zero
     */
    public BigFraction divide(final int value) {
        return divide(BigInteger.valueOf(value));
    }

    /**
     * Divide this fraction by the passed {@code value}, returning
     * the result in reduced form.
     *
     * @param value Value to divide by
     * @return {@code this / value}.
     * @throws ArithmeticException if the value to divide by is zero
     */
    public BigFraction divide(final long value) {
        return divide(BigInteger.valueOf(value));
    }

    /**
     * Divide this fraction by the passed {@code value}, returning
     * the result in reduced form.
     *
     * @param value Value to divide by
     * @return {@code this / value}.
     * @throws ArithmeticException if the value to divide by is zero
     */
    public BigFraction divide(final BigInteger value) {
        if (value.signum() == 0) {
            throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
        }
        if (isZero()) {
            return this;
        }
        return new BigFraction(numerator, denominator.multiply(value));
    }

    /**
     * Divide this fraction by the passed {@code value}, returning
     * the result in reduced form.
     *
     * @param value Value to divide by
     * @return {@code this / value}.
     * @throws ArithmeticException if the value to divide by is zero
     */
    @Override
    public BigFraction divide(final BigFraction value) {
        if (value.isZero()) {
            throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
        }
        if (isZero()) {
            return this;
        }
        return multiply(value.reciprocal());
    }

    /**
     * Returns a {@code BigFraction} whose value is
     * <code>this<sup>exponent</sup></code>, returning the result in reduced form.
     *
     * @param exponent exponent to which this {@code BigFraction} is to be raised.
     * @return <code>this<sup>exponent</sup></code>.
     */
    @Override
    public BigFraction pow(final int exponent) {
        if (exponent == 0) {
            return ONE;
        }
        if (isZero()) {
            return this;
        }

        if (exponent < 0) {
            return new BigFraction(denominator.pow(-exponent),
                                   numerator.pow(-exponent));
        }
        return new BigFraction(numerator.pow(exponent),
                               denominator.pow(exponent));
    }

    /**
     * Returns a {@code BigFraction} whose value is
     * <code>this<sup>exponent</sup></code>, returning the result in reduced form.
     *
     * @param exponent exponent to which this {@code BigFraction} is to be raised.
     * @return <code>this<sup>exponent</sup></code>.
     */
    public BigFraction pow(final long exponent) {
        if (exponent == 0) {
            return ONE;
        }
        if (isZero()) {
            return this;
        }

        if (exponent < 0) {
            return new BigFraction(ArithmeticUtils.pow(denominator, -exponent),
                                   ArithmeticUtils.pow(numerator,   -exponent));
        }
        return new BigFraction(ArithmeticUtils.pow(numerator,   exponent),
                               ArithmeticUtils.pow(denominator, exponent));
    }

    /**
     * Returns a {@code BigFraction} whose value is
     * <code>this<sup>exponent</sup></code>, returning the result in reduced form.
     *
     * @param exponent exponent to which this {@code BigFraction} is to be raised.
     * @return <code>this<sup>exponent</sup></code>.
     */
    public BigFraction pow(final BigInteger exponent) {
        if (exponent.signum() == 0) {
            return ONE;
        }
        if (isZero()) {
            return this;
        }

        if (exponent.signum() == -1) {
            final BigInteger eNeg = exponent.negate();
            return new BigFraction(ArithmeticUtils.pow(denominator, eNeg),
                                   ArithmeticUtils.pow(numerator,   eNeg));
        }
        return new BigFraction(ArithmeticUtils.pow(numerator,   exponent),
                               ArithmeticUtils.pow(denominator, exponent));
    }

    /**
     * Returns a {@code double} whose value is
     * <code>this<sup>exponent</sup></code>.
     *
     * @param exponent exponent to which this {@code BigFraction} is to be raised.
     * @return <code>this<sup>exponent</sup></code> as a {@code double}.
     */
    public double pow(final double exponent) {
        return Math.pow(numerator.doubleValue(),   exponent) /
               Math.pow(denominator.doubleValue(), exponent);
    }

    /**
     * Returns the {@code String} representing this fraction.
     * Uses:
     * <ul>
     *  <li>{@code "0"} if {@code numerator} is zero.
     *  <li>{@code "numerator"} if {@code denominator} is one.
     *  <li>{@code "numerator / denominator"} for all other cases.
     * </ul>
     *
     * @return a string representation of the fraction.
     */
    @Override
    public String toString() {
        final String str;
        if (BigInteger.ONE.equals(denominator)) {
            str = numerator.toString();
        } else if (isZero()) {
            str = "0";
        } else {
            str = numerator + " / " + denominator;
        }
        return str;
    }

    /**
     * Compares this object with the specified object for order using the signed magnitude.
     *
     * @param other {@inheritDoc}
     * @return {@inheritDoc}
     */
    @Override
    public int compareTo(final BigFraction other) {
        final int lhsSigNum = signum();
        final int rhsSigNum = other.signum();

        if (lhsSigNum != rhsSigNum) {
            return (lhsSigNum > rhsSigNum) ? 1 : -1;
        }
        if (lhsSigNum == 0) {
            return 0;
        }

        final BigInteger nOd = numerator.multiply(other.denominator);
        final BigInteger dOn = denominator.multiply(other.numerator);
        return nOd.compareTo(dOn);
    }

    /**
     * Test for equality with another object. If the other object is a {@code Fraction} then a
     * comparison is made of the sign and magnitude; otherwise {@code false} is returned.
     *
     * @param other {@inheritDoc}
     * @return {@inheritDoc}
     */
    @Override
    public boolean equals(final Object other) {
        if (this == other) {
            return true;
        }

        if (other instanceof BigFraction) {
            // Since fractions are always in lowest terms, numerators and
            // denominators can be compared directly for equality.
            final BigFraction rhs = (BigFraction) other;
            if (signum() == rhs.signum()) {
                return numerator.abs().equals(rhs.numerator.abs()) &&
                       denominator.abs().equals(rhs.denominator.abs());
            }
        }

        return false;
    }

    @Override
    public int hashCode() {
        // Incorporate the sign and absolute values of the numerator and denominator.
        // Equivalent to:
        // int hash = 1;
        // hash = 31 * hash + numerator.abs().hashCode();
        // hash = 31 * hash + denominator.abs().hashCode();
        // hash = hash * signum()
        // Note: BigInteger.hashCode() * BigInteger.signum() == BigInteger.abs().hashCode().
        final int numS = numerator.signum();
        final int denS = denominator.signum();
        return (31 * (31 + numerator.hashCode() * numS) + denominator.hashCode() * denS) * numS * denS;
    }

    /**
     * Calculates the sign bit, the biased exponent and the significand for a
     * binary floating-point representation of this {@code BigFraction}
     * according to the IEEE 754 standard, and encodes these values into a {@code long}
     * variable. The representative bits are arranged adjacent to each other and
     * placed at the low-order end of the returned {@code long} value, with the
     * least significant bits used for the significand, the next more
     * significant bits for the exponent, and next more significant bit for the
     * sign.
     *
     * <p>Warning: The arguments are not validated.
     *
     * @param exponentLength the number of bits allowed for the exponent; must be
     *                       between 1 and 32 (inclusive), and must not be greater
     *                       than {@code 63 - significandLength}
     * @param significandLength the number of bits allowed for the significand
     *                          (excluding the implicit leading 1-bit in
     *                          normalized numbers, e.g. 52 for a double-precision
     *                          floating-point number); must be between 1 and
     *                          {@code 63 - exponentLength} (inclusive)
     * @return the bits of an IEEE 754 binary floating-point representation of
     * this fraction encoded in a {@code long}, as described above.
     */
    private long toFloatingPointBits(int exponentLength, int significandLength) {
        // Assume the following conditions:
        //assert exponentLength >= 1;
        //assert exponentLength <= 32;
        //assert significandLength >= 1;
        //assert significandLength <= 63 - exponentLength;

        if (isZero()) {
            return 0L;
        }

        final long sign = (numerator.signum() * denominator.signum()) == -1 ? 1L : 0L;
        final BigInteger positiveNumerator = numerator.abs();
        final BigInteger positiveDenominator = denominator.abs();

        /*
         * The most significant 1-bit of a non-zero number is not explicitly
         * stored in the significand of an IEEE 754 normalized binary
         * floating-point number, so we need to round the value of this fraction
         * to (significandLength + 1) bits. In order to do this, we calculate
         * the most significant (significandLength + 2) bits, and then, based on
         * the least significant of those bits, find out whether we need to
         * round up or down.
         *
         * First, we'll remove all powers of 2 from the denominator because they
         * are not relevant for the significand of the prospective binary
         * floating-point value.
         */
        final int denRightShift = positiveDenominator.getLowestSetBit();
        final BigInteger divisor = positiveDenominator.shiftRight(denRightShift);

        /*
         * Now, we're going to calculate the (significandLength + 2) most
         * significant bits of the fraction's value using integer division. To
         * guarantee that the quotient of the division has at least
         * (significandLength + 2) bits, the bit length of the dividend must
         * exceed that of the divisor by at least that amount.
         *
         * If the denominator has prime factors other than 2, i.e. if the
         * divisor was not reduced to 1, an excess of exactly
         * (significandLength + 2) bits is sufficient, because the knowledge
         * that the fractional part of the precise quotient's binary
         * representation does not terminate is enough information to resolve
         * cases where the most significant (significandLength + 2) bits alone
         * are not conclusive.
         *
         * Otherwise, the quotient must be calculated exactly and the bit length
         * of the numerator can only be reduced as long as no precision is lost
         * in the process (meaning it can have powers of 2 removed, like the
         * denominator).
         */
        int numRightShift = positiveNumerator.bitLength() - divisor.bitLength() - (significandLength + 2);
        if (numRightShift > 0 &&
            divisor.equals(BigInteger.ONE)) {
            numRightShift = Math.min(numRightShift, positiveNumerator.getLowestSetBit());
        }
        final BigInteger dividend = positiveNumerator.shiftRight(numRightShift);

        final BigInteger quotient = dividend.divide(divisor);

        int quotRightShift = quotient.bitLength() - (significandLength + 1);
        long significand = roundAndRightShift(
                quotient,
                quotRightShift,
                !divisor.equals(BigInteger.ONE)
        ).longValue();

        /*
         * If the significand had to be rounded up, this could have caused the
         * bit length of the significand to increase by one.
         */
        if ((significand & (1L << (significandLength + 1))) != 0) {
            significand >>= 1;
            quotRightShift++;
        }

        /*
         * Now comes the exponent. The absolute value of this fraction based on
         * the current local variables is:
         *
         * significand * 2^(numRightShift - denRightShift + quotRightShift)
         *
         * To get the unbiased exponent for the floating-point value, we need to
         * add (significandLength) to the above exponent, because all but the
         * most significant bit of the significand will be treated as a
         * fractional part. To convert the unbiased exponent to a biased
         * exponent, we also need to add the exponent bias.
         */
        final int exponentBias = (1 << (exponentLength - 1)) - 1;
        long exponent = (long) numRightShift - denRightShift + quotRightShift + significandLength + exponentBias;
        final long maxExponent = (1L << exponentLength) - 1L; //special exponent for infinities and NaN

        if (exponent >= maxExponent) { //infinity
            exponent = maxExponent;
            significand = 0L;
        } else if (exponent > 0) { //normalized number
            significand &= -1L >>> (64 - significandLength); //remove implicit leading 1-bit
        } else { //smaller than the smallest normalized number
            /*
             * We need to round the quotient to fewer than
             * (significandLength + 1) bits. This must be done with the original
             * quotient and not with the current significand, because the loss
             * of precision in the previous rounding might cause a rounding of
             * the current significand's value to produce a different result
             * than a rounding of the original quotient.
             *
             * So we find out how many high-order bits from the quotient we can
             * transfer into the significand. The absolute value of the fraction
             * is:
             *
             * quotient * 2^(numRightShift - denRightShift)
             *
             * To get the significand, we need to right shift the quotient so
             * that the above exponent becomes (1 - exponentBias - significandLength)
             * (the unbiased exponent of a subnormal floating-point number is
             * defined as equivalent to the minimum unbiased exponent of a
             * normalized floating-point number, and (- significandLength)
             * because the significand will be treated as the fractional part).
             */
            significand = roundAndRightShift(quotient,
                                             (1 - exponentBias - significandLength) - (numRightShift - denRightShift),
                                             !divisor.equals(BigInteger.ONE)).longValue();
            exponent = 0L;

            /*
             * Note: It is possible that an otherwise subnormal number will
             * round up to the smallest normal number. However, this special
             * case does not need to be treated separately, because the
             * overflowing highest-order bit of the significand will then simply
             * become the lowest-order bit of the exponent, increasing the
             * exponent from 0 to 1 and thus establishing the implicity of the
             * leading 1-bit.
             */
        }

        return (sign << (significandLength + exponentLength)) |
            (exponent << significandLength) |
            significand;
    }

    /**
     * Rounds an integer to the specified power of two (i.e. the minimum number of
     * low-order bits that must be zero) and performs a right-shift by this
     * amount. The rounding mode applied is round to nearest, with ties rounding
     * to even (meaning the prospective least significant bit must be zero). The
     * number can optionally be treated as though it contained at
     * least one 0-bit and one 1-bit in its fractional part, to influence the result in cases
     * that would otherwise be a tie.
     * @param value the number to round and right-shift
     * @param bits the power of two to which to round; must be positive
     * @param hasFractionalBits whether the number should be treated as though
     *                          it contained a non-zero fractional part
     * @return a {@code BigInteger} as described above
     * @throws IllegalArgumentException if {@code bits <= 0}
     */
    private static BigInteger roundAndRightShift(BigInteger value, int bits, boolean hasFractionalBits) {
        if (bits <= 0) {
            throw new IllegalArgumentException("bits: " + bits);
        }

        BigInteger result = value.shiftRight(bits);
        if (value.testBit(bits - 1) &&
            (hasFractionalBits ||
             (value.getLowestSetBit() < bits - 1) ||
             value.testBit(bits))) {
            result = result.add(BigInteger.ONE); //round up
        }

        return result;
    }

    /**
     * Returns true if this fraction is zero.
     *
     * @return true if zero
     */
    private boolean isZero() {
        return numerator.signum() == 0;
    }
}