/*
    * 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 org.apache.commons.numbers.core.ArithmeticUtils;
  import org.apache.commons.numbers.core.NativeOperators;
  
  /**
   * Representation of a rational number.
   *
   * <p>The number is expressed as the quotient {@code p/q} of two 32-bit integers,
   * 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 Fraction
      extends Number
      implements Comparable<Fraction>,
                 NativeOperators<Fraction>,
                 Serializable {
      /** A fraction representing "0". */
      public static final Fraction ZERO = new Fraction(0);
  
      /** A fraction representing "1". */
      public static final Fraction ONE = new Fraction(1);
  
      /** Serializable version identifier. */
      private static final long serialVersionUID = 20190701L;
  
      /** The default epsilon used for convergence. */
      private static final double DEFAULT_EPSILON = 1e-5;
  
      /** The default iterations used for convergence. */
      private static final int DEFAULT_MAX_ITERATIONS = 100;
  
      /** Message for non-finite input double argument to factory constructors. */
      private static final String NOT_FINITE = "Not finite: ";
  
      /** The overflow limit for conversion from a double (2^31). */
      private static final long OVERFLOW = 1L << 31;
  
      /** The numerator of this fraction reduced to lowest terms. */
      private final int numerator;
  
      /** The denominator of this fraction reduced to lowest terms. */
      private final int denominator;
  
      /**
       * Private constructor: Instances are created using factory methods.
       *
       * <p>This constructor should only be invoked when the fraction is known
       * to be non-zero; otherwise use {@link #ZERO}. This avoids creating
       * the zero representation {@code 0 / -1}.
       *
       * @param num Numerator.
       * @param den Denominator.
       * @throws ArithmeticException if the denominator is {@code zero}.
       */
      private Fraction(int num, int den) {
          if (den == 0) {
              throw new FractionException(FractionException.ERROR_ZERO_DENOMINATOR);
          }
  
          if (num == den) {
              numerator = 1;
              denominator = 1;
          } else {
              // Reduce numerator (p) and denominator (q) by greatest common divisor.
              final int p;
              final int q;
  
              // If num and den are both 2^-31, or if one is 0 and the other is 2^-31,
              // the calculation of the gcd below will fail. Ensure that this does not
              // happen by dividing both by 2 in case both are even.
              if (((num | den) & 1) == 0) {
                  p = num >> 1;
                  q = den >> 1;
              } else {
                  p = num;
                  q = den;
              }
  
             // Will not throw.
             // Cannot return 0 as gcd(0, 0) has been eliminated.
             final int d = ArithmeticUtils.gcd(p, q);
             numerator = p / d;
             denominator = q / d;
         }
     }
 
     /**
      * Private constructor: Instances are created using factory methods.
      *
      * <p>This sets the denominator to 1.
      *
      * @param num Numerator.
      */
     private Fraction(int num) {
         numerator = num;
         denominator = 1;
     }
 
     /**
      * Create a fraction given the double value and either the maximum error
      * allowed or the maximum number of denominator digits.
      *
      * <p>
      * NOTE: This constructor is called with:
      * <ul>
      *  <li>EITHER a valid epsilon value and the maxDenominator set to
      *      Integer.MAX_VALUE (that way the maxDenominator has no effect)</li>
      *  <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).</li>
      * </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>
      *
      * <p>
      * Warning: This conversion assumes the value is not zero.
      * </p>
      *
      * @param value Value to convert to a fraction. Must not be zero.
      * @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.
      * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
      * @throws ArithmeticException if the continued fraction failed to converge.
      */
     private Fraction(final double value,
                      final double epsilon,
                      final int maxDenominator,
                      final int maxIterations) {
         if (!Double.isFinite(value)) {
             throw new IllegalArgumentException(NOT_FINITE + value);
         }
 
         // Remove sign, this is restored at the end.
         // (Assumes the value is not zero and thus signum(value) is not zero).
         final double absValue = Math.abs(value);
         double r0 = absValue;
         long a0 = (long) Math.floor(r0);
         if (a0 > OVERFLOW) {
             throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, a0, 1);
         }
 
         // check for (almost) integer arguments, which should not go to iterations.
         if (r0 - a0 <= epsilon) {
             int num = (int) a0;
             int den = 1;
             // Restore the sign.
             if (Math.signum(num) != Math.signum(value)) {
                 if (num == Integer.MIN_VALUE) {
                     den = -den;
                 } else {
                     num = -num;
                 }
             }
             this.numerator = num;
             this.denominator = den;
             return;
         }
 
         // Support 2^31 as maximum denominator.
         // This is negative as an integer so convert to long.
         final long maxDen = Math.abs((long) maxDenominator);
 
         long p0 = 1;
         long q0 = 0;
         long p1 = a0;
         long q1 = 1;
 
         long p2;
         long q2;
 
         int n = 0;
         boolean stop = false;
         do {
             ++n;
             final double r1 = 1.0 / (r0 - a0);
             final long a1 = (long) Math.floor(r1);
             p2 = (a1 * p1) + p0;
             q2 = (a1 * q1) + q0;
 
             if (Long.compareUnsigned(p2, OVERFLOW) > 0 ||
                 Long.compareUnsigned(q2, OVERFLOW) > 0) {
                 // In maxDenominator mode, fall-back to the previous valid fraction.
                 if (epsilon == 0.0) {
                     p2 = p1;
                     q2 = q1;
                     break;
                 }
                 throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, p2, q2);
             }
 
             final double convergent = (double) p2 / q2;
             if (n < maxIterations &&
                 Math.abs(convergent - absValue) > epsilon &&
                 q2 < maxDen) {
                 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);
         }
 
         // Use p2 / q2 or p1 / q1 if q2 has grown too large in maxDenominator mode
         // Note: Conversion of long 2^31 to an integer will create a negative. This could
         // be either the numerator or denominator. This is handled by restoring the sign.
         int num;
         int den;
         if (q2 <= maxDen) {
             num = (int) p2;
             den = (int) q2;
         } else {
             num = (int) p1;
             den = (int) q1;
         }
 
         // Restore the sign.
         if (Math.signum(num) * Math.signum(den) != Math.signum(value)) {
             if (num == Integer.MIN_VALUE) {
                 den = -den;
             } else {
                 num = -num;
             }
         }
 
         this.numerator = num;
         this.denominator = den;
     }
 
     /**
      * Create a fraction given the double value.
      *
      * @param value Value to convert to a fraction.
      * @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 Fraction from(final double value) {
         return from(value, DEFAULT_EPSILON, DEFAULT_MAX_ITERATIONS);
     }
 
     /**
      * Create a fraction given the double value and maximum error allowed.
      *
      * <p>
      * References:
      * <ul>
      * <li><a href="https://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;
      * {@code epsilon} is not positive; or {@code maxIterations < 1}.
      * @throws ArithmeticException if the continued fraction failed to converge.
      * @return a new instance.
      */
     public static Fraction from(final double value,
                                 final double epsilon,
                                 final int maxIterations) {
         if (value == 0) {
             return ZERO;
         }
         if (maxIterations < 1) {
             throw new IllegalArgumentException("Max iterations must be strictly positive: " + maxIterations);
         }
         if (epsilon >= 0) {
             return new Fraction(value, epsilon, Integer.MIN_VALUE, maxIterations);
         }
         throw new IllegalArgumentException("Epsilon must be positive: " + maxIterations);
     }
 
     /**
      * Create a fraction given the double value and maximum denominator.
      *
      * <p>
      * References:
      * <ul>
      * <li><a href="https://mathworld.wolfram.com/ContinuedFraction.html">
      * Continued Fraction</a> equations (11) and (22)-(26)</li>
      * </ul>
      *
      * <p>Note: The magnitude of the {@code maxDenominator} is used allowing use of
      * {@link Integer#MIN_VALUE} for a supported maximum denominator of 2<sup>31</sup>.
      *
      * @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
      * or {@code maxDenominator} is zero.
      * @throws ArithmeticException if the continued fraction failed to converge.
      * @return a new instance.
      */
     public static Fraction from(final double value,
                                 final int maxDenominator) {
         if (value == 0) {
             return ZERO;
         }
         if (maxDenominator == 0) {
             // Re-use the zero denominator message
             throw new IllegalArgumentException(FractionException.ERROR_ZERO_DENOMINATOR);
         }
         return new Fraction(value, 0, maxDenominator, DEFAULT_MAX_ITERATIONS);
     }
 
     /**
      * Create a fraction given the numerator. The denominator is {@code 1}.
      *
      * @param num Numerator.
      * @return a new instance.
      */
     public static Fraction of(final int num) {
         if (num == 0) {
             return ZERO;
         }
         return new Fraction(num);
     }
 
     /**
      * Create a fraction given the numerator and denominator.
      * The fraction is reduced to lowest terms.
      *
      * @param num Numerator.
      * @param den Denominator.
      * @throws ArithmeticException if the denominator is {@code zero}.
      * @return a new instance.
      */
     public static Fraction of(final int num, final int den) {
         if (num == 0) {
             return ZERO;
         }
         return new Fraction(num, den);
     }
 
     /**
      * Returns a {@code Fraction} 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() Fraction.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 Integer#parseInt(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 Fraction} are shown below:
      *
      * <pre>
      * "0"                 = Fraction.of(0)
      * "42"                = Fraction.of(42)
      * "0 / 1"             = Fraction.of(0, 1)
      * "1 / 3"             = Fraction.of(1, 3)
      * "-4 / 13"           = Fraction.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 Fraction.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 Integer#parseInt(String)
      * @see #toString()
      */
     public static Fraction parse(String s) {
         final String stripped = s.replace(",", "");
         final int slashLoc = stripped.indexOf('/');
         // if no slash, parse as single number
         if (slashLoc == -1) {
             return of(Integer.parseInt(stripped.trim()));
         }
         final int num = Integer.parseInt(stripped.substring(0, slashLoc).trim());
         final int denom = Integer.parseInt(stripped.substring(slashLoc + 1).trim());
         return of(num, denom);
     }
 
     @Override
     public Fraction zero() {
         return ZERO;
     }
 
     /**
      * {@inheritDoc}
      *
      * @since 1.2
      */
     @Override
     public boolean isZero() {
         return numerator == 0;
     }
 
     @Override
     public Fraction one() {
         return ONE;
     }
 
     /**
      * {@inheritDoc}
      *
      * @since 1.2
      */
     @Override
     public boolean isOne() {
         return numerator == denominator;
     }
 
     /**
      * Access the numerator as an {@code int}.
      *
      * @return the numerator as an {@code int}.
      */
     public int getNumerator() {
         return numerator;
     }
 
     /**
      * Access the denominator as an {@code int}.
      *
      * @return the denominator as an {@code int}.
      */
     public int getDenominator() {
         return denominator;
     }
 
     /**
      * 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 Integer.signum(numerator) * Integer.signum(denominator);
     }
 
     /**
      * Returns the absolute value of this fraction.
      *
      * @return the absolute value.
      */
     public Fraction abs() {
         return signum() >= 0 ?
             this :
             negate();
     }
 
     @Override
     public Fraction negate() {
         return numerator == Integer.MIN_VALUE ?
             new Fraction(numerator, -denominator) :
             new Fraction(-numerator, denominator);
     }
 
     /**
      * {@inheritDoc}
      *
      * <p>Raises an exception if the fraction is equal to zero.
      *
      * @throws ArithmeticException if the current numerator is {@code zero}
      */
     @Override
     public Fraction reciprocal() {
         return new Fraction(denominator, numerator);
     }
 
     /**
      * Returns the {@code double} value closest to this fraction.
      * This calculates the fraction as numerator divided by denominator.
      *
      * @return the fraction as a {@code double}.
      */
     @Override
     public double doubleValue() {
         return numerator / (double) denominator;
     }
 
     /**
      * Returns the {@code float} value closest to this fraction.
      * This calculates the fraction as numerator divided by denominator.
      *
      * @return the fraction as a {@code float}.
      */
     @Override
     public float floatValue() {
         return (float) doubleValue();
     }
 
     /**
      * 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() {
         // Note: numerator / denominator fails for Integer.MIN_VALUE / -1.
         // Casting the double value handles this case.
         return (int) doubleValue();
     }
 
     /**
      * 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 (long) numerator / denominator;
     }
 
     /**
      * Adds the specified {@code value} to this fraction, returning
      * the result in reduced form.
      *
      * @param value Value to add.
      * @return {@code this + value}.
      * @throws ArithmeticException if the resulting numerator
      * cannot be represented in an {@code int}.
      */
     public Fraction add(final int value) {
         if (value == 0) {
             return this;
         }
         if (isZero()) {
             return new Fraction(value);
         }
         // Convert to numerator with same effective denominator
         final long num = (long) value * denominator;
         return of(Math.toIntExact(numerator + num), denominator);
     }
 
     /**
      * Adds the specified {@code value} to this fraction, returning
      * the result in reduced form.
      *
      * @param value Value to add.
      * @return {@code this + value}.
      * @throws ArithmeticException if the resulting numerator or denominator
      * cannot be represented in an {@code int}.
      */
     @Override
     public Fraction add(Fraction value) {
         return addSub(value, true /* add */);
     }
 
     /**
      * Subtracts the specified {@code value} from this fraction, returning
      * the result in reduced form.
      *
      * @param value Value to subtract.
      * @return {@code this - value}.
      * @throws ArithmeticException if the resulting numerator
      * cannot be represented in an {@code int}.
      */
     public Fraction subtract(final int value) {
         if (value == 0) {
             return this;
         }
         if (isZero()) {
             // Special case for min value
             return value == Integer.MIN_VALUE ?
                 new Fraction(Integer.MIN_VALUE, -1) :
                 new Fraction(-value);
         }
         // Convert to numerator with same effective denominator
         final long num = (long) value * denominator;
         return of(Math.toIntExact(numerator - num), denominator);
     }
 
     /**
      * Subtracts the specified {@code value} from this fraction, returning
      * the result in reduced form.
      *
      * @param value Value to subtract.
      * @return {@code this - value}.
      * @throws ArithmeticException if the resulting numerator or denominator
      * cannot be represented in an {@code int}.
      */
     @Override
     public Fraction subtract(Fraction value) {
         return addSub(value, false /* subtract */);
     }
 
     /**
      * Implements add and subtract using algorithm described in Knuth 4.5.1.
      *
      * @param value Fraction to add or subtract.
      * @param isAdd Whether the operation is "add" or "subtract".
      * @return a new instance.
      * @throws ArithmeticException if the resulting numerator or denominator
      * cannot be represented in an {@code int}.
      */
     private Fraction addSub(Fraction value, boolean isAdd) {
         if (value.isZero()) {
             return this;
         }
         // Zero is identity for addition.
         if (isZero()) {
             return isAdd ? value : value.negate();
         }
 
         /*
          * Let the two fractions be u/u' and v/v', and d1 = gcd(u', v').
          * First, compute t, defined as:
          *
          * t = u(v'/d1) +/- v(u'/d1)
          */
         final int d1 = ArithmeticUtils.gcd(denominator, value.denominator);
         final long uvp = (long) numerator * (value.denominator / d1);
         final long upv = (long) value.numerator * (denominator / d1);
 
         /*
          * The largest possible absolute value of a product of two ints is 2^62,
          * which can only happen as a result of -2^31 * -2^31 = 2^62, so a
          * product of -2^62 is not possible. It follows that (uvp - upv) cannot
          * overflow, and (uvp + upv) could only overflow if uvp = upv = 2^62.
          * But for this to happen, the terms u, v, v'/d1 and u'/d1 would all
          * have to be -2^31, which is not possible because v'/d1 and u'/d1
          * are necessarily coprime.
          */
         final long t = isAdd ? uvp + upv : uvp - upv;
 
         /*
          * Because u is coprime to u' and v is coprime to v', t is necessarily
          * coprime to both v'/d1 and u'/d1. However, it might have a common
          * factor with d1.
          */
         final long d2 = ArithmeticUtils.gcd(t, d1);
         // result is (t/d2) / (u'/d1)(v'/d2)
         return of(Math.toIntExact(t / d2),
                   Math.multiplyExact(denominator / d1,
                                      value.denominator / (int) d2));
     }
 
     /**
      * Multiply this fraction by the passed {@code value}, returning
      * the result in reduced form.
      *
      * @param value Value to multiply by.
      * @return {@code this * value}.
      * @throws ArithmeticException if the resulting numerator
      * cannot be represented in an {@code int}.
      */
     @Override
     public Fraction multiply(final int value) {
         if (value == 0 || isZero()) {
             return ZERO;
         }
 
         // knuth 4.5.1
         // Make sure we don't overflow unless the result *must* overflow.
         // (see multiply(Fraction) using value / 1 as the argument).
         final int d2 = ArithmeticUtils.gcd(value, denominator);
         return new Fraction(Math.multiplyExact(numerator, value / d2),
                             denominator / d2);
     }
 
     /**
      * Multiply this fraction by the passed {@code value}, returning
      * the result in reduced form.
      *
      * @param value Value to multiply by.
      * @return {@code this * value}.
      * @throws ArithmeticException if the resulting numerator or denominator
      * cannot be represented in an {@code int}.
      */
     @Override
     public Fraction multiply(Fraction value) {
         if (value.isZero() || isZero()) {
             return ZERO;
         }
         return multiply(value.numerator, value.denominator);
     }
 
     /**
      * Multiply this fraction by the passed fraction decomposed into a numerator and
      * denominator, returning the result in reduced form.
      *
      * <p>This is a utility method to be used by multiply and divide. The decomposed
      * fraction arguments and this fraction are not checked for zero.
      *
      * @param num Fraction numerator.
      * @param den Fraction denominator.
      * @return {@code this * num / den}.
      * @throws ArithmeticException if the resulting numerator or denominator cannot
      * be represented in an {@code int}.
      */
     private Fraction multiply(int num, int den) {
         // knuth 4.5.1
         // Make sure we don't overflow unless the result *must* overflow.
         final int d1 = ArithmeticUtils.gcd(numerator, den);
         final int d2 = ArithmeticUtils.gcd(num, denominator);
         return new Fraction(Math.multiplyExact(numerator / d1, num / d2),
                             Math.multiplyExact(denominator / d2, den / d1));
     }
 
     /**
      * 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
      * or if the resulting numerator or denominator cannot be represented
      * by an {@code int}.
      */
     public Fraction divide(final int value) {
         if (value == 0) {
             throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
         }
         if (isZero()) {
             return ZERO;
         }
         // Multiply by reciprocal
 
         // knuth 4.5.1
         // Make sure we don't overflow unless the result *must* overflow.
         // (see multiply(Fraction) using 1 / value as the argument).
         final int d1 = ArithmeticUtils.gcd(numerator, value);
         return new Fraction(numerator / d1,
                             Math.multiplyExact(denominator, value / d1));
     }
 
     /**
      * 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
      * or if the resulting numerator or denominator cannot be represented
      * by an {@code int}.
      */
     @Override
     public Fraction divide(Fraction value) {
         if (value.isZero()) {
             throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
         }
         if (isZero()) {
             return ZERO;
         }
         // Multiply by reciprocal
         return multiply(value.denominator, value.numerator);
     }
 
     /**
      * Returns a {@code Fraction} whose value is
      * <code>this<sup>exponent</sup></code>, returning the result in reduced form.
      *
      * @param exponent exponent to which this {@code Fraction} is to be raised.
      * @return <code>this<sup>exponent</sup></code>.
      * @throws ArithmeticException if the intermediate result would overflow.
      */
     @Override
     public Fraction pow(final int exponent) {
         if (exponent == 1) {
             return this;
         }
         if (exponent == 0) {
             return ONE;
         }
         if (isZero()) {
             if (exponent < 0) {
                 throw new FractionException(FractionException.ERROR_ZERO_DENOMINATOR);
             }
             return ZERO;
         }
         if (exponent > 0) {
             return new Fraction(ArithmeticUtils.pow(numerator, exponent),
                                 ArithmeticUtils.pow(denominator, exponent));
         }
         if (exponent == -1) {
             return this.reciprocal();
         }
         if (exponent == Integer.MIN_VALUE) {
             // MIN_VALUE can't be negated
             return new Fraction(ArithmeticUtils.pow(denominator, Integer.MAX_VALUE) * denominator,
                                 ArithmeticUtils.pow(numerator, Integer.MAX_VALUE) * numerator);
         }
         return new Fraction(ArithmeticUtils.pow(denominator, -exponent),
                             ArithmeticUtils.pow(numerator, -exponent));
     }
 
     /**
      * Returns the {@code String} representing this fraction.
      * Uses:
      * <ul>
      *  <li>{@code "0"} if {@code numerator} is zero.</li>
      *  <li>{@code "numerator"} if {@code denominator} is one.</li>
      *  <li>{@code "numerator / denominator"} for all other cases.</li>
      * </ul>
      *
      * @return a string representation of the fraction.
      */
     @Override
     public String toString() {
         final String str;
         if (isZero()) {
             str = "0";
         } else if (denominator == 1) {
             str = Integer.toString(numerator);
         } 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(Fraction other) {
         // Compute the sign of each part
         final int lns = Integer.signum(numerator);
         final int lds = Integer.signum(denominator);
         final int rns = Integer.signum(other.numerator);
         final int rds = Integer.signum(other.denominator);
 
         final int lhsSigNum = lns * lds;
         final int rhsSigNum = rns * rds;
 
         if (lhsSigNum != rhsSigNum) {
             return (lhsSigNum > rhsSigNum) ? 1 : -1;
         }
         // Same sign.
         // Avoid a multiply if both fractions are zero
         if (lhsSigNum == 0) {
             return 0;
         }
         // Compare absolute magnitude.
         // Multiplication by the signum is equal to the absolute.
         final long nOd = ((long) numerator) * lns * other.denominator * rds;
         final long dOn = ((long) denominator) * lds * other.numerator * rns;
         return lhsSigNum > 0 ?
             Long.compare(nOd, dOn) :
             Long.compare(dOn, nOd);
     }
 
     /**
      * 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(Object other) {
         if (this == other) {
             return true;
         }
 
         if (other instanceof Fraction) {
             // Since fractions are always in lowest terms, numerators and
             // denominators can be compared directly for equality.
             final Fraction rhs = (Fraction) other;
             if (signum() == rhs.signum()) {
                 return Math.abs(numerator) == Math.abs(rhs.numerator) &&
                        Math.abs(denominator) == Math.abs(rhs.denominator);
             }
         }
 
         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 + Math.abs(numerator);
         // hash = 31 * hash + Math.abs(denominator);
         // hash = hash * signum()
         // Note: x * Integer.signum(x) == Math.abs(x).
         final int numS = Integer.signum(numerator);
         final int denS = Integer.signum(denominator);
         return (31 * (31 + numerator * numS) + denominator * denS) * numS * denS;
     }
 }