001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.numbers.fraction;
018
019import java.io.Serializable;
020import org.apache.commons.numbers.core.ArithmeticUtils;
021import org.apache.commons.numbers.core.NativeOperators;
022
023/**
024 * Representation of a rational number.
025 *
026 * <p>The number is expressed as the quotient {@code p/q} of two 32-bit integers,
027 * a numerator {@code p} and a non-zero denominator {@code q}.
028 *
029 * <p>This class is immutable.
030 *
031 * <a href="https://en.wikipedia.org/wiki/Rational_number">Rational number</a>
032 */
033public final class Fraction
034    extends Number
035    implements Comparable<Fraction>,
036               NativeOperators<Fraction>,
037               Serializable {
038    /** A fraction representing "0". */
039    public static final Fraction ZERO = new Fraction(0);
040
041    /** A fraction representing "1". */
042    public static final Fraction ONE = new Fraction(1);
043
044    /** Serializable version identifier. */
045    private static final long serialVersionUID = 20190701L;
046
047    /** The default epsilon used for convergence. */
048    private static final double DEFAULT_EPSILON = 1e-5;
049
050    /** The default iterations used for convergence. */
051    private static final int DEFAULT_MAX_ITERATIONS = 100;
052
053    /** Message for non-finite input double argument to factory constructors. */
054    private static final String NOT_FINITE = "Not finite: ";
055
056    /** The overflow limit for conversion from a double (2^31). */
057    private static final long OVERFLOW = 1L << 31;
058
059    /** The numerator of this fraction reduced to lowest terms. */
060    private final int numerator;
061
062    /** The denominator of this fraction reduced to lowest terms. */
063    private final int denominator;
064
065    /**
066     * Private constructor: Instances are created using factory methods.
067     *
068     * <p>This constructor should only be invoked when the fraction is known
069     * to be non-zero; otherwise use {@link #ZERO}. This avoids creating
070     * the zero representation {@code 0 / -1}.
071     *
072     * @param num Numerator.
073     * @param den Denominator.
074     * @throws ArithmeticException if the denominator is {@code zero}.
075     */
076    private Fraction(int num, int den) {
077        if (den == 0) {
078            throw new FractionException(FractionException.ERROR_ZERO_DENOMINATOR);
079        }
080
081        if (num == den) {
082            numerator = 1;
083            denominator = 1;
084        } else {
085            // Reduce numerator (p) and denominator (q) by greatest common divisor.
086            int p;
087            int q;
088
089            // If num and den are both 2^-31, or if one is 0 and the other is 2^-31,
090            // the calculation of the gcd below will fail. Ensure that this does not
091            // happen by dividing both by 2 in case both are even.
092            if (((num | den) & 1) == 0) {
093                p = num >> 1;
094                q = den >> 1;
095            } else {
096                p = num;
097                q = den;
098            }
099
100            // Will not throw.
101            // Cannot return 0 as gcd(0, 0) has been eliminated.
102            final int d = ArithmeticUtils.gcd(p, q);
103            numerator = p / d;
104            denominator = q / d;
105        }
106    }
107
108    /**
109     * Private constructor: Instances are created using factory methods.
110     *
111     * <p>This sets the denominator to 1.
112     *
113     * @param num Numerator.
114     */
115    private Fraction(int num) {
116        numerator = num;
117        denominator = 1;
118    }
119
120    /**
121     * Create a fraction given the double value and either the maximum error
122     * allowed or the maximum number of denominator digits.
123     *
124     * <p>
125     * NOTE: This constructor is called with:
126     * <ul>
127     *  <li>EITHER a valid epsilon value and the maxDenominator set to
128     *      Integer.MAX_VALUE (that way the maxDenominator has no effect)
129     *  <li>OR a valid maxDenominator value and the epsilon value set to
130     *      zero (that way epsilon only has effect if there is an exact
131     *      match before the maxDenominator value is reached).
132     * </ul>
133     * <p>
134     * It has been done this way so that the same code can be reused for
135     * both scenarios. However this could be confusing to users if it
136     * were part of the public API and this method should therefore remain
137     * PRIVATE.
138     * </p>
139     *
140     * <p>
141     * See JIRA issue ticket MATH-181 for more details:
142     *     https://issues.apache.org/jira/browse/MATH-181
143     * </p>
144     *
145     * <p>
146     * Warning: This conversion assumes the value is not zero.
147     * </p>
148     *
149     * @param value Value to convert to a fraction. Must not be zero.
150     * @param epsilon Maximum error allowed.
151     * The resulting fraction is within {@code epsilon} of {@code value},
152     * in absolute terms.
153     * @param maxDenominator Maximum denominator value allowed.
154     * @param maxIterations Maximum number of convergents.
155     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
156     * @throws ArithmeticException if the continued fraction failed to converge.
157     */
158    private Fraction(final double value,
159                     final double epsilon,
160                     final int maxDenominator,
161                     final int maxIterations) {
162        if (!Double.isFinite(value)) {
163            throw new IllegalArgumentException(NOT_FINITE + value);
164        }
165
166        // Remove sign, this is restored at the end.
167        // (Assumes the value is not zero and thus signum(value) is not zero).
168        final double absValue = Math.abs(value);
169        double r0 = absValue;
170        long a0 = (long) Math.floor(r0);
171        if (a0 > OVERFLOW) {
172            throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, a0, 1);
173        }
174
175        // check for (almost) integer arguments, which should not go to iterations.
176        if (r0 - a0 <= epsilon) {
177            int num = (int) a0;
178            int den = 1;
179            // Restore the sign.
180            if (Math.signum(num) != Math.signum(value)) {
181                if (num == Integer.MIN_VALUE) {
182                    den = -den;
183                } else {
184                    num = -num;
185                }
186            }
187            this.numerator = num;
188            this.denominator = den;
189            return;
190        }
191
192        // Support 2^31 as maximum denominator.
193        // This is negative as an integer so convert to long.
194        final long maxDen = Math.abs((long) maxDenominator);
195
196        long p0 = 1;
197        long q0 = 0;
198        long p1 = a0;
199        long q1 = 1;
200
201        long p2 = 0;
202        long q2 = 1;
203
204        int n = 0;
205        boolean stop = false;
206        do {
207            ++n;
208            final double r1 = 1.0 / (r0 - a0);
209            final long a1 = (long) Math.floor(r1);
210            p2 = (a1 * p1) + p0;
211            q2 = (a1 * q1) + q0;
212
213            if (Long.compareUnsigned(p2, OVERFLOW) > 0 ||
214                Long.compareUnsigned(q2, OVERFLOW) > 0) {
215                // In maxDenominator mode, fall-back to the previous valid fraction.
216                if (epsilon == 0.0) {
217                    p2 = p1;
218                    q2 = q1;
219                    break;
220                }
221                throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, p2, q2);
222            }
223
224            final double convergent = (double) p2 / (double) q2;
225            if (n < maxIterations &&
226                Math.abs(convergent - absValue) > epsilon &&
227                q2 < maxDen) {
228                p0 = p1;
229                p1 = p2;
230                q0 = q1;
231                q1 = q2;
232                a0 = a1;
233                r0 = r1;
234            } else {
235                stop = true;
236            }
237        } while (!stop);
238
239        if (n >= maxIterations) {
240            throw new FractionException(FractionException.ERROR_CONVERSION, value, maxIterations);
241        }
242
243        // Use p2 / q2 or p1 / q1 if q2 has grown too large in maxDenominator mode
244        // Note: Conversion of long 2^31 to an integer will create a negative. This could
245        // be either the numerator or denominator. This is handled by restoring the sign.
246        int num;
247        int den;
248        if (q2 <= maxDen) {
249            num = (int) p2;
250            den = (int) q2;
251        } else {
252            num = (int) p1;
253            den = (int) q1;
254        }
255
256        // Restore the sign.
257        if (Math.signum(num) * Math.signum(den) != Math.signum(value)) {
258            if (num == Integer.MIN_VALUE) {
259                den = -den;
260            } else {
261                num = -num;
262            }
263        }
264
265        this.numerator = num;
266        this.denominator = den;
267    }
268
269    /**
270     * Create a fraction given the double value.
271     *
272     * @param value Value to convert to a fraction.
273     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
274     * @throws ArithmeticException if the continued fraction failed to converge.
275     * @return a new instance.
276     */
277    public static Fraction from(final double value) {
278        return from(value, DEFAULT_EPSILON, DEFAULT_MAX_ITERATIONS);
279    }
280
281    /**
282     * Create a fraction given the double value and maximum error allowed.
283     *
284     * <p>
285     * References:
286     * <ul>
287     * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
288     * Continued Fraction</a> equations (11) and (22)-(26)</li>
289     * </ul>
290     *
291     * @param value Value to convert to a fraction.
292     * @param epsilon Maximum error allowed. The resulting fraction is within
293     * {@code epsilon} of {@code value}, in absolute terms.
294     * @param maxIterations Maximum number of convergents.
295     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite;
296     * {@code epsilon} is not positive; or {@code maxIterations < 1}.
297     * @throws ArithmeticException if the continued fraction failed to converge.
298     * @return a new instance.
299     */
300    public static Fraction from(final double value,
301                                final double epsilon,
302                                final int maxIterations) {
303        if (value == 0) {
304            return ZERO;
305        }
306        if (maxIterations < 1) {
307            throw new IllegalArgumentException("Max iterations must be strictly positive: " + maxIterations);
308        }
309        if (epsilon >= 0) {
310            return new Fraction(value, epsilon, Integer.MIN_VALUE, maxIterations);
311        }
312        throw new IllegalArgumentException("Epsilon must be positive: " + maxIterations);
313    }
314
315    /**
316     * Create a fraction given the double value and maximum denominator.
317     *
318     * <p>
319     * References:
320     * <ul>
321     * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
322     * Continued Fraction</a> equations (11) and (22)-(26)</li>
323     * </ul>
324     *
325     * <p>Note: The magnitude of the {@code maxDenominator} is used allowing use of
326     * {@link Integer#MIN_VALUE} for a supported maximum denominator of 2<sup>31</sup>.
327     *
328     * @param value Value to convert to a fraction.
329     * @param maxDenominator Maximum allowed value for denominator.
330     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite
331     * or {@code maxDenominator} is zero.
332     * @throws ArithmeticException if the continued fraction failed to converge.
333     * @return a new instance.
334     */
335    public static Fraction from(final double value,
336                                final int maxDenominator) {
337        if (value == 0) {
338            return ZERO;
339        }
340        if (maxDenominator == 0) {
341            // Re-use the zero denominator message
342            throw new IllegalArgumentException(FractionException.ERROR_ZERO_DENOMINATOR);
343        }
344        return new Fraction(value, 0, maxDenominator, DEFAULT_MAX_ITERATIONS);
345    }
346
347    /**
348     * Create a fraction given the numerator. The denominator is {@code 1}.
349     *
350     * @param num Numerator.
351     * @return a new instance.
352     */
353    public static Fraction of(final int num) {
354        if (num == 0) {
355            return ZERO;
356        }
357        return new Fraction(num);
358    }
359
360    /**
361     * Create a fraction given the numerator and denominator.
362     * The fraction is reduced to lowest terms.
363     *
364     * @param num Numerator.
365     * @param den Denominator.
366     * @throws ArithmeticException if the denominator is {@code zero}.
367     * @return a new instance.
368     */
369    public static Fraction of(final int num, final int den) {
370        if (num == 0) {
371            return ZERO;
372        }
373        return new Fraction(num, den);
374    }
375
376    /**
377     * Returns a {@code Fraction} instance representing the specified string {@code s}.
378     *
379     * <p>If {@code s} is {@code null}, then a {@code NullPointerException} is thrown.
380     *
381     * <p>The string must be in a format compatible with that produced by
382     * {@link #toString() Fraction.toString()}.
383     * The format expects an integer optionally followed by a {@code '/'} character and
384     * and second integer. Leading and trailing spaces are allowed around each numeric part.
385     * Each numeric part is parsed using {@link Integer#parseInt(String)}. The parts
386     * are interpreted as the numerator and optional denominator of the fraction. If absent
387     * the denominator is assumed to be "1".
388     *
389     * <p>Examples of valid strings and the equivalent {@code Fraction} are shown below:
390     *
391     * <pre>
392     * "0"                 = Fraction.of(0)
393     * "42"                = Fraction.of(42)
394     * "0 / 1"             = Fraction.of(0, 1)
395     * "1 / 3"             = Fraction.of(1, 3)
396     * "-4 / 13"           = Fraction.of(-4, 13)</pre>
397     *
398     * <p>Note: The fraction is returned in reduced form and the numerator and denominator
399     * may not match the values in the input string. For this reason the result of
400     * {@code Fraction.parse(s).toString().equals(s)} may not be {@code true}.
401     *
402     * @param s String representation.
403     * @return an instance.
404     * @throws NullPointerException if the string is null.
405     * @throws NumberFormatException if the string does not contain a parsable fraction.
406     * @see Integer#parseInt(String)
407     * @see #toString()
408     */
409    public static Fraction parse(String s) {
410        final String stripped = s.replace(",", "");
411        final int slashLoc = stripped.indexOf('/');
412        // if no slash, parse as single number
413        if (slashLoc == -1) {
414            return of(Integer.parseInt(stripped.trim()));
415        }
416        final int num = Integer.parseInt(stripped.substring(0, slashLoc).trim());
417        final int denom = Integer.parseInt(stripped.substring(slashLoc + 1).trim());
418        return of(num, denom);
419    }
420
421    @Override
422    public Fraction zero() {
423        return ZERO;
424    }
425
426    @Override
427    public Fraction one() {
428        return ONE;
429    }
430
431    /**
432     * Access the numerator as an {@code int}.
433     *
434     * @return the numerator as an {@code int}.
435     */
436    public int getNumerator() {
437        return numerator;
438    }
439
440    /**
441     * Access the denominator as an {@code int}.
442     *
443     * @return the denominator as an {@code int}.
444     */
445    public int getDenominator() {
446        return denominator;
447    }
448
449    /**
450     * Retrieves the sign of this fraction.
451     *
452     * @return -1 if the value is strictly negative, 1 if it is strictly
453     * positive, 0 if it is 0.
454     */
455    public int signum() {
456        return Integer.signum(numerator) * Integer.signum(denominator);
457    }
458
459    /**
460     * Returns the absolute value of this fraction.
461     *
462     * @return the absolute value.
463     */
464    public Fraction abs() {
465        return signum() >= 0 ?
466            this :
467            negate();
468    }
469
470    @Override
471    public Fraction negate() {
472        return numerator == Integer.MIN_VALUE ?
473            new Fraction(numerator, -denominator) :
474            new Fraction(-numerator, denominator);
475    }
476
477    /**
478     * {@inheritDoc}
479     *
480     * <p>Raises an exception if the fraction is equal to zero.
481     *
482     * @throws ArithmeticException if the current numerator is {@code zero}
483     */
484    @Override
485    public Fraction reciprocal() {
486        return new Fraction(denominator, numerator);
487    }
488
489    /**
490     * Returns the {@code double} value closest to this fraction.
491     * This calculates the fraction as numerator divided by denominator.
492     *
493     * @return the fraction as a {@code double}.
494     */
495    @Override
496    public double doubleValue() {
497        return (double) numerator / (double) denominator;
498    }
499
500    /**
501     * Returns the {@code float} value closest to this fraction.
502     * This calculates the fraction as numerator divided by denominator.
503     *
504     * @return the fraction as a {@code float}.
505     */
506    @Override
507    public float floatValue() {
508        return (float) doubleValue();
509    }
510
511    /**
512     * Returns the whole number part of the fraction.
513     *
514     * @return the largest {@code int} value that is not larger than this fraction.
515     */
516    @Override
517    public int intValue() {
518        // Note: numerator / denominator fails for Integer.MIN_VALUE / -1.
519        // Casting the double value handles this case.
520        return (int) doubleValue();
521    }
522
523    /**
524     * Returns the whole number part of the fraction.
525     *
526     * @return the largest {@code long} value that is not larger than this fraction.
527     */
528    @Override
529    public long longValue() {
530        return (long) numerator / denominator;
531    }
532
533    /**
534     * Adds the specified {@code value} to this fraction, returning
535     * the result in reduced form.
536     *
537     * @param value Value to add.
538     * @return {@code this + value}.
539     * @throws ArithmeticException if the resulting numerator
540     * cannot be represented in an {@code int}.
541     */
542    public Fraction add(final int value) {
543        if (value == 0) {
544            return this;
545        }
546        if (isZero()) {
547            return new Fraction(value);
548        }
549        // Convert to numerator with same effective denominator
550        final long num = (long) value * denominator;
551        return of(Math.toIntExact(numerator + num), denominator);
552    }
553
554    /**
555     * Adds the specified {@code value} to this fraction, returning
556     * the result in reduced form.
557     *
558     * @param value Value to add.
559     * @return {@code this + value}.
560     * @throws ArithmeticException if the resulting numerator or denominator
561     * cannot be represented in an {@code int}.
562     */
563    @Override
564    public Fraction add(Fraction value) {
565        return addSub(value, true /* add */);
566    }
567
568    /**
569     * Subtracts the specified {@code value} from this fraction, returning
570     * the result in reduced form.
571     *
572     * @param value Value to subtract.
573     * @return {@code this - value}.
574     * @throws ArithmeticException if the resulting numerator
575     * cannot be represented in an {@code int}.
576     */
577    public Fraction subtract(final int value) {
578        if (value == 0) {
579            return this;
580        }
581        if (isZero()) {
582            // Special case for min value
583            return value == Integer.MIN_VALUE ?
584                new Fraction(Integer.MIN_VALUE, -1) :
585                new Fraction(-value);
586        }
587        // Convert to numerator with same effective denominator
588        final long num = (long) value * denominator;
589        return of(Math.toIntExact(numerator - num), denominator);
590    }
591
592    /**
593     * Subtracts the specified {@code value} from this fraction, returning
594     * the result in reduced form.
595     *
596     * @param value Value to subtract.
597     * @return {@code this - value}.
598     * @throws ArithmeticException if the resulting numerator or denominator
599     * cannot be represented in an {@code int}.
600     */
601    @Override
602    public Fraction subtract(Fraction value) {
603        return addSub(value, false /* subtract */);
604    }
605
606    /**
607     * Implements add and subtract using algorithm described in Knuth 4.5.1.
608     *
609     * @param value Fraction to add or subtract.
610     * @param isAdd Whether the operation is "add" or "subtract".
611     * @return a new instance.
612     * @throws ArithmeticException if the resulting numerator or denominator
613     * cannot be represented in an {@code int}.
614     */
615    private Fraction addSub(Fraction value, boolean isAdd) {
616        if (value.isZero()) {
617            return this;
618        }
619        // Zero is identity for addition.
620        if (isZero()) {
621            return isAdd ? value : value.negate();
622        }
623
624        /*
625         * Let the two fractions be u/u' and v/v', and d1 = gcd(u', v').
626         * First, compute t, defined as:
627         *
628         * t = u(v'/d1) +/- v(u'/d1)
629         */
630        final int d1 = ArithmeticUtils.gcd(denominator, value.denominator);
631        final long uvp = (long) numerator * (long) (value.denominator / d1);
632        final long upv = (long) value.numerator * (long) (denominator / d1);
633
634        /*
635         * The largest possible absolute value of a product of two ints is 2^62,
636         * which can only happen as a result of -2^31 * -2^31 = 2^62, so a
637         * product of -2^62 is not possible. It follows that (uvp - upv) cannot
638         * overflow, and (uvp + upv) could only overflow if uvp = upv = 2^62.
639         * But for this to happen, the terms u, v, v'/d1 and u'/d1 would all
640         * have to be -2^31, which is not possible because v'/d1 and u'/d1
641         * are necessarily coprime.
642         */
643        final long t = isAdd ? uvp + upv : uvp - upv;
644
645        /*
646         * Because u is coprime to u' and v is coprime to v', t is necessarily
647         * coprime to both v'/d1 and u'/d1. However, it might have a common
648         * factor with d1.
649         */
650        final long d2 = ArithmeticUtils.gcd(t, d1);
651        // result is (t/d2) / (u'/d1)(v'/d2)
652        return of(Math.toIntExact(t / d2),
653                  Math.multiplyExact(denominator / d1,
654                                     value.denominator / (int) d2));
655    }
656
657    /**
658     * Multiply this fraction by the passed {@code value}, returning
659     * the result in reduced form.
660     *
661     * @param value Value to multiply by.
662     * @return {@code this * value}.
663     * @throws ArithmeticException if the resulting numerator
664     * cannot be represented in an {@code int}.
665     */
666    @Override
667    public Fraction multiply(final int value) {
668        if (value == 0 || isZero()) {
669            return ZERO;
670        }
671
672        // knuth 4.5.1
673        // Make sure we don't overflow unless the result *must* overflow.
674        // (see multiply(Fraction) using value / 1 as the argument).
675        final int d2 = ArithmeticUtils.gcd(value, denominator);
676        return new Fraction(Math.multiplyExact(numerator, value / d2),
677                            denominator / d2);
678    }
679
680    /**
681     * Multiply this fraction by the passed {@code value}, returning
682     * the result in reduced form.
683     *
684     * @param value Value to multiply by.
685     * @return {@code this * value}.
686     * @throws ArithmeticException if the resulting numerator or denominator
687     * cannot be represented in an {@code int}.
688     */
689    @Override
690    public Fraction multiply(Fraction value) {
691        if (value.isZero() || isZero()) {
692            return ZERO;
693        }
694        return multiply(value.numerator, value.denominator);
695    }
696
697    /**
698     * Multiply this fraction by the passed fraction decomposed into a numerator and
699     * denominator, returning the result in reduced form.
700     *
701     * <p>This is a utility method to be used by multiply and divide. The decomposed
702     * fraction arguments and this fraction are not checked for zero.
703     *
704     * @param num Fraction numerator.
705     * @param den Fraction denominator.
706     * @return {@code this * num / den}.
707     * @throws ArithmeticException if the resulting numerator or denominator cannot
708     * be represented in an {@code int}.
709     */
710    private Fraction multiply(int num, int den) {
711        // knuth 4.5.1
712        // Make sure we don't overflow unless the result *must* overflow.
713        final int d1 = ArithmeticUtils.gcd(numerator, den);
714        final int d2 = ArithmeticUtils.gcd(num, denominator);
715        return new Fraction(Math.multiplyExact(numerator / d1, num / d2),
716                            Math.multiplyExact(denominator / d2, den / d1));
717    }
718
719    /**
720     * Divide this fraction by the passed {@code value}, returning
721     * the result in reduced form.
722     *
723     * @param value Value to divide by
724     * @return {@code this / value}.
725     * @throws ArithmeticException if the value to divide by is zero
726     * or if the resulting numerator or denominator cannot be represented
727     * by an {@code int}.
728     */
729    public Fraction divide(final int value) {
730        if (value == 0) {
731            throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
732        }
733        if (isZero()) {
734            return ZERO;
735        }
736        // Multiply by reciprocal
737
738        // knuth 4.5.1
739        // Make sure we don't overflow unless the result *must* overflow.
740        // (see multiply(Fraction) using 1 / value as the argument).
741        final int d1 = ArithmeticUtils.gcd(numerator, value);
742        return new Fraction(numerator / d1,
743                            Math.multiplyExact(denominator, value / d1));
744    }
745
746    /**
747     * Divide this fraction by the passed {@code value}, returning
748     * the result in reduced form.
749     *
750     * @param value Value to divide by
751     * @return {@code this / value}.
752     * @throws ArithmeticException if the value to divide by is zero
753     * or if the resulting numerator or denominator cannot be represented
754     * by an {@code int}.
755     */
756    @Override
757    public Fraction divide(Fraction value) {
758        if (value.isZero()) {
759            throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
760        }
761        if (isZero()) {
762            return ZERO;
763        }
764        // Multiply by reciprocal
765        return multiply(value.denominator, value.numerator);
766    }
767
768    /**
769     * Returns a {@code Fraction} whose value is
770     * <code>this<sup>exponent</sup></code>, returning the result in reduced form.
771     *
772     * @param exponent exponent to which this {@code Fraction} is to be raised.
773     * @return <code>this<sup>exponent</sup></code>.
774     * @throws ArithmeticException if the intermediate result would overflow.
775     */
776    @Override
777    public Fraction pow(final int exponent) {
778        if (exponent == 1) {
779            return this;
780        }
781        if (exponent == 0) {
782            return ONE;
783        }
784        if (isZero()) {
785            if (exponent < 0) {
786                throw new FractionException(FractionException.ERROR_ZERO_DENOMINATOR);
787            }
788            return ZERO;
789        }
790        if (exponent > 0) {
791            return new Fraction(ArithmeticUtils.pow(numerator, exponent),
792                                ArithmeticUtils.pow(denominator, exponent));
793        }
794        if (exponent == -1) {
795            return this.reciprocal();
796        }
797        if (exponent == Integer.MIN_VALUE) {
798            // MIN_VALUE can't be negated
799            return new Fraction(ArithmeticUtils.pow(denominator, Integer.MAX_VALUE) * denominator,
800                                ArithmeticUtils.pow(numerator, Integer.MAX_VALUE) * numerator);
801        }
802        return new Fraction(ArithmeticUtils.pow(denominator, -exponent),
803                            ArithmeticUtils.pow(numerator, -exponent));
804    }
805
806    /**
807     * Returns the {@code String} representing this fraction.
808     * Uses:
809     * <ul>
810     *  <li>{@code "0"} if {@code numerator} is zero.
811     *  <li>{@code "numerator"} if {@code denominator} is one.
812     *  <li>{@code "numerator / denominator"} for all other cases.
813     * </ul>
814     *
815     * @return a string representation of the fraction.
816     */
817    @Override
818    public String toString() {
819        final String str;
820        if (isZero()) {
821            str = "0";
822        } else if (denominator == 1) {
823            str = Integer.toString(numerator);
824        } else {
825            str = numerator + " / " + denominator;
826        }
827        return str;
828    }
829
830    /**
831     * Compares this object with the specified object for order using the signed magnitude.
832     *
833     * @param other {@inheritDoc}
834     * @return {@inheritDoc}
835     */
836    @Override
837    public int compareTo(Fraction other) {
838        // Compute the sign of each part
839        final int lns = Integer.signum(numerator);
840        final int lds = Integer.signum(denominator);
841        final int rns = Integer.signum(other.numerator);
842        final int rds = Integer.signum(other.denominator);
843
844        final int lhsSigNum = lns * lds;
845        final int rhsSigNum = rns * rds;
846
847        if (lhsSigNum != rhsSigNum) {
848            return (lhsSigNum > rhsSigNum) ? 1 : -1;
849        }
850        // Same sign.
851        // Avoid a multiply if both fractions are zero
852        if (lhsSigNum == 0) {
853            return 0;
854        }
855        // Compare absolute magnitude.
856        // Multiplication by the signum is equal to the absolute.
857        final long nOd = ((long) numerator) * lns * other.denominator * rds;
858        final long dOn = ((long) denominator) * lds * other.numerator * rns;
859        return Long.compare(nOd, dOn);
860    }
861
862    /**
863     * Test for equality with another object. If the other object is a {@code Fraction} then a
864     * comparison is made of the sign and magnitude; otherwise {@code false} is returned.
865     *
866     * @param other {@inheritDoc}
867     * @return {@inheritDoc}
868     */
869    @Override
870    public boolean equals(Object other) {
871        if (this == other) {
872            return true;
873        }
874
875        if (other instanceof Fraction) {
876            // Since fractions are always in lowest terms, numerators and
877            // denominators can be compared directly for equality.
878            final Fraction rhs = (Fraction) other;
879            if (signum() == rhs.signum()) {
880                return Math.abs(numerator) == Math.abs(rhs.numerator) &&
881                       Math.abs(denominator) == Math.abs(rhs.denominator);
882            }
883        }
884
885        return false;
886    }
887
888    @Override
889    public int hashCode() {
890        // Incorporate the sign and absolute values of the numerator and denominator.
891        // Equivalent to:
892        // int hash = 1;
893        // hash = 31 * hash + Math.abs(numerator);
894        // hash = 31 * hash + Math.abs(denominator);
895        // hash = hash * signum()
896        // Note: x * Integer.signum(x) == Math.abs(x).
897        final int numS = Integer.signum(numerator);
898        final int denS = Integer.signum(denominator);
899        return (31 * (31 + numerator * numS) + denominator * denS) * numS * denS;
900    }
901
902    /**
903     * Returns true if this fraction is zero.
904     *
905     * @return true if zero
906     */
907    private boolean isZero() {
908        return numerator == 0;
909    }
910}