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