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;
202        long q2;
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    /** {@inheritDoc} */
427    @Override
428    public boolean isZero() {
429        return numerator == 0;
430    }
431
432    @Override
433    public Fraction one() {
434        return ONE;
435    }
436
437    /** {@inheritDoc} */
438    @Override
439    public boolean isOne() {
440        return numerator == denominator;
441    }
442
443    /**
444     * Access the numerator as an {@code int}.
445     *
446     * @return the numerator as an {@code int}.
447     */
448    public int getNumerator() {
449        return numerator;
450    }
451
452    /**
453     * Access the denominator as an {@code int}.
454     *
455     * @return the denominator as an {@code int}.
456     */
457    public int getDenominator() {
458        return denominator;
459    }
460
461    /**
462     * Retrieves the sign of this fraction.
463     *
464     * @return -1 if the value is strictly negative, 1 if it is strictly
465     * positive, 0 if it is 0.
466     */
467    public int signum() {
468        return Integer.signum(numerator) * Integer.signum(denominator);
469    }
470
471    /**
472     * Returns the absolute value of this fraction.
473     *
474     * @return the absolute value.
475     */
476    public Fraction abs() {
477        return signum() >= 0 ?
478            this :
479            negate();
480    }
481
482    @Override
483    public Fraction negate() {
484        return numerator == Integer.MIN_VALUE ?
485            new Fraction(numerator, -denominator) :
486            new Fraction(-numerator, denominator);
487    }
488
489    /**
490     * {@inheritDoc}
491     *
492     * <p>Raises an exception if the fraction is equal to zero.
493     *
494     * @throws ArithmeticException if the current numerator is {@code zero}
495     */
496    @Override
497    public Fraction reciprocal() {
498        return new Fraction(denominator, numerator);
499    }
500
501    /**
502     * Returns the {@code double} value closest to this fraction.
503     * This calculates the fraction as numerator divided by denominator.
504     *
505     * @return the fraction as a {@code double}.
506     */
507    @Override
508    public double doubleValue() {
509        return (double) numerator / (double) denominator;
510    }
511
512    /**
513     * Returns the {@code float} value closest to this fraction.
514     * This calculates the fraction as numerator divided by denominator.
515     *
516     * @return the fraction as a {@code float}.
517     */
518    @Override
519    public float floatValue() {
520        return (float) doubleValue();
521    }
522
523    /**
524     * Returns the whole number part of the fraction.
525     *
526     * @return the largest {@code int} value that is not larger than this fraction.
527     */
528    @Override
529    public int intValue() {
530        // Note: numerator / denominator fails for Integer.MIN_VALUE / -1.
531        // Casting the double value handles this case.
532        return (int) doubleValue();
533    }
534
535    /**
536     * Returns the whole number part of the fraction.
537     *
538     * @return the largest {@code long} value that is not larger than this fraction.
539     */
540    @Override
541    public long longValue() {
542        return (long) numerator / denominator;
543    }
544
545    /**
546     * Adds the specified {@code value} to this fraction, returning
547     * the result in reduced form.
548     *
549     * @param value Value to add.
550     * @return {@code this + value}.
551     * @throws ArithmeticException if the resulting numerator
552     * cannot be represented in an {@code int}.
553     */
554    public Fraction add(final int value) {
555        if (value == 0) {
556            return this;
557        }
558        if (isZero()) {
559            return new Fraction(value);
560        }
561        // Convert to numerator with same effective denominator
562        final long num = (long) value * denominator;
563        return of(Math.toIntExact(numerator + num), denominator);
564    }
565
566    /**
567     * Adds the specified {@code value} to this fraction, returning
568     * the result in reduced form.
569     *
570     * @param value Value to add.
571     * @return {@code this + value}.
572     * @throws ArithmeticException if the resulting numerator or denominator
573     * cannot be represented in an {@code int}.
574     */
575    @Override
576    public Fraction add(Fraction value) {
577        return addSub(value, true /* add */);
578    }
579
580    /**
581     * Subtracts the specified {@code value} from this fraction, returning
582     * the result in reduced form.
583     *
584     * @param value Value to subtract.
585     * @return {@code this - value}.
586     * @throws ArithmeticException if the resulting numerator
587     * cannot be represented in an {@code int}.
588     */
589    public Fraction subtract(final int value) {
590        if (value == 0) {
591            return this;
592        }
593        if (isZero()) {
594            // Special case for min value
595            return value == Integer.MIN_VALUE ?
596                new Fraction(Integer.MIN_VALUE, -1) :
597                new Fraction(-value);
598        }
599        // Convert to numerator with same effective denominator
600        final long num = (long) value * denominator;
601        return of(Math.toIntExact(numerator - num), denominator);
602    }
603
604    /**
605     * Subtracts the specified {@code value} from this fraction, returning
606     * the result in reduced form.
607     *
608     * @param value Value to subtract.
609     * @return {@code this - value}.
610     * @throws ArithmeticException if the resulting numerator or denominator
611     * cannot be represented in an {@code int}.
612     */
613    @Override
614    public Fraction subtract(Fraction value) {
615        return addSub(value, false /* subtract */);
616    }
617
618    /**
619     * Implements add and subtract using algorithm described in Knuth 4.5.1.
620     *
621     * @param value Fraction to add or subtract.
622     * @param isAdd Whether the operation is "add" or "subtract".
623     * @return a new instance.
624     * @throws ArithmeticException if the resulting numerator or denominator
625     * cannot be represented in an {@code int}.
626     */
627    private Fraction addSub(Fraction value, boolean isAdd) {
628        if (value.isZero()) {
629            return this;
630        }
631        // Zero is identity for addition.
632        if (isZero()) {
633            return isAdd ? value : value.negate();
634        }
635
636        /*
637         * Let the two fractions be u/u' and v/v', and d1 = gcd(u', v').
638         * First, compute t, defined as:
639         *
640         * t = u(v'/d1) +/- v(u'/d1)
641         */
642        final int d1 = ArithmeticUtils.gcd(denominator, value.denominator);
643        final long uvp = (long) numerator * (long) (value.denominator / d1);
644        final long upv = (long) value.numerator * (long) (denominator / d1);
645
646        /*
647         * The largest possible absolute value of a product of two ints is 2^62,
648         * which can only happen as a result of -2^31 * -2^31 = 2^62, so a
649         * product of -2^62 is not possible. It follows that (uvp - upv) cannot
650         * overflow, and (uvp + upv) could only overflow if uvp = upv = 2^62.
651         * But for this to happen, the terms u, v, v'/d1 and u'/d1 would all
652         * have to be -2^31, which is not possible because v'/d1 and u'/d1
653         * are necessarily coprime.
654         */
655        final long t = isAdd ? uvp + upv : uvp - upv;
656
657        /*
658         * Because u is coprime to u' and v is coprime to v', t is necessarily
659         * coprime to both v'/d1 and u'/d1. However, it might have a common
660         * factor with d1.
661         */
662        final long d2 = ArithmeticUtils.gcd(t, d1);
663        // result is (t/d2) / (u'/d1)(v'/d2)
664        return of(Math.toIntExact(t / d2),
665                  Math.multiplyExact(denominator / d1,
666                                     value.denominator / (int) d2));
667    }
668
669    /**
670     * Multiply this fraction by the passed {@code value}, returning
671     * the result in reduced form.
672     *
673     * @param value Value to multiply by.
674     * @return {@code this * value}.
675     * @throws ArithmeticException if the resulting numerator
676     * cannot be represented in an {@code int}.
677     */
678    @Override
679    public Fraction multiply(final int value) {
680        if (value == 0 || isZero()) {
681            return ZERO;
682        }
683
684        // knuth 4.5.1
685        // Make sure we don't overflow unless the result *must* overflow.
686        // (see multiply(Fraction) using value / 1 as the argument).
687        final int d2 = ArithmeticUtils.gcd(value, denominator);
688        return new Fraction(Math.multiplyExact(numerator, value / d2),
689                            denominator / d2);
690    }
691
692    /**
693     * Multiply this fraction by the passed {@code value}, returning
694     * the result in reduced form.
695     *
696     * @param value Value to multiply by.
697     * @return {@code this * value}.
698     * @throws ArithmeticException if the resulting numerator or denominator
699     * cannot be represented in an {@code int}.
700     */
701    @Override
702    public Fraction multiply(Fraction value) {
703        if (value.isZero() || isZero()) {
704            return ZERO;
705        }
706        return multiply(value.numerator, value.denominator);
707    }
708
709    /**
710     * Multiply this fraction by the passed fraction decomposed into a numerator and
711     * denominator, returning the result in reduced form.
712     *
713     * <p>This is a utility method to be used by multiply and divide. The decomposed
714     * fraction arguments and this fraction are not checked for zero.
715     *
716     * @param num Fraction numerator.
717     * @param den Fraction denominator.
718     * @return {@code this * num / den}.
719     * @throws ArithmeticException if the resulting numerator or denominator cannot
720     * be represented in an {@code int}.
721     */
722    private Fraction multiply(int num, int den) {
723        // knuth 4.5.1
724        // Make sure we don't overflow unless the result *must* overflow.
725        final int d1 = ArithmeticUtils.gcd(numerator, den);
726        final int d2 = ArithmeticUtils.gcd(num, denominator);
727        return new Fraction(Math.multiplyExact(numerator / d1, num / d2),
728                            Math.multiplyExact(denominator / d2, den / d1));
729    }
730
731    /**
732     * Divide this fraction by the passed {@code value}, returning
733     * the result in reduced form.
734     *
735     * @param value Value to divide by
736     * @return {@code this / value}.
737     * @throws ArithmeticException if the value to divide by is zero
738     * or if the resulting numerator or denominator cannot be represented
739     * by an {@code int}.
740     */
741    public Fraction divide(final int value) {
742        if (value == 0) {
743            throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
744        }
745        if (isZero()) {
746            return ZERO;
747        }
748        // Multiply by reciprocal
749
750        // knuth 4.5.1
751        // Make sure we don't overflow unless the result *must* overflow.
752        // (see multiply(Fraction) using 1 / value as the argument).
753        final int d1 = ArithmeticUtils.gcd(numerator, value);
754        return new Fraction(numerator / d1,
755                            Math.multiplyExact(denominator, value / d1));
756    }
757
758    /**
759     * Divide this fraction by the passed {@code value}, returning
760     * the result in reduced form.
761     *
762     * @param value Value to divide by
763     * @return {@code this / value}.
764     * @throws ArithmeticException if the value to divide by is zero
765     * or if the resulting numerator or denominator cannot be represented
766     * by an {@code int}.
767     */
768    @Override
769    public Fraction divide(Fraction value) {
770        if (value.isZero()) {
771            throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
772        }
773        if (isZero()) {
774            return ZERO;
775        }
776        // Multiply by reciprocal
777        return multiply(value.denominator, value.numerator);
778    }
779
780    /**
781     * Returns a {@code Fraction} whose value is
782     * <code>this<sup>exponent</sup></code>, returning the result in reduced form.
783     *
784     * @param exponent exponent to which this {@code Fraction} is to be raised.
785     * @return <code>this<sup>exponent</sup></code>.
786     * @throws ArithmeticException if the intermediate result would overflow.
787     */
788    @Override
789    public Fraction pow(final int exponent) {
790        if (exponent == 1) {
791            return this;
792        }
793        if (exponent == 0) {
794            return ONE;
795        }
796        if (isZero()) {
797            if (exponent < 0) {
798                throw new FractionException(FractionException.ERROR_ZERO_DENOMINATOR);
799            }
800            return ZERO;
801        }
802        if (exponent > 0) {
803            return new Fraction(ArithmeticUtils.pow(numerator, exponent),
804                                ArithmeticUtils.pow(denominator, exponent));
805        }
806        if (exponent == -1) {
807            return this.reciprocal();
808        }
809        if (exponent == Integer.MIN_VALUE) {
810            // MIN_VALUE can't be negated
811            return new Fraction(ArithmeticUtils.pow(denominator, Integer.MAX_VALUE) * denominator,
812                                ArithmeticUtils.pow(numerator, Integer.MAX_VALUE) * numerator);
813        }
814        return new Fraction(ArithmeticUtils.pow(denominator, -exponent),
815                            ArithmeticUtils.pow(numerator, -exponent));
816    }
817
818    /**
819     * Returns the {@code String} representing this fraction.
820     * Uses:
821     * <ul>
822     *  <li>{@code "0"} if {@code numerator} is zero.
823     *  <li>{@code "numerator"} if {@code denominator} is one.
824     *  <li>{@code "numerator / denominator"} for all other cases.
825     * </ul>
826     *
827     * @return a string representation of the fraction.
828     */
829    @Override
830    public String toString() {
831        final String str;
832        if (isZero()) {
833            str = "0";
834        } else if (denominator == 1) {
835            str = Integer.toString(numerator);
836        } else {
837            str = numerator + " / " + denominator;
838        }
839        return str;
840    }
841
842    /**
843     * Compares this object with the specified object for order using the signed magnitude.
844     *
845     * @param other {@inheritDoc}
846     * @return {@inheritDoc}
847     */
848    @Override
849    public int compareTo(Fraction other) {
850        // Compute the sign of each part
851        final int lns = Integer.signum(numerator);
852        final int lds = Integer.signum(denominator);
853        final int rns = Integer.signum(other.numerator);
854        final int rds = Integer.signum(other.denominator);
855
856        final int lhsSigNum = lns * lds;
857        final int rhsSigNum = rns * rds;
858
859        if (lhsSigNum != rhsSigNum) {
860            return (lhsSigNum > rhsSigNum) ? 1 : -1;
861        }
862        // Same sign.
863        // Avoid a multiply if both fractions are zero
864        if (lhsSigNum == 0) {
865            return 0;
866        }
867        // Compare absolute magnitude.
868        // Multiplication by the signum is equal to the absolute.
869        final long nOd = ((long) numerator) * lns * other.denominator * rds;
870        final long dOn = ((long) denominator) * lds * other.numerator * rns;
871        return Long.compare(nOd, dOn);
872    }
873
874    /**
875     * Test for equality with another object. If the other object is a {@code Fraction} then a
876     * comparison is made of the sign and magnitude; otherwise {@code false} is returned.
877     *
878     * @param other {@inheritDoc}
879     * @return {@inheritDoc}
880     */
881    @Override
882    public boolean equals(Object other) {
883        if (this == other) {
884            return true;
885        }
886
887        if (other instanceof Fraction) {
888            // Since fractions are always in lowest terms, numerators and
889            // denominators can be compared directly for equality.
890            final Fraction rhs = (Fraction) other;
891            if (signum() == rhs.signum()) {
892                return Math.abs(numerator) == Math.abs(rhs.numerator) &&
893                       Math.abs(denominator) == Math.abs(rhs.denominator);
894            }
895        }
896
897        return false;
898    }
899
900    @Override
901    public int hashCode() {
902        // Incorporate the sign and absolute values of the numerator and denominator.
903        // Equivalent to:
904        // int hash = 1;
905        // hash = 31 * hash + Math.abs(numerator);
906        // hash = 31 * hash + Math.abs(denominator);
907        // hash = hash * signum()
908        // Note: x * Integer.signum(x) == Math.abs(x).
909        final int numS = Integer.signum(numerator);
910        final int denS = Integer.signum(denominator);
911        return (31 * (31 + numerator * numS) + denominator * denS) * numS * denS;
912    }
913}