    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}