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