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