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