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.lang3.math;
018
019import java.math.BigInteger;
020import java.util.Objects;
021
022/**
023 * {@link Fraction} is a {@link Number} implementation that
024 * stores fractions accurately.
025 *
026 * <p>This class is immutable, and interoperable with most methods that accept
027 * a {@link Number}.</p>
028 *
029 * <p>Note that this class is intended for common use cases, it is <i>int</i>
030 * based and thus suffers from various overflow issues. For a BigInteger based
031 * equivalent, please see the Commons Math BigFraction class.</p>
032 *
033 * @since 2.0
034 */
035public final class Fraction extends Number implements Comparable<Fraction> {
036
037    /**
038     * Required for serialization support. Lang version 2.0.
039     *
040     * @see java.io.Serializable
041     */
042    private static final long serialVersionUID = 65382027393090L;
043
044    /**
045     * {@link Fraction} representation of 0.
046     */
047    public static final Fraction ZERO = new Fraction(0, 1);
048    /**
049     * {@link Fraction} representation of 1.
050     */
051    public static final Fraction ONE = new Fraction(1, 1);
052    /**
053     * {@link Fraction} representation of 1/2.
054     */
055    public static final Fraction ONE_HALF = new Fraction(1, 2);
056    /**
057     * {@link Fraction} representation of 1/3.
058     */
059    public static final Fraction ONE_THIRD = new Fraction(1, 3);
060    /**
061     * {@link Fraction} representation of 2/3.
062     */
063    public static final Fraction TWO_THIRDS = new Fraction(2, 3);
064    /**
065     * {@link Fraction} representation of 1/4.
066     */
067    public static final Fraction ONE_QUARTER = new Fraction(1, 4);
068    /**
069     * {@link Fraction} representation of 2/4.
070     */
071    public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
072    /**
073     * {@link Fraction} representation of 3/4.
074     */
075    public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
076    /**
077     * {@link Fraction} representation of 1/5.
078     */
079    public static final Fraction ONE_FIFTH = new Fraction(1, 5);
080    /**
081     * {@link Fraction} representation of 2/5.
082     */
083    public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
084    /**
085     * {@link Fraction} representation of 3/5.
086     */
087    public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
088    /**
089     * {@link Fraction} representation of 4/5.
090     */
091    public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
092
093
094    /**
095     * The numerator number part of the fraction (the three in three sevenths).
096     */
097    private final int numerator;
098    /**
099     * The denominator number part of the fraction (the seven in three sevenths).
100     */
101    private final int denominator;
102
103    /**
104     * Cached output hashCode (class is immutable).
105     */
106    private transient int hashCode;
107    /**
108     * Cached output toString (class is immutable).
109     */
110    private transient String toString;
111    /**
112     * Cached output toProperString (class is immutable).
113     */
114    private transient String toProperString;
115
116    /**
117     * Constructs a {@link Fraction} instance with the 2 parts
118     * of a fraction Y/Z.
119     *
120     * @param numerator  the numerator, for example the three in 'three sevenths'
121     * @param denominator  the denominator, for example the seven in 'three sevenths'
122     */
123    private Fraction(final int numerator, final int denominator) {
124        this.numerator = numerator;
125        this.denominator = denominator;
126    }
127
128    /**
129     * Creates a {@link Fraction} instance with the 2 parts
130     * of a fraction Y/Z.
131     *
132     * <p>Any negative signs are resolved to be on the numerator.</p>
133     *
134     * @param numerator  the numerator, for example the three in 'three sevenths'
135     * @param denominator  the denominator, for example the seven in 'three sevenths'
136     * @return a new fraction instance
137     * @throws ArithmeticException if the denominator is {@code zero}
138     * or the denominator is {@code negative} and the numerator is {@code Integer#MIN_VALUE}
139     */
140    public static Fraction getFraction(int numerator, int denominator) {
141        if (denominator == 0) {
142            throw new ArithmeticException("The denominator must not be zero");
143        }
144        if (denominator < 0) {
145            if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) {
146                throw new ArithmeticException("overflow: can't negate");
147            }
148            numerator = -numerator;
149            denominator = -denominator;
150        }
151        return new Fraction(numerator, denominator);
152    }
153
154    /**
155     * Creates a {@link Fraction} instance with the 3 parts
156     * of a fraction X Y/Z.
157     *
158     * <p>The negative sign must be passed in on the whole number part.</p>
159     *
160     * @param whole  the whole number, for example the one in 'one and three sevenths'
161     * @param numerator  the numerator, for example the three in 'one and three sevenths'
162     * @param denominator  the denominator, for example the seven in 'one and three sevenths'
163     * @return a new fraction instance
164     * @throws ArithmeticException if the denominator is {@code zero}
165     * @throws ArithmeticException if the denominator is negative
166     * @throws ArithmeticException if the numerator is negative
167     * @throws ArithmeticException if the resulting numerator exceeds
168     *  {@code Integer.MAX_VALUE}
169     */
170    public static Fraction getFraction(final int whole, final int numerator, final int denominator) {
171        if (denominator == 0) {
172            throw new ArithmeticException("The denominator must not be zero");
173        }
174        if (denominator < 0) {
175            throw new ArithmeticException("The denominator must not be negative");
176        }
177        if (numerator < 0) {
178            throw new ArithmeticException("The numerator must not be negative");
179        }
180        final long numeratorValue;
181        if (whole < 0) {
182            numeratorValue = whole * (long) denominator - numerator;
183        } else {
184            numeratorValue = whole * (long) denominator + numerator;
185        }
186        if (numeratorValue < Integer.MIN_VALUE || numeratorValue > Integer.MAX_VALUE) {
187            throw new ArithmeticException("Numerator too large to represent as an Integer.");
188        }
189        return new Fraction((int) numeratorValue, denominator);
190    }
191
192    /**
193     * Creates a reduced {@link Fraction} instance with the 2 parts
194     * of a fraction Y/Z.
195     *
196     * <p>For example, if the input parameters represent 2/4, then the created
197     * fraction will be 1/2.</p>
198     *
199     * <p>Any negative signs are resolved to be on the numerator.</p>
200     *
201     * @param numerator  the numerator, for example the three in 'three sevenths'
202     * @param denominator  the denominator, for example the seven in 'three sevenths'
203     * @return a new fraction instance, with the numerator and denominator reduced
204     * @throws ArithmeticException if the denominator is {@code zero}
205     */
206    public static Fraction getReducedFraction(int numerator, int denominator) {
207        if (denominator == 0) {
208            throw new ArithmeticException("The denominator must not be zero");
209        }
210        if (numerator == 0) {
211            return ZERO; // normalize zero.
212        }
213        // allow 2^k/-2^31 as a valid fraction (where k>0)
214        if (denominator == Integer.MIN_VALUE && (numerator & 1) == 0) {
215            numerator /= 2;
216            denominator /= 2;
217        }
218        if (denominator < 0) {
219            if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) {
220                throw new ArithmeticException("overflow: can't negate");
221            }
222            numerator = -numerator;
223            denominator = -denominator;
224        }
225        // simplify fraction.
226        final int gcd = greatestCommonDivisor(numerator, denominator);
227        numerator /= gcd;
228        denominator /= gcd;
229        return new Fraction(numerator, denominator);
230    }
231
232    /**
233     * Creates a {@link Fraction} instance from a {@code double} value.
234     *
235     * <p>This method uses the <a href="https://web.archive.org/web/20210516065058/http%3A//archives.math.utk.edu/articles/atuyl/confrac/">
236     *  continued fraction algorithm</a>, computing a maximum of
237     *  25 convergents and bounding the denominator by 10,000.</p>
238     *
239     * @param value  the double value to convert
240     * @return a new fraction instance that is close to the value
241     * @throws ArithmeticException if {@code |value| &gt; Integer.MAX_VALUE}
242     *  or {@code value = NaN}
243     * @throws ArithmeticException if the calculated denominator is {@code zero}
244     * @throws ArithmeticException if the algorithm does not converge
245     */
246    public static Fraction getFraction(double value) {
247        final int sign = value < 0 ? -1 : 1;
248        value = Math.abs(value);
249        if (value > Integer.MAX_VALUE || Double.isNaN(value)) {
250            throw new ArithmeticException("The value must not be greater than Integer.MAX_VALUE or NaN");
251        }
252        final int wholeNumber = (int) value;
253        value -= wholeNumber;
254
255        int numer0 = 0; // the pre-previous
256        int denom0 = 1; // the pre-previous
257        int numer1 = 1; // the previous
258        int denom1 = 0; // the previous
259        int numer2; // the current, setup in calculation
260        int denom2; // the current, setup in calculation
261        int a1 = (int) value;
262        int a2;
263        double x1 = 1;
264        double x2;
265        double y1 = value - a1;
266        double y2;
267        double delta1, delta2 = Double.MAX_VALUE;
268        double fraction;
269        int i = 1;
270        do {
271            delta1 = delta2;
272            a2 = (int) (x1 / y1);
273            x2 = y1;
274            y2 = x1 - a2 * y1;
275            numer2 = a1 * numer1 + numer0;
276            denom2 = a1 * denom1 + denom0;
277            fraction = (double) numer2 / (double) denom2;
278            delta2 = Math.abs(value - fraction);
279            a1 = a2;
280            x1 = x2;
281            y1 = y2;
282            numer0 = numer1;
283            denom0 = denom1;
284            numer1 = numer2;
285            denom1 = denom2;
286            i++;
287        } while (delta1 > delta2 && denom2 <= 10000 && denom2 > 0 && i < 25);
288        if (i == 25) {
289            throw new ArithmeticException("Unable to convert double to fraction");
290        }
291        return getReducedFraction((numer0 + wholeNumber * denom0) * sign, denom0);
292    }
293
294    /**
295     * Creates a Fraction from a {@link String}.
296     *
297     * <p>The formats accepted are:</p>
298     *
299     * <ol>
300     *  <li>{@code double} String containing a dot</li>
301     *  <li>'X Y/Z'</li>
302     *  <li>'Y/Z'</li>
303     *  <li>'X' (a simple whole number)</li>
304     * </ol>
305     * <p>and a .</p>
306     *
307     * @param str  the string to parse, must not be {@code null}
308     * @return the new {@link Fraction} instance
309     * @throws NullPointerException if the string is {@code null}
310     * @throws NumberFormatException if the number format is invalid
311     */
312    public static Fraction getFraction(String str) {
313        Objects.requireNonNull(str, "str");
314        // parse double format
315        int pos = str.indexOf('.');
316        if (pos >= 0) {
317            return getFraction(Double.parseDouble(str));
318        }
319
320        // parse X Y/Z format
321        pos = str.indexOf(' ');
322        if (pos > 0) {
323            final int whole = Integer.parseInt(str.substring(0, pos));
324            str = str.substring(pos + 1);
325            pos = str.indexOf('/');
326            if (pos < 0) {
327                throw new NumberFormatException("The fraction could not be parsed as the format X Y/Z");
328            }
329            final int numer = Integer.parseInt(str.substring(0, pos));
330            final int denom = Integer.parseInt(str.substring(pos + 1));
331            return getFraction(whole, numer, denom);
332        }
333
334        // parse Y/Z format
335        pos = str.indexOf('/');
336        if (pos < 0) {
337            // simple whole number
338            return getFraction(Integer.parseInt(str), 1);
339        }
340        final int numer = Integer.parseInt(str.substring(0, pos));
341        final int denom = Integer.parseInt(str.substring(pos + 1));
342        return getFraction(numer, denom);
343    }
344
345    /**
346     * Gets the numerator part of the fraction.
347     *
348     * <p>This method may return a value greater than the denominator, an
349     * improper fraction, such as the seven in 7/4.</p>
350     *
351     * @return the numerator fraction part
352     */
353    public int getNumerator() {
354        return numerator;
355    }
356
357    /**
358     * Gets the denominator part of the fraction.
359     *
360     * @return the denominator fraction part
361     */
362    public int getDenominator() {
363        return denominator;
364    }
365
366    /**
367     * Gets the proper numerator, always positive.
368     *
369     * <p>An improper fraction 7/4 can be resolved into a proper one, 1 3/4.
370     * This method returns the 3 from the proper fraction.</p>
371     *
372     * <p>If the fraction is negative such as -7/4, it can be resolved into
373     * -1 3/4, so this method returns the positive proper numerator, 3.</p>
374     *
375     * @return the numerator fraction part of a proper fraction, always positive
376     */
377    public int getProperNumerator() {
378        return Math.abs(numerator % denominator);
379    }
380
381    /**
382     * Gets the proper whole part of the fraction.
383     *
384     * <p>An improper fraction 7/4 can be resolved into a proper one, 1 3/4.
385     * This method returns the 1 from the proper fraction.</p>
386     *
387     * <p>If the fraction is negative such as -7/4, it can be resolved into
388     * -1 3/4, so this method returns the positive whole part -1.</p>
389     *
390     * @return the whole fraction part of a proper fraction, that includes the sign
391     */
392    public int getProperWhole() {
393        return numerator / denominator;
394    }
395
396    /**
397     * Gets the fraction as an {@code int}. This returns the whole number
398     * part of the fraction.
399     *
400     * @return the whole number fraction part
401     */
402    @Override
403    public int intValue() {
404        return numerator / denominator;
405    }
406
407    /**
408     * Gets the fraction as a {@code long}. This returns the whole number
409     * part of the fraction.
410     *
411     * @return the whole number fraction part
412     */
413    @Override
414    public long longValue() {
415        return (long) numerator / denominator;
416    }
417
418    /**
419     * Gets the fraction as a {@code float}. This calculates the fraction
420     * as the numerator divided by denominator.
421     *
422     * @return the fraction as a {@code float}
423     */
424    @Override
425    public float floatValue() {
426        return (float) numerator / (float) denominator;
427    }
428
429    /**
430     * Gets the fraction as a {@code double}. This calculates the fraction
431     * as the numerator divided by denominator.
432     *
433     * @return the fraction as a {@code double}
434     */
435    @Override
436    public double doubleValue() {
437        return (double) numerator / (double) denominator;
438    }
439
440    /**
441     * Reduce the fraction to the smallest values for the numerator and
442     * denominator, returning the result.
443     *
444     * <p>For example, if this fraction represents 2/4, then the result
445     * will be 1/2.</p>
446     *
447     * @return a new reduced fraction instance, or this if no simplification possible
448     */
449    public Fraction reduce() {
450        if (numerator == 0) {
451            return equals(ZERO) ? this : ZERO;
452        }
453        final int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
454        if (gcd == 1) {
455            return this;
456        }
457        return getFraction(numerator / gcd, denominator / gcd);
458    }
459
460    /**
461     * Gets a fraction that is the inverse (1/fraction) of this one.
462     *
463     * <p>The returned fraction is not reduced.</p>
464     *
465     * @return a new fraction instance with the numerator and denominator
466     *         inverted.
467     * @throws ArithmeticException if the fraction represents zero.
468     */
469    public Fraction invert() {
470        if (numerator == 0) {
471            throw new ArithmeticException("Unable to invert zero.");
472        }
473        if (numerator==Integer.MIN_VALUE) {
474            throw new ArithmeticException("overflow: can't negate numerator");
475        }
476        if (numerator<0) {
477            return new Fraction(-denominator, -numerator);
478        }
479        return new Fraction(denominator, numerator);
480    }
481
482    /**
483     * Gets a fraction that is the negative (-fraction) of this one.
484     *
485     * <p>The returned fraction is not reduced.</p>
486     *
487     * @return a new fraction instance with the opposite signed numerator
488     */
489    public Fraction negate() {
490        // the positive range is one smaller than the negative range of an int.
491        if (numerator==Integer.MIN_VALUE) {
492            throw new ArithmeticException("overflow: too large to negate");
493        }
494        return new Fraction(-numerator, denominator);
495    }
496
497    /**
498     * Gets a fraction that is the positive equivalent of this one.
499     * <p>More precisely: {@code (fraction &gt;= 0 ? this : -fraction)}</p>
500     *
501     * <p>The returned fraction is not reduced.</p>
502     *
503     * @return {@code this} if it is positive, or a new positive fraction
504     *  instance with the opposite signed numerator
505     */
506    public Fraction abs() {
507        if (numerator >= 0) {
508            return this;
509        }
510        return negate();
511    }
512
513    /**
514     * Gets a fraction that is raised to the passed in power.
515     *
516     * <p>The returned fraction is in reduced form.</p>
517     *
518     * @param power  the power to raise the fraction to
519     * @return {@code this} if the power is one, {@link #ONE} if the power
520     * is zero (even if the fraction equals ZERO) or a new fraction instance
521     * raised to the appropriate power
522     * @throws ArithmeticException if the resulting numerator or denominator exceeds
523     *  {@code Integer.MAX_VALUE}
524     */
525    public Fraction pow(final int power) {
526        if (power == 1) {
527            return this;
528        }
529        if (power == 0) {
530            return ONE;
531        }
532        if (power < 0) {
533            if (power == Integer.MIN_VALUE) { // MIN_VALUE can't be negated.
534                return this.invert().pow(2).pow(-(power / 2));
535            }
536            return this.invert().pow(-power);
537        }
538        final Fraction f = this.multiplyBy(this);
539        if (power % 2 == 0) { // if even...
540            return f.pow(power / 2);
541        }
542        return f.pow(power / 2).multiplyBy(this);
543    }
544
545    /**
546     * Gets the greatest common divisor of the absolute value of
547     * two numbers, using the "binary gcd" method which avoids
548     * division and modulo operations.  See Knuth 4.5.2 algorithm B.
549     * This algorithm is due to Josef Stein (1961).
550     *
551     * @param u  a non-zero number
552     * @param v  a non-zero number
553     * @return the greatest common divisor, never zero
554     */
555    private static int greatestCommonDivisor(int u, int v) {
556        // From Commons Math:
557        if (u == 0 || v == 0) {
558            if (u == Integer.MIN_VALUE || v == Integer.MIN_VALUE) {
559                throw new ArithmeticException("overflow: gcd is 2^31");
560            }
561            return Math.abs(u) + Math.abs(v);
562        }
563        // if either operand is abs 1, return 1:
564        if (Math.abs(u) == 1 || Math.abs(v) == 1) {
565            return 1;
566        }
567        // keep u and v negative, as negative integers range down to
568        // -2^31, while positive numbers can only be as large as 2^31-1
569        // (i.e. we can't necessarily negate a negative number without
570        // overflow)
571        if (u > 0) {
572            u = -u;
573        } // make u negative
574        if (v > 0) {
575            v = -v;
576        } // make v negative
577        // B1. [Find power of 2]
578        int k = 0;
579        while ((u & 1) == 0 && (v & 1) == 0 && k < 31) { // while u and v are both even...
580            u /= 2;
581            v /= 2;
582            k++; // cast out twos.
583        }
584        if (k == 31) {
585            throw new ArithmeticException("overflow: gcd is 2^31");
586        }
587        // B2. Initialize: u and v have been divided by 2^k and at least
588        // one is odd.
589        int t = (u & 1) == 1 ? v : -(u / 2)/* B3 */;
590        // t negative: u was odd, v may be even (t replaces v)
591        // t positive: u was even, v is odd (t replaces u)
592        do {
593            /* assert u<0 && v<0; */
594            // B4/B3: cast out twos from t.
595            while ((t & 1) == 0) { // while t is even.
596                t /= 2; // cast out twos
597            }
598            // B5 [reset max(u,v)]
599            if (t > 0) {
600                u = -t;
601            } else {
602                v = t;
603            }
604            // B6/B3. at this point both u and v should be odd.
605            t = (v - u) / 2;
606            // |u| larger: t positive (replace u)
607            // |v| larger: t negative (replace v)
608        } while (t != 0);
609        return -u * (1 << k); // gcd is u*2^k
610    }
611
612    /**
613     * Multiply two integers, checking for overflow.
614     *
615     * @param x a factor
616     * @param y a factor
617     * @return the product {@code x*y}
618     * @throws ArithmeticException if the result can not be represented as
619     *                             an int
620     */
621    private static int mulAndCheck(final int x, final int y) {
622        final long m = (long) x * (long) y;
623        if (m < Integer.MIN_VALUE || m > Integer.MAX_VALUE) {
624            throw new ArithmeticException("overflow: mul");
625        }
626        return (int) m;
627    }
628
629    /**
630     *  Multiply two non-negative integers, checking for overflow.
631     *
632     * @param x a non-negative factor
633     * @param y a non-negative factor
634     * @return the product {@code x*y}
635     * @throws ArithmeticException if the result can not be represented as
636     * an int
637     */
638    private static int mulPosAndCheck(final int x, final int y) {
639        /* assert x>=0 && y>=0; */
640        final long m = (long) x * (long) y;
641        if (m > Integer.MAX_VALUE) {
642            throw new ArithmeticException("overflow: mulPos");
643        }
644        return (int) m;
645    }
646
647    /**
648     * Add two integers, checking for overflow.
649     *
650     * @param x an addend
651     * @param y an addend
652     * @return the sum {@code x+y}
653     * @throws ArithmeticException if the result can not be represented as
654     * an int
655     */
656    private static int addAndCheck(final int x, final int y) {
657        final long s = (long) x + (long) y;
658        if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
659            throw new ArithmeticException("overflow: add");
660        }
661        return (int) s;
662    }
663
664    /**
665     * Subtract two integers, checking for overflow.
666     *
667     * @param x the minuend
668     * @param y the subtrahend
669     * @return the difference {@code x-y}
670     * @throws ArithmeticException if the result can not be represented as
671     * an int
672     */
673    private static int subAndCheck(final int x, final int y) {
674        final long s = (long) x - (long) y;
675        if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
676            throw new ArithmeticException("overflow: add");
677        }
678        return (int) s;
679    }
680
681    /**
682     * Adds the value of this fraction to another, returning the result in reduced form.
683     * The algorithm follows Knuth, 4.5.1.
684     *
685     * @param fraction  the fraction to add, must not be {@code null}
686     * @return a {@link Fraction} instance with the resulting values
687     * @throws NullPointerException if the fraction is {@code null}
688     * @throws ArithmeticException if the resulting numerator or denominator exceeds
689     *  {@code Integer.MAX_VALUE}
690     */
691    public Fraction add(final Fraction fraction) {
692        return addSub(fraction, true /* add */);
693    }
694
695    /**
696     * Subtracts the value of another fraction from the value of this one,
697     * returning the result in reduced form.
698     *
699     * @param fraction  the fraction to subtract, must not be {@code null}
700     * @return a {@link Fraction} instance with the resulting values
701     * @throws NullPointerException if the fraction is {@code null}
702     * @throws ArithmeticException if the resulting numerator or denominator
703     *   cannot be represented in an {@code int}.
704     */
705    public Fraction subtract(final Fraction fraction) {
706        return addSub(fraction, false /* subtract */);
707    }
708
709    /**
710     * Implement add and subtract using algorithm described in Knuth 4.5.1.
711     *
712     * @param fraction the fraction to subtract, must not be {@code null}
713     * @param isAdd true to add, false to subtract
714     * @return a {@link Fraction} instance with the resulting values
715     * @throws IllegalArgumentException if the fraction is {@code null}
716     * @throws ArithmeticException if the resulting numerator or denominator
717     *   cannot be represented in an {@code int}.
718     */
719    private Fraction addSub(final Fraction fraction, final boolean isAdd) {
720        Objects.requireNonNull(fraction, "fraction");
721        // zero is identity for addition.
722        if (numerator == 0) {
723            return isAdd ? fraction : fraction.negate();
724        }
725        if (fraction.numerator == 0) {
726            return this;
727        }
728        // if denominators are randomly distributed, d1 will be 1 about 61%
729        // of the time.
730        final int d1 = greatestCommonDivisor(denominator, fraction.denominator);
731        if (d1 == 1) {
732            // result is ( (u*v' +/- u'v) / u'v')
733            final int uvp = mulAndCheck(numerator, fraction.denominator);
734            final int upv = mulAndCheck(fraction.numerator, denominator);
735            return new Fraction(isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv), mulPosAndCheck(denominator,
736                    fraction.denominator));
737        }
738        // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
739        // exercise 7. we're going to use a BigInteger.
740        // t = u(v'/d1) +/- v(u'/d1)
741        final BigInteger uvp = BigInteger.valueOf(numerator).multiply(BigInteger.valueOf(fraction.denominator / d1));
742        final BigInteger upv = BigInteger.valueOf(fraction.numerator).multiply(BigInteger.valueOf(denominator / d1));
743        final BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
744        // but d2 doesn't need extra precision because
745        // d2 = gcd(t,d1) = gcd(t mod d1, d1)
746        final int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
747        final int d2 = tmodd1 == 0 ? d1 : greatestCommonDivisor(tmodd1, d1);
748
749        // result is (t/d2) / (u'/d1)(v'/d2)
750        final BigInteger w = t.divide(BigInteger.valueOf(d2));
751        if (w.bitLength() > 31) {
752            throw new ArithmeticException("overflow: numerator too large after multiply");
753        }
754        return new Fraction(w.intValue(), mulPosAndCheck(denominator / d1, fraction.denominator / d2));
755    }
756
757    /**
758     * Multiplies the value of this fraction by another, returning the
759     * result in reduced form.
760     *
761     * @param fraction  the fraction to multiply by, must not be {@code null}
762     * @return a {@link Fraction} instance with the resulting values
763     * @throws NullPointerException if the fraction is {@code null}
764     * @throws ArithmeticException if the resulting numerator or denominator exceeds
765     *  {@code Integer.MAX_VALUE}
766     */
767    public Fraction multiplyBy(final Fraction fraction) {
768        Objects.requireNonNull(fraction, "fraction");
769        if (numerator == 0 || fraction.numerator == 0) {
770            return ZERO;
771        }
772        // knuth 4.5.1
773        // make sure we don't overflow unless the result *must* overflow.
774        final int d1 = greatestCommonDivisor(numerator, fraction.denominator);
775        final int d2 = greatestCommonDivisor(fraction.numerator, denominator);
776        return getReducedFraction(mulAndCheck(numerator / d1, fraction.numerator / d2),
777                mulPosAndCheck(denominator / d2, fraction.denominator / d1));
778    }
779
780    /**
781     * Divide the value of this fraction by another.
782     *
783     * @param fraction  the fraction to divide by, must not be {@code null}
784     * @return a {@link Fraction} instance with the resulting values
785     * @throws NullPointerException if the fraction is {@code null}
786     * @throws ArithmeticException if the fraction to divide by is zero
787     * @throws ArithmeticException if the resulting numerator or denominator exceeds
788     *  {@code Integer.MAX_VALUE}
789     */
790    public Fraction divideBy(final Fraction fraction) {
791        Objects.requireNonNull(fraction, "fraction");
792        if (fraction.numerator == 0) {
793            throw new ArithmeticException("The fraction to divide by must not be zero");
794        }
795        return multiplyBy(fraction.invert());
796    }
797
798    /**
799     * Compares this fraction to another object to test if they are equal..
800     *
801     * <p>To be equal, both values must be equal. Thus 2/4 is not equal to 1/2.</p>
802     *
803     * @param obj the reference object with which to compare
804     * @return {@code true} if this object is equal
805     */
806    @Override
807    public boolean equals(final Object obj) {
808        if (obj == this) {
809            return true;
810        }
811        if (!(obj instanceof Fraction)) {
812            return false;
813        }
814        final Fraction other = (Fraction) obj;
815        return getNumerator() == other.getNumerator() && getDenominator() == other.getDenominator();
816    }
817
818    /**
819     * Gets a hashCode for the fraction.
820     *
821     * @return a hash code value for this object
822     */
823    @Override
824    public int hashCode() {
825        if (hashCode == 0) {
826            // hash code update should be atomic.
827            hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator();
828        }
829        return hashCode;
830    }
831
832    /**
833     * Compares this object to another based on size.
834     *
835     * <p>Note: this class has a natural ordering that is inconsistent
836     * with equals, because, for example, equals treats 1/2 and 2/4 as
837     * different, whereas compareTo treats them as equal.
838     *
839     * @param other  the object to compare to
840     * @return -1 if this is less, 0 if equal, +1 if greater
841     * @throws ClassCastException if the object is not a {@link Fraction}
842     * @throws NullPointerException if the object is {@code null}
843     */
844    @Override
845    public int compareTo(final Fraction other) {
846        if (this == other) {
847            return 0;
848        }
849        if (numerator == other.numerator && denominator == other.denominator) {
850            return 0;
851        }
852
853        // otherwise see which is less
854        final long first = (long) numerator * (long) other.denominator;
855        final long second = (long) other.numerator * (long) denominator;
856        return Long.compare(first, second);
857    }
858
859    /**
860     * Gets the fraction as a {@link String}.
861     *
862     * <p>The format used is '<i>numerator</i>/<i>denominator</i>' always.
863     *
864     * @return a {@link String} form of the fraction
865     */
866    @Override
867    public String toString() {
868        if (toString == null) {
869            toString = getNumerator() + "/" + getDenominator();
870        }
871        return toString;
872    }
873
874    /**
875     * Gets the fraction as a proper {@link String} in the format X Y/Z.
876     *
877     * <p>The format used in '<i>wholeNumber</i> <i>numerator</i>/<i>denominator</i>'.
878     * If the whole number is zero it will be omitted. If the numerator is zero,
879     * only the whole number is returned.</p>
880     *
881     * @return a {@link String} form of the fraction
882     */
883    public String toProperString() {
884        if (toProperString == null) {
885            if (numerator == 0) {
886                toProperString = "0";
887            } else if (numerator == denominator) {
888                toProperString = "1";
889            } else if (numerator == -1 * denominator) {
890                toProperString = "-1";
891            } else if ((numerator > 0 ? -numerator : numerator) < -denominator) {
892                // note that we do the magnitude comparison test above with
893                // NEGATIVE (not positive) numbers, since negative numbers
894                // have a larger range. otherwise numerator==Integer.MIN_VALUE
895                // is handled incorrectly.
896                final int properNumerator = getProperNumerator();
897                if (properNumerator == 0) {
898                    toProperString = Integer.toString(getProperWhole());
899                } else {
900                    toProperString = getProperWhole() + " " + properNumerator + "/" + getDenominator();
901                }
902            } else {
903                toProperString = getNumerator() + "/" + getDenominator();
904            }
905        }
906        return toProperString;
907    }
908}