Source code

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