    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.math.fraction;
    018
    019    import java.io.Serializable;
    020    import java.math.BigInteger;
    021
    022    import org.apache.commons.math.FieldElement;
    023    import org.apache.commons.math.MathRuntimeException;
    024    import org.apache.commons.math.exception.util.LocalizedFormats;
    025    import org.apache.commons.math.exception.NullArgumentException;
    026    import org.apache.commons.math.util.MathUtils;
    027    import org.apache.commons.math.util.FastMath;
    028
    029    /**
    030     * Representation of a rational number.
    031     *
    032     * implements Serializable since 2.0
    033     *
    034     * @since 1.1
    035     * @version $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 ao??t 2010) $
    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</code> of <code>value</code>, 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</code> of <code>value</code>, 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 (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 ((p2 > overflow) || (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 ArithmeticException if the denominator is <code>zero</code>
    255         */
    256        public Fraction(int num, int den) {
    257            if (den == 0) {
    258                throw MathRuntimeException.createArithmeticException(
    259                      LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION, num, den);
    260            }
    261            if (den < 0) {
    262                if (num == Integer.MIN_VALUE || den == Integer.MIN_VALUE) {
    263                    throw MathRuntimeException.createArithmeticException(
    264                          LocalizedFormats.OVERFLOW_IN_FRACTION, num, den);
    265                }
    266                num = -num;
    267                den = -den;
    268            }
    269            // reduce numerator and denominator by greatest common denominator.
    270            final int d = MathUtils.gcd(num, den);
    271            if (d > 1) {
    272                num /= d;
    273                den /= d;
    274            }
    275
    276            // move sign to numerator.
    277            if (den < 0) {
    278                num = -num;
    279                den = -den;
    280            }
    281            this.numerator   = num;
    282            this.denominator = den;
    283        }
    284
    285        /**
    286         * Returns the absolute value of this fraction.
    287         * @return the absolute value.
    288         */
    289        public Fraction abs() {
    290            Fraction ret;
    291            if (numerator >= 0) {
    292                ret = this;
    293            } else {
    294                ret = negate();
    295            }
    296            return ret;
    297        }
    298
    299        /**
    300         * Compares this object to another based on size.
    301         * @param object the object to compare to
    302         * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
    303         *         than <tt>object</tt>, 0 if they are equal.
    304         */
    305        public int compareTo(Fraction object) {
    306            long nOd = ((long) numerator) * object.denominator;
    307            long dOn = ((long) denominator) * object.numerator;
    308            return (nOd < dOn) ? -1 : ((nOd > dOn) ? +1 : 0);
    309        }
    310
    311        /**
    312         * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
    313         * the numerator divided by denominator.
    314         * @return the fraction as a <tt>double</tt>
    315         */
    316        @Override
    317        public double doubleValue() {
    318            return (double)numerator / (double)denominator;
    319        }
    320
    321        /**
    322         * Test for the equality of two fractions.  If the lowest term
    323         * numerator and denominators are the same for both fractions, the two
    324         * fractions are considered to be equal.
    325         * @param other fraction to test for equality to this fraction
    326         * @return true if two fractions are equal, false if object is
    327         *         <tt>null</tt>, not an instance of {@link Fraction}, or not equal
    328         *         to this fraction instance.
    329         */
    330        @Override
    331        public boolean equals(Object other) {
    332            if (this == other) {
    333                return true;
    334            }
    335            if (other instanceof Fraction) {
    336                // since fractions are always in lowest terms, numerators and
    337                // denominators can be compared directly for equality.
    338                Fraction rhs = (Fraction)other;
    339                return (numerator == rhs.numerator) &&
    340                    (denominator == rhs.denominator);
    341            }
    342            return false;
    343        }
    344
    345        /**
    346         * Gets the fraction as a <tt>float</tt>. This calculates the fraction as
    347         * the numerator divided by denominator.
    348         * @return the fraction as a <tt>float</tt>
    349         */
    350        @Override
    351        public float floatValue() {
    352            return (float)doubleValue();
    353        }
    354
    355        /**
    356         * Access the denominator.
    357         * @return the denominator.
    358         */
    359        public int getDenominator() {
    360            return denominator;
    361        }
    362
    363        /**
    364         * Access the numerator.
    365         * @return the numerator.
    366         */
    367        public int getNumerator() {
    368            return numerator;
    369        }
    370
    371        /**
    372         * Gets a hashCode for the fraction.
    373         * @return a hash code value for this object
    374         */
    375        @Override
    376        public int hashCode() {
    377            return 37 * (37 * 17 + numerator) + denominator;
    378        }
    379
    380        /**
    381         * Gets the fraction as an <tt>int</tt>. This returns the whole number part
    382         * of the fraction.
    383         * @return the whole number fraction part
    384         */
    385        @Override
    386        public int intValue() {
    387            return (int)doubleValue();
    388        }
    389
    390        /**
    391         * Gets the fraction as a <tt>long</tt>. This returns the whole number part
    392         * of the fraction.
    393         * @return the whole number fraction part
    394         */
    395        @Override
    396        public long longValue() {
    397            return (long)doubleValue();
    398        }
    399
    400        /**
    401         * Return the additive inverse of this fraction.
    402         * @return the negation of this fraction.
    403         */
    404        public Fraction negate() {
    405            if (numerator==Integer.MIN_VALUE) {
    406                throw MathRuntimeException.createArithmeticException(
    407                      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</code>
    425         * @return a <code>Fraction</code> instance with the resulting values
    426         * @throws IllegalArgumentException if the fraction is <code>null</code>
    427         * @throws ArithmeticException if the resulting numerator or denominator exceeds
    428         *  <code>Integer.MAX_VALUE</code>
    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</code>
    448         * @return a <code>Fraction</code> instance with the resulting values
    449         * @throws IllegalArgumentException if the fraction is <code>null</code>
    450         * @throws ArithmeticException if the resulting numerator or denominator
    451         *   cannot be represented in an <code>int</code>.
    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</code>
    470         * @param isAdd true to add, false to subtract
    471         * @return a <code>Fraction</code> instance with the resulting values
    472         * @throws IllegalArgumentException if the fraction is <code>null</code>
    473         * @throws ArithmeticException if the resulting numerator or denominator
    474         *   cannot be represented in an <code>int</code>.
    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 = MathUtils.gcd(denominator, fraction.denominator);
    490            if (d1==1) {
    491                // result is ( (u*v' +/- u'v) / u'v')
    492                int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
    493                int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
    494                return new Fraction
    495                    (isAdd ? MathUtils.addAndCheck(uvp, upv) :
    496                     MathUtils.subAndCheck(uvp, upv),
    497                     MathUtils.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:MathUtils.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 MathRuntimeException.createArithmeticException(LocalizedFormats.NUMERATOR_OVERFLOW_AFTER_MULTIPLY,
    516                                                                     w);
    517            }
    518            return new Fraction (w.intValue(),
    519                    MathUtils.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</code>
    528         * @return a <code>Fraction</code> instance with the resulting values
    529         * @throws IllegalArgumentException if the fraction is <code>null</code>
    530         * @throws ArithmeticException if the resulting numerator or denominator exceeds
    531         *  <code>Integer.MAX_VALUE</code>
    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 = MathUtils.gcd(numerator, fraction.denominator);
    543            int d2 = MathUtils.gcd(fraction.numerator, denominator);
    544            return getReducedFraction
    545            (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
    546                    MathUtils.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</code>
    562         * @return a <code>Fraction</code> instance with the resulting values
    563         * @throws IllegalArgumentException if the fraction is <code>null</code>
    564         * @throws ArithmeticException if the fraction to divide by is zero
    565         * @throws ArithmeticException if the resulting numerator or denominator exceeds
    566         *  <code>Integer.MAX_VALUE</code>
    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 MathRuntimeException.createArithmeticException(
    574                        LocalizedFormats.ZERO_FRACTION_TO_DIVIDE_BY,
    575                        fraction.numerator, fraction.denominator);
    576            }
    577            return multiply(fraction.reciprocal());
    578        }
    579
    580        /**
    581         * Divide the fraction by an integer.
    582         * @param i the <tt>integer</tt> to divide by.
    583         * @return this * i
    584         */
    585        public Fraction divide(final int i) {
    586            return new Fraction(numerator, denominator * i);
    587        }
    588
    589        /**
    590         * <p>Creates a <code>Fraction</code> instance with the 2 parts
    591         * of a fraction Y/Z.</p>
    592         *
    593         * <p>Any negative signs are resolved to be on the numerator.</p>
    594         *
    595         * @param numerator  the numerator, for example the three in 'three sevenths'
    596         * @param denominator  the denominator, for example the seven in 'three sevenths'
    597         * @return a new fraction instance, with the numerator and denominator reduced
    598         * @throws ArithmeticException if the denominator is <code>zero</code>
    599         */
    600        public static Fraction getReducedFraction(int numerator, int denominator) {
    601            if (denominator == 0) {
    602                throw MathRuntimeException.createArithmeticException(
    603                      LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION, numerator, denominator);
    604            }
    605            if (numerator==0) {
    606                return ZERO; // normalize zero.
    607            }
    608            // allow 2^k/-2^31 as a valid fraction (where k>0)
    609            if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
    610                numerator/=2; denominator/=2;
    611            }
    612            if (denominator < 0) {
    613                if (numerator==Integer.MIN_VALUE ||
    614                        denominator==Integer.MIN_VALUE) {
    615                    throw MathRuntimeException.createArithmeticException(
    616                          LocalizedFormats.OVERFLOW_IN_FRACTION, numerator, denominator);
    617                }
    618                numerator = -numerator;
    619                denominator = -denominator;
    620            }
    621            // simplify fraction.
    622            int gcd = MathUtils.gcd(numerator, denominator);
    623            numerator /= gcd;
    624            denominator /= gcd;
    625            return new Fraction(numerator, denominator);
    626        }
    627
    628        /**
    629         * <p>
    630         * Returns the <code>String</code> representing this fraction, ie
    631         * "num / dem" or just "num" if the denominator is one.
    632         * </p>
    633         *
    634         * @return a string representation of the fraction.
    635         * @see java.lang.Object#toString()
    636         */
    637        @Override
    638        public String toString() {
    639            String str = null;
    640            if (denominator == 1) {
    641                str = Integer.toString(numerator);
    642            } else if (numerator == 0) {
    643                str = "0";
    644            } else {
    645                str = numerator + " / " + denominator;
    646            }
    647            return str;
    648        }
    649
    650        /** {@inheritDoc} */
    651        public FractionField getField() {
    652            return FractionField.getInstance();
    653        }
    654
    655    }