    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.math3.fraction;
    018
    019    import java.io.Serializable;
    020    import java.math.BigInteger;
    021
    022    import org.apache.commons.math3.FieldElement;
    023    import org.apache.commons.math3.exception.util.LocalizedFormats;
    024    import org.apache.commons.math3.exception.MathArithmeticException;
    025    import org.apache.commons.math3.exception.NullArgumentException;
    026    import org.apache.commons.math3.util.ArithmeticUtils;
    027    import org.apache.commons.math3.util.FastMath;
    028
    029    /**
    030     * Representation of a rational number.
    031     *
    032     * implements Serializable since 2.0
    033     *
    034     * @since 1.1
    035     * @version $Id: Fraction.java 1416643 2012-12-03 19:37:14Z tn $
    036     */
    037    public class Fraction
    038        extends Number
    039        implements FieldElement<Fraction>, Comparable<Fraction>, Serializable {
    040
    041        /** A fraction representing "2 / 1". */
    042        public static final Fraction TWO = new Fraction(2, 1);
    043
    044        /** A fraction representing "1". */
    045        public static final Fraction ONE = new Fraction(1, 1);
    046
    047        /** A fraction representing "0". */
    048        public static final Fraction ZERO = new Fraction(0, 1);
    049
    050        /** A fraction representing "4/5". */
    051        public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
    052
    053        /** A fraction representing "1/5". */
    054        public static final Fraction ONE_FIFTH = new Fraction(1, 5);
    055
    056        /** A fraction representing "1/2". */
    057        public static final Fraction ONE_HALF = new Fraction(1, 2);
    058
    059        /** A fraction representing "1/4". */
    060        public static final Fraction ONE_QUARTER = new Fraction(1, 4);
    061
    062        /** A fraction representing "1/3". */
    063        public static final Fraction ONE_THIRD = new Fraction(1, 3);
    064
    065        /** A fraction representing "3/5". */
    066        public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
    067
    068        /** A fraction representing "3/4". */
    069        public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
    070
    071        /** A fraction representing "2/5". */
    072        public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
    073
    074        /** A fraction representing "2/4". */
    075        public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
    076
    077        /** A fraction representing "2/3". */
    078        public static final Fraction TWO_THIRDS = new Fraction(2, 3);
    079
    080        /** A fraction representing "-1 / 1". */
    081        public static final Fraction MINUS_ONE = new Fraction(-1, 1);
    082
    083        /** Serializable version identifier */
    084        private static final long serialVersionUID = 3698073679419233275L;
    085
    086        /** The denominator. */
    087        private final int denominator;
    088
    089        /** The numerator. */
    090        private final int numerator;
    091
    092        /**
    093         * Create a fraction given the double value.
    094         * @param value the double value to convert to a fraction.
    095         * @throws FractionConversionException if the continued fraction failed to
    096         *         converge.
    097         */
    098        public Fraction(double value) throws FractionConversionException {
    099            this(value, 1.0e-5, 100);
    100        }
    101
    102        /**
    103         * Create a fraction given the double value and maximum error allowed.
    104         * <p>
    105         * References:
    106         * <ul>
    107         * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
    108         * Continued Fraction</a> equations (11) and (22)-(26)</li>
    109         * </ul>
    110         * </p>
    111         * @param value the double value to convert to a fraction.
    112         * @param epsilon maximum error allowed.  The resulting fraction is within
    113         *        {@code epsilon} of {@code value}, in absolute terms.
    114         * @param maxIterations maximum number of convergents
    115         * @throws FractionConversionException if the continued fraction failed to
    116         *         converge.
    117         */
    118        public Fraction(double value, double epsilon, int maxIterations)
    119            throws FractionConversionException
    120        {
    121            this(value, epsilon, Integer.MAX_VALUE, maxIterations);
    122        }
    123
    124        /**
    125         * Create a fraction given the double value and maximum denominator.
    126         * <p>
    127         * References:
    128         * <ul>
    129         * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
    130         * Continued Fraction</a> equations (11) and (22)-(26)</li>
    131         * </ul>
    132         * </p>
    133         * @param value the double value to convert to a fraction.
    134         * @param maxDenominator The maximum allowed value for denominator
    135         * @throws FractionConversionException if the continued fraction failed to
    136         *         converge
    137         */
    138        public Fraction(double value, int maxDenominator)
    139            throws FractionConversionException
    140        {
    141           this(value, 0, maxDenominator, 100);
    142        }
    143
    144        /**
    145         * Create a fraction given the double value and either the maximum error
    146         * allowed or the maximum number of denominator digits.
    147         * <p>
    148         *
    149         * NOTE: This constructor is called with EITHER
    150         *   - a valid epsilon value and the maxDenominator set to Integer.MAX_VALUE
    151         *     (that way the maxDenominator has no effect).
    152         * OR
    153         *   - a valid maxDenominator value and the epsilon value set to zero
    154         *     (that way epsilon only has effect if there is an exact match before
    155         *     the maxDenominator value is reached).
    156         * </p><p>
    157         *
    158         * It has been done this way so that the same code can be (re)used for both
    159         * scenarios. However this could be confusing to users if it were part of
    160         * the public API and this constructor should therefore remain PRIVATE.
    161         * </p>
    162         *
    163         * See JIRA issue ticket MATH-181 for more details:
    164         *
    165         *     https://issues.apache.org/jira/browse/MATH-181
    166         *
    167         * @param value the double value to convert to a fraction.
    168         * @param epsilon maximum error allowed.  The resulting fraction is within
    169         *        {@code epsilon} of {@code value}, in absolute terms.
    170         * @param maxDenominator maximum denominator value allowed.
    171         * @param maxIterations maximum number of convergents
    172         * @throws FractionConversionException if the continued fraction failed to
    173         *         converge.
    174         */
    175        private Fraction(double value, double epsilon, int maxDenominator, int maxIterations)
    176            throws FractionConversionException
    177        {
    178            long overflow = Integer.MAX_VALUE;
    179            double r0 = value;
    180            long a0 = (long)FastMath.floor(r0);
    181            if (FastMath.abs(a0) > overflow) {
    182                throw new FractionConversionException(value, a0, 1l);
    183            }
    184
    185            // check for (almost) integer arguments, which should not go
    186            // to iterations.
    187            if (FastMath.abs(a0 - value) < epsilon) {
    188                this.numerator = (int) a0;
    189                this.denominator = 1;
    190                return;
    191            }
    192
    193            long p0 = 1;
    194            long q0 = 0;
    195            long p1 = a0;
    196            long q1 = 1;
    197
    198            long p2 = 0;
    199            long q2 = 1;
    200
    201            int n = 0;
    202            boolean stop = false;
    203            do {
    204                ++n;
    205                double r1 = 1.0 / (r0 - a0);
    206                long a1 = (long)FastMath.floor(r1);
    207                p2 = (a1 * p1) + p0;
    208                q2 = (a1 * q1) + q0;
    209                if ((FastMath.abs(p2) > overflow) || (FastMath.abs(q2) > overflow)) {
    210                    throw new FractionConversionException(value, p2, q2);
    211                }
    212
    213                double convergent = (double)p2 / (double)q2;
    214                if (n < maxIterations && FastMath.abs(convergent - value) > epsilon && q2 < maxDenominator) {
    215                    p0 = p1;
    216                    p1 = p2;
    217                    q0 = q1;
    218                    q1 = q2;
    219                    a0 = a1;
    220                    r0 = r1;
    221                } else {
    222                    stop = true;
    223                }
    224            } while (!stop);
    225
    226            if (n >= maxIterations) {
    227                throw new FractionConversionException(value, maxIterations);
    228            }
    229
    230            if (q2 < maxDenominator) {
    231                this.numerator = (int) p2;
    232                this.denominator = (int) q2;
    233            } else {
    234                this.numerator = (int) p1;
    235                this.denominator = (int) q1;
    236            }
    237
    238        }
    239
    240        /**
    241         * Create a fraction from an int.
    242         * The fraction is num / 1.
    243         * @param num the numerator.
    244         */
    245        public Fraction(int num) {
    246            this(num, 1);
    247        }
    248
    249        /**
    250         * Create a fraction given the numerator and denominator.  The fraction is
    251         * reduced to lowest terms.
    252         * @param num the numerator.
    253         * @param den the denominator.
    254         * @throws MathArithmeticException if the denominator is {@code zero}
    255         */
    256        public Fraction(int num, int den) {
    257            if (den == 0) {
    258                throw new MathArithmeticException(LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION,
    259                                                  num, den);
    260            }
    261            if (den < 0) {
    262                if (num == Integer.MIN_VALUE ||
    263                    den == Integer.MIN_VALUE) {
    264                    throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_FRACTION,
    265                                                      num, den);
    266                }
    267                num = -num;
    268                den = -den;
    269            }
    270            // reduce numerator and denominator by greatest common denominator.
    271            final int d = ArithmeticUtils.gcd(num, den);
    272            if (d > 1) {
    273                num /= d;
    274                den /= d;
    275            }
    276
    277            // move sign to numerator.
    278            if (den < 0) {
    279                num = -num;
    280                den = -den;
    281            }
    282            this.numerator   = num;
    283            this.denominator = den;
    284        }
    285
    286        /**
    287         * Returns the absolute value of this fraction.
    288         * @return the absolute value.
    289         */
    290        public Fraction abs() {
    291            Fraction ret;
    292            if (numerator >= 0) {
    293                ret = this;
    294            } else {
    295                ret = negate();
    296            }
    297            return ret;
    298        }
    299
    300        /**
    301         * Compares this object to another based on size.
    302         * @param object the object to compare to
    303         * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
    304         *         than <tt>object</tt>, 0 if they are equal.
    305         */
    306        public int compareTo(Fraction object) {
    307            long nOd = ((long) numerator) * object.denominator;
    308            long dOn = ((long) denominator) * object.numerator;
    309            return (nOd < dOn) ? -1 : ((nOd > dOn) ? +1 : 0);
    310        }
    311
    312        /**
    313         * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
    314         * the numerator divided by denominator.
    315         * @return the fraction as a <tt>double</tt>
    316         */
    317        @Override
    318        public double doubleValue() {
    319            return (double)numerator / (double)denominator;
    320        }
    321
    322        /**
    323         * Test for the equality of two fractions.  If the lowest term
    324         * numerator and denominators are the same for both fractions, the two
    325         * fractions are considered to be equal.
    326         * @param other fraction to test for equality to this fraction
    327         * @return true if two fractions are equal, false if object is
    328         *         <tt>null</tt>, not an instance of {@link Fraction}, or not equal
    329         *         to this fraction instance.
    330         */
    331        @Override
    332        public boolean equals(Object other) {
    333            if (this == other) {
    334                return true;
    335            }
    336            if (other instanceof Fraction) {
    337                // since fractions are always in lowest terms, numerators and
    338                // denominators can be compared directly for equality.
    339                Fraction rhs = (Fraction)other;
    340                return (numerator == rhs.numerator) &&
    341                    (denominator == rhs.denominator);
    342            }
    343            return false;
    344        }
    345
    346        /**
    347         * Gets the fraction as a <tt>float</tt>. This calculates the fraction as
    348         * the numerator divided by denominator.
    349         * @return the fraction as a <tt>float</tt>
    350         */
    351        @Override
    352        public float floatValue() {
    353            return (float)doubleValue();
    354        }
    355
    356        /**
    357         * Access the denominator.
    358         * @return the denominator.
    359         */
    360        public int getDenominator() {
    361            return denominator;
    362        }
    363
    364        /**
    365         * Access the numerator.
    366         * @return the numerator.
    367         */
    368        public int getNumerator() {
    369            return numerator;
    370        }
    371
    372        /**
    373         * Gets a hashCode for the fraction.
    374         * @return a hash code value for this object
    375         */
    376        @Override
    377        public int hashCode() {
    378            return 37 * (37 * 17 + numerator) + denominator;
    379        }
    380
    381        /**
    382         * Gets the fraction as an <tt>int</tt>. This returns the whole number part
    383         * of the fraction.
    384         * @return the whole number fraction part
    385         */
    386        @Override
    387        public int intValue() {
    388            return (int)doubleValue();
    389        }
    390
    391        /**
    392         * Gets the fraction as a <tt>long</tt>. This returns the whole number part
    393         * of the fraction.
    394         * @return the whole number fraction part
    395         */
    396        @Override
    397        public long longValue() {
    398            return (long)doubleValue();
    399        }
    400
    401        /**
    402         * Return the additive inverse of this fraction.
    403         * @return the negation of this fraction.
    404         */
    405        public Fraction negate() {
    406            if (numerator==Integer.MIN_VALUE) {
    407                throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_FRACTION, numerator, denominator);
    408            }
    409            return new Fraction(-numerator, denominator);
    410        }
    411
    412        /**
    413         * Return the multiplicative inverse of this fraction.
    414         * @return the reciprocal fraction
    415         */
    416        public Fraction reciprocal() {
    417            return new Fraction(denominator, numerator);
    418        }
    419
    420        /**
    421         * <p>Adds the value of this fraction to another, returning the result in reduced form.
    422         * The algorithm follows Knuth, 4.5.1.</p>
    423         *
    424         * @param fraction  the fraction to add, must not be {@code null}
    425         * @return a {@code Fraction} instance with the resulting values
    426         * @throws NullArgumentException if the fraction is {@code null}
    427         * @throws MathArithmeticException if the resulting numerator or denominator exceeds
    428         *  {@code Integer.MAX_VALUE}
    429         */
    430        public Fraction add(Fraction fraction) {
    431            return addSub(fraction, true /* add */);
    432        }
    433
    434        /**
    435         * Add an integer to the fraction.
    436         * @param i the <tt>integer</tt> to add.
    437         * @return this + i
    438         */
    439        public Fraction add(final int i) {
    440            return new Fraction(numerator + i * denominator, denominator);
    441        }
    442
    443        /**
    444         * <p>Subtracts the value of another fraction from the value of this one,
    445         * returning the result in reduced form.</p>
    446         *
    447         * @param fraction  the fraction to subtract, must not be {@code null}
    448         * @return a {@code Fraction} instance with the resulting values
    449         * @throws NullArgumentException if the fraction is {@code null}
    450         * @throws MathArithmeticException if the resulting numerator or denominator
    451         *   cannot be represented in an {@code int}.
    452         */
    453        public Fraction subtract(Fraction fraction) {
    454            return addSub(fraction, false /* subtract */);
    455        }
    456
    457        /**
    458         * Subtract an integer from the fraction.
    459         * @param i the <tt>integer</tt> to subtract.
    460         * @return this - i
    461         */
    462        public Fraction subtract(final int i) {
    463            return new Fraction(numerator - i * denominator, denominator);
    464        }
    465
    466        /**
    467         * Implement add and subtract using algorithm described in Knuth 4.5.1.
    468         *
    469         * @param fraction the fraction to subtract, must not be {@code null}
    470         * @param isAdd true to add, false to subtract
    471         * @return a {@code Fraction} instance with the resulting values
    472         * @throws NullArgumentException if the fraction is {@code null}
    473         * @throws MathArithmeticException if the resulting numerator or denominator
    474         *   cannot be represented in an {@code int}.
    475         */
    476        private Fraction addSub(Fraction fraction, boolean isAdd) {
    477            if (fraction == null) {
    478                throw new NullArgumentException(LocalizedFormats.FRACTION);
    479            }
    480            // zero is identity for addition.
    481            if (numerator == 0) {
    482                return isAdd ? fraction : fraction.negate();
    483            }
    484            if (fraction.numerator == 0) {
    485                return this;
    486            }
    487            // if denominators are randomly distributed, d1 will be 1 about 61%
    488            // of the time.
    489            int d1 = ArithmeticUtils.gcd(denominator, fraction.denominator);
    490            if (d1==1) {
    491                // result is ( (u*v' +/- u'v) / u'v')
    492                int uvp = ArithmeticUtils.mulAndCheck(numerator, fraction.denominator);
    493                int upv = ArithmeticUtils.mulAndCheck(fraction.numerator, denominator);
    494                return new Fraction
    495                    (isAdd ? ArithmeticUtils.addAndCheck(uvp, upv) :
    496                     ArithmeticUtils.subAndCheck(uvp, upv),
    497                     ArithmeticUtils.mulAndCheck(denominator, fraction.denominator));
    498            }
    499            // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
    500            // exercise 7.  we're going to use a BigInteger.
    501            // t = u(v'/d1) +/- v(u'/d1)
    502            BigInteger uvp = BigInteger.valueOf(numerator)
    503            .multiply(BigInteger.valueOf(fraction.denominator/d1));
    504            BigInteger upv = BigInteger.valueOf(fraction.numerator)
    505            .multiply(BigInteger.valueOf(denominator/d1));
    506            BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
    507            // but d2 doesn't need extra precision because
    508            // d2 = gcd(t,d1) = gcd(t mod d1, d1)
    509            int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
    510            int d2 = (tmodd1==0)?d1:ArithmeticUtils.gcd(tmodd1, d1);
    511
    512            // result is (t/d2) / (u'/d1)(v'/d2)
    513            BigInteger w = t.divide(BigInteger.valueOf(d2));
    514            if (w.bitLength() > 31) {
    515                throw new MathArithmeticException(LocalizedFormats.NUMERATOR_OVERFLOW_AFTER_MULTIPLY,
    516                                                  w);
    517            }
    518            return new Fraction (w.intValue(),
    519                    ArithmeticUtils.mulAndCheck(denominator/d1,
    520                            fraction.denominator/d2));
    521        }
    522
    523        /**
    524         * <p>Multiplies the value of this fraction by another, returning the
    525         * result in reduced form.</p>
    526         *
    527         * @param fraction  the fraction to multiply by, must not be {@code null}
    528         * @return a {@code Fraction} instance with the resulting values
    529         * @throws NullArgumentException if the fraction is {@code null}
    530         * @throws MathArithmeticException if the resulting numerator or denominator exceeds
    531         *  {@code Integer.MAX_VALUE}
    532         */
    533        public Fraction multiply(Fraction fraction) {
    534            if (fraction == null) {
    535                throw new NullArgumentException(LocalizedFormats.FRACTION);
    536            }
    537            if (numerator == 0 || fraction.numerator == 0) {
    538                return ZERO;
    539            }
    540            // knuth 4.5.1
    541            // make sure we don't overflow unless the result *must* overflow.
    542            int d1 = ArithmeticUtils.gcd(numerator, fraction.denominator);
    543            int d2 = ArithmeticUtils.gcd(fraction.numerator, denominator);
    544            return getReducedFraction
    545            (ArithmeticUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
    546                    ArithmeticUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
    547        }
    548
    549        /**
    550         * Multiply the fraction by an integer.
    551         * @param i the <tt>integer</tt> to multiply by.
    552         * @return this * i
    553         */
    554        public Fraction multiply(final int i) {
    555            return new Fraction(numerator * i, denominator);
    556        }
    557
    558        /**
    559         * <p>Divide the value of this fraction by another.</p>
    560         *
    561         * @param fraction  the fraction to divide by, must not be {@code null}
    562         * @return a {@code Fraction} instance with the resulting values
    563         * @throws IllegalArgumentException if the fraction is {@code null}
    564         * @throws MathArithmeticException if the fraction to divide by is zero
    565         * @throws MathArithmeticException if the resulting numerator or denominator exceeds
    566         *  {@code Integer.MAX_VALUE}
    567         */
    568        public Fraction divide(Fraction fraction) {
    569            if (fraction == null) {
    570                throw new NullArgumentException(LocalizedFormats.FRACTION);
    571            }
    572            if (fraction.numerator == 0) {
    573                throw new MathArithmeticException(LocalizedFormats.ZERO_FRACTION_TO_DIVIDE_BY,
    574                                                  fraction.numerator, fraction.denominator);
    575            }
    576            return multiply(fraction.reciprocal());
    577        }
    578
    579        /**
    580         * Divide the fraction by an integer.
    581         * @param i the <tt>integer</tt> to divide by.
    582         * @return this * i
    583         */
    584        public Fraction divide(final int i) {
    585            return new Fraction(numerator, denominator * i);
    586        }
    587
    588        /**
    589         * <p>
    590         * Gets the fraction percentage as a <tt>double</tt>. This calculates the
    591         * fraction as the numerator divided by denominator multiplied by 100.
    592         * </p>
    593         *
    594         * @return the fraction percentage as a <tt>double</tt>.
    595         */
    596        public double percentageValue() {
    597            return 100 * doubleValue();
    598        }
    599
    600        /**
    601         * <p>Creates a {@code Fraction} instance with the 2 parts
    602         * of a fraction Y/Z.</p>
    603         *
    604         * <p>Any negative signs are resolved to be on the numerator.</p>
    605         *
    606         * @param numerator  the numerator, for example the three in 'three sevenths'
    607         * @param denominator  the denominator, for example the seven in 'three sevenths'
    608         * @return a new fraction instance, with the numerator and denominator reduced
    609         * @throws MathArithmeticException if the denominator is {@code zero}
    610         */
    611        public static Fraction getReducedFraction(int numerator, int denominator) {
    612            if (denominator == 0) {
    613                throw new MathArithmeticException(LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION,
    614                                                  numerator, denominator);
    615            }
    616            if (numerator==0) {
    617                return ZERO; // normalize zero.
    618            }
    619            // allow 2^k/-2^31 as a valid fraction (where k>0)
    620            if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
    621                numerator/=2; denominator/=2;
    622            }
    623            if (denominator < 0) {
    624                if (numerator==Integer.MIN_VALUE ||
    625                        denominator==Integer.MIN_VALUE) {
    626                    throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_FRACTION,
    627                                                      numerator, denominator);
    628                }
    629                numerator = -numerator;
    630                denominator = -denominator;
    631            }
    632            // simplify fraction.
    633            int gcd = ArithmeticUtils.gcd(numerator, denominator);
    634            numerator /= gcd;
    635            denominator /= gcd;
    636            return new Fraction(numerator, denominator);
    637        }
    638
    639        /**
    640         * <p>
    641         * Returns the {@code String} representing this fraction, ie
    642         * "num / dem" or just "num" if the denominator is one.
    643         * </p>
    644         *
    645         * @return a string representation of the fraction.
    646         * @see java.lang.Object#toString()
    647         */
    648        @Override
    649        public String toString() {
    650            String str = null;
    651            if (denominator == 1) {
    652                str = Integer.toString(numerator);
    653            } else if (numerator == 0) {
    654                str = "0";
    655            } else {
    656                str = numerator + " / " + denominator;
    657            }
    658            return str;
    659        }
    660
    661        /** {@inheritDoc} */
    662        public FractionField getField() {
    663            return FractionField.getInstance();
    664        }
    665
    666    }