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