View Javadoc

    1   /*
    2    * Copyright 2005 The Apache Software Foundation.
    3    *
    4    * Licensed under the Apache License, Version 2.0 (the "License");
    5    * you may not use this file except in compliance with the License.
    6    * You may obtain a copy of the License at
    7    *
    8    *      http://www.apache.org/licenses/LICENSE-2.0
    9    *
    10   * Unless required by applicable law or agreed to in writing, software
    11   * distributed under the License is distributed on an "AS IS" BASIS,
    12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13   * See the License for the specific language governing permissions and
    14   * limitations under the License.
    15   */
    16  package org.apache.commons.math.fraction;
    17
    18  import java.math.BigInteger;
    19  import org.apache.commons.math.ConvergenceException;
    20  import org.apache.commons.math.util.MathUtils;
    21
    22  /***
    23   * Representation of a rational number.
    24   *
    25   * @since 1.1
    26   * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
    27   */
    28  public class Fraction extends Number implements Comparable {
    29
    30      /*** A fraction representing "1 / 1". */
    31      public static final Fraction ONE = new Fraction(1, 1);
    32
    33      /*** A fraction representing "0 / 1". */
    34      public static final Fraction ZERO = new Fraction(0, 1);
    35
    36      /*** Serializable version identifier */
    37      private static final long serialVersionUID = 65382027393090L;
    38
    39      /*** The denominator. */
    40      private int denominator;
    41
    42      /*** The numerator. */
    43      private int numerator;
    44
    45      /***
    46       * Create a fraction given the double value.
    47       * @param value the double value to convert to a fraction.
    48       * @throws ConvergenceException if the continued fraction failed to
    49       *         converge.
    50       */
    51      public Fraction(double value) throws ConvergenceException {
    52          this(value, 1.0e-5, 100);
    53      }
    54
    55      /***
    56       * Create a fraction given the double value.
    57       * <p>
    58       * References:
    59       * <ul>
    60       * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
    61       * Continued Fraction</a> equations (11) and (22)-(26)</li>
    62       * </ul>
    63       * </p>
    64       * @param value the double value to convert to a fraction.
    65       * @param epsilon maximum error allowed.  The resulting fraction is within
    66       *        <code>epsilon</code> of <code>value</code>, in absolute terms.
    67       * @param maxIterations maximum number of convergents
    68       * @throws ConvergenceException if the continued fraction failed to
    69       *         converge.
    70       */
    71      public Fraction(double value, double epsilon, int maxIterations)
    72          throws ConvergenceException
    73      {
    74          double r0 = value;
    75          int a0 = (int)Math.floor(r0);
    76
    77          // check for (almost) integer arguments, which should not go
    78          // to iterations.
    79          if (Math.abs(a0 - value) < epsilon) {
    80              this.numerator = a0;
    81              this.denominator = 1;
    82              return;
    83          }
    84
    85          int p0 = 1;
    86          int q0 = 0;
    87          int p1 = a0;
    88          int q1 = 1;
    89
    90          int p2 = 0;
    91          int q2 = 1;
    92
    93          int n = 0;
    94          boolean stop = false;
    95          do {
    96              ++n;
    97              double r1 = 1.0 / (r0 - a0);
    98              int a1 = (int)Math.floor(r1);
    99              p2 = (a1 * p1) + p0;
    100             q2 = (a1 * q1) + q0;
    101
    102             double convergent = (double)p2 / (double)q2;
    103             if (n < maxIterations && Math.abs(convergent - value) > epsilon) {
    104                 p0 = p1;
    105                 p1 = p2;
    106                 q0 = q1;
    107                 q1 = q2;
    108                 a0 = a1;
    109                 r0 = r1;
    110             } else {
    111                 stop = true;
    112             }
    113         } while (!stop);
    114
    115         if (n >= maxIterations) {
    116             throw new ConvergenceException(
    117                     "Unable to convert double to fraction");
    118         }
    119
    120         this.numerator = p2;
    121         this.denominator = q2;
    122         reduce();
    123     }
    124
    125     /***
    126      * Create a fraction given the numerator and denominator.  The fraction is
    127      * reduced to lowest terms.
    128      * @param num the numerator.
    129      * @param den the denominator.
    130      * @throws ArithmeticException if the denomiator is <code>zero</code>
    131      */
    132     public Fraction(int num, int den) {
    133         super();
    134         if (den == 0) {
    135             throw new ArithmeticException("The denominator must not be zero");
    136         }
    137         if (den < 0) {
    138             if (num == Integer.MIN_VALUE ||
    139                     den == Integer.MIN_VALUE) {
    140                 throw new ArithmeticException("overflow: can't negate");
    141             }
    142             num = -num;
    143             den = -den;
    144         }
    145         this.numerator = num;
    146         this.denominator = den;
    147         reduce();
    148     }
    149
    150     /***
    151      * Returns the absolute value of this fraction.
    152      * @return the absolute value.
    153      */
    154     public Fraction abs() {
    155         Fraction ret;
    156         if (numerator >= 0) {
    157             ret = this;
    158         } else {
    159             ret = negate();
    160         }
    161         return ret;
    162     }
    163
    164     /***
    165      * Compares this object to another based on size.
    166      * @param object the object to compare to
    167      * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
    168      *         than <tt>object</tt>, 0 if they are equal.
    169      */
    170     public int compareTo(Object object) {
    171         int ret = 0;
    172
    173         if (this != object) {
    174             Fraction other = (Fraction)object;
    175             double first = doubleValue();
    176             double second = other.doubleValue();
    177
    178             if (first < second) {
    179                 ret = -1;
    180             } else if (first > second) {
    181                 ret = 1;
    182             }
    183         }
    184
    185         return ret;
    186     }
    187
    188     /***
    189      * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
    190      * the numerator divided by denominator.
    191      * @return the fraction as a <tt>double</tt>
    192      */
    193     public double doubleValue() {
    194         return (double)numerator / (double)denominator;
    195     }
    196
    197     /***
    198      * Test for the equality of two fractions.  If the lowest term
    199      * numerator and denominators are the same for both fractions, the two
    200      * fractions are considered to be equal.
    201      * @param other fraction to test for equality to this fraction
    202      * @return true if two fractions are equal, false if object is
    203      *         <tt>null</tt>, not an instance of {@link Fraction}, or not equal
    204      *         to this fraction instance.
    205      */
    206     public boolean equals(Object other) {
    207         boolean ret;
    208
    209         if (this == other) {
    210             ret = true;
    211         } else if (other == null) {
    212             ret = false;
    213         } else {
    214             try {
    215                 // since fractions are always in lowest terms, numerators and
    216                 // denominators can be compared directly for equality.
    217                 Fraction rhs = (Fraction)other;
    218                 ret = (numerator == rhs.numerator) &&
    219                     (denominator == rhs.denominator);
    220             } catch (ClassCastException ex) {
    221                 // ignore exception
    222                 ret = false;
    223             }
    224         }
    225
    226         return ret;
    227     }
    228
    229     /***
    230      * Gets the fraction as a <tt>float</tt>. This calculates the fraction as
    231      * the numerator divided by denominator.
    232      * @return the fraction as a <tt>float</tt>
    233      */
    234     public float floatValue() {
    235         return (float)doubleValue();
    236     }
    237
    238     /***
    239      * Access the denominator.
    240      * @return the denominator.
    241      */
    242     public int getDenominator() {
    243         return denominator;
    244     }
    245
    246     /***
    247      * Access the numerator.
    248      * @return the numerator.
    249      */
    250     public int getNumerator() {
    251         return numerator;
    252     }
    253
    254     /***
    255      * Gets a hashCode for the fraction.
    256      * @return a hash code value for this object
    257      */
    258     public int hashCode() {
    259         return 37 * (37 * 17 + getNumerator()) + getDenominator();
    260     }
    261
    262     /***
    263      * Gets the fraction as an <tt>int</tt>. This returns the whole number part
    264      * of the fraction.
    265      * @return the whole number fraction part
    266      */
    267     public int intValue() {
    268         return (int)doubleValue();
    269     }
    270
    271     /***
    272      * Gets the fraction as a <tt>long</tt>. This returns the whole number part
    273      * of the fraction.
    274      * @return the whole number fraction part
    275      */
    276     public long longValue() {
    277         return (long)doubleValue();
    278     }
    279
    280     /***
    281      * Return the additive inverse of this fraction.
    282      * @return the negation of this fraction.
    283      */
    284     public Fraction negate() {
    285         if (numerator==Integer.MIN_VALUE) {
    286             throw new ArithmeticException("overflow: too large to negate");
    287         }
    288         return new Fraction(-numerator, denominator);
    289     }
    290
    291     /***
    292      * Return the multiplicative inverse of this fraction.
    293      * @return the reciprocal fraction
    294      */
    295     public Fraction reciprocal() {
    296         return new Fraction(denominator, numerator);
    297     }
    298
    299     /***
    300      * <p>Adds the value of this fraction to another, returning the result in reduced form.
    301      * The algorithm follows Knuth, 4.5.1.</p>
    302      *
    303      * @param fraction  the fraction to add, must not be <code>null</code>
    304      * @return a <code>Fraction</code> instance with the resulting values
    305      * @throws IllegalArgumentException if the fraction is <code>null</code>
    306      * @throws ArithmeticException if the resulting numerator or denominator exceeds
    307      *  <code>Integer.MAX_VALUE</code>
    308      */
    309     public Fraction add(Fraction fraction) {
    310         return addSub(fraction, true /* add */);
    311     }
    312
    313     /***
    314      * <p>Subtracts the value of another fraction from the value of this one,
    315      * returning the result in reduced form.</p>
    316      *
    317      * @param fraction  the fraction to subtract, must not be <code>null</code>
    318      * @return a <code>Fraction</code> instance with the resulting values
    319      * @throws IllegalArgumentException if the fraction is <code>null</code>
    320      * @throws ArithmeticException if the resulting numerator or denominator
    321      *   cannot be represented in an <code>int</code>.
    322      */
    323     public Fraction subtract(Fraction fraction) {
    324         return addSub(fraction, false /* subtract */);
    325     }
    326
    327     /***
    328      * Implement add and subtract using algorithm described in Knuth 4.5.1.
    329      *
    330      * @param fraction the fraction to subtract, must not be <code>null</code>
    331      * @param isAdd true to add, false to subtract
    332      * @return a <code>Fraction</code> instance with the resulting values
    333      * @throws IllegalArgumentException if the fraction is <code>null</code>
    334      * @throws ArithmeticException if the resulting numerator or denominator
    335      *   cannot be represented in an <code>int</code>.
    336      */
    337     private Fraction addSub(Fraction fraction, boolean isAdd) {
    338         if (fraction == null) {
    339             throw new IllegalArgumentException("The fraction must not be null");
    340         }
    341         // zero is identity for addition.
    342         if (numerator == 0) {
    343             return isAdd ? fraction : fraction.negate();
    344         }
    345         if (fraction.numerator == 0) {
    346             return this;
    347         }
    348         // if denominators are randomly distributed, d1 will be 1 about 61%
    349         // of the time.
    350         int d1 = MathUtils.gcd(denominator, fraction.denominator);
    351         if (d1==1) {
    352             // result is ( (u*v' +/- u'v) / u'v')
    353             int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
    354             int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
    355             return new Fraction
    356                 (isAdd ? MathUtils.addAndCheck(uvp, upv) :
    357                  MathUtils.subAndCheck(uvp, upv),
    358                  MathUtils.mulAndCheck(denominator, fraction.denominator));
    359         }
    360         // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
    361         // exercise 7.  we're going to use a BigInteger.
    362         // t = u(v'/d1) +/- v(u'/d1)
    363         BigInteger uvp = BigInteger.valueOf(numerator)
    364         .multiply(BigInteger.valueOf(fraction.denominator/d1));
    365         BigInteger upv = BigInteger.valueOf(fraction.numerator)
    366         .multiply(BigInteger.valueOf(denominator/d1));
    367         BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
    368         // but d2 doesn't need extra precision because
    369         // d2 = gcd(t,d1) = gcd(t mod d1, d1)
    370         int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
    371         int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1);
    372
    373         // result is (t/d2) / (u'/d1)(v'/d2)
    374         BigInteger w = t.divide(BigInteger.valueOf(d2));
    375         if (w.bitLength() > 31) {
    376             throw new ArithmeticException
    377             ("overflow: numerator too large after multiply");
    378         }
    379         return new Fraction (w.intValue(),
    380                 MathUtils.mulAndCheck(denominator/d1,
    381                         fraction.denominator/d2));
    382     }
    383
    384     /***
    385      * <p>Multiplies the value of this fraction by another, returning the
    386      * result in reduced form.</p>
    387      *
    388      * @param fraction  the fraction to multiply by, must not be <code>null</code>
    389      * @return a <code>Fraction</code> instance with the resulting values
    390      * @throws IllegalArgumentException if the fraction is <code>null</code>
    391      * @throws ArithmeticException if the resulting numerator or denominator exceeds
    392      *  <code>Integer.MAX_VALUE</code>
    393      */
    394     public Fraction multiply(Fraction fraction) {
    395         if (fraction == null) {
    396             throw new IllegalArgumentException("The fraction must not be null");
    397         }
    398         if (numerator == 0 || fraction.numerator == 0) {
    399             return ZERO;
    400         }
    401         // knuth 4.5.1
    402         // make sure we don't overflow unless the result *must* overflow.
    403         int d1 = MathUtils.gcd(numerator, fraction.denominator);
    404         int d2 = MathUtils.gcd(fraction.numerator, denominator);
    405         return getReducedFraction
    406         (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
    407                 MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
    408     }
    409
    410     /***
    411      * <p>Divide the value of this fraction by another.</p>
    412      *
    413      * @param fraction  the fraction to divide by, must not be <code>null</code>
    414      * @return a <code>Fraction</code> instance with the resulting values
    415      * @throws IllegalArgumentException if the fraction is <code>null</code>
    416      * @throws ArithmeticException if the fraction to divide by is zero
    417      * @throws ArithmeticException if the resulting numerator or denominator exceeds
    418      *  <code>Integer.MAX_VALUE</code>
    419      */
    420     public Fraction divide(Fraction fraction) {
    421         if (fraction == null) {
    422             throw new IllegalArgumentException("The fraction must not be null");
    423         }
    424         if (fraction.numerator == 0) {
    425             throw new ArithmeticException("The fraction to divide by must not be zero");
    426         }
    427         return multiply(fraction.reciprocal());
    428     }
    429
    430     /***
    431      * <p>Creates a <code>Fraction</code> instance with the 2 parts
    432      * of a fraction Y/Z.</p>
    433      *
    434      * <p>Any negative signs are resolved to be on the numerator.</p>
    435      *
    436      * @param numerator  the numerator, for example the three in 'three sevenths'
    437      * @param denominator  the denominator, for example the seven in 'three sevenths'
    438      * @return a new fraction instance, with the numerator and denominator reduced
    439      * @throws ArithmeticException if the denominator is <code>zero</code>
    440      */
    441     public static Fraction getReducedFraction(int numerator, int denominator) {
    442         if (denominator == 0) {
    443             throw new ArithmeticException("The denominator must not be zero");
    444         }
    445         if (numerator==0) {
    446             return ZERO; // normalize zero.
    447         }
    448         // allow 2^k/-2^31 as a valid fraction (where k>0)
    449         if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
    450             numerator/=2; denominator/=2;
    451         }
    452         if (denominator < 0) {
    453             if (numerator==Integer.MIN_VALUE ||
    454                     denominator==Integer.MIN_VALUE) {
    455                 throw new ArithmeticException("overflow: can't negate");
    456             }
    457             numerator = -numerator;
    458             denominator = -denominator;
    459         }
    460         // simplify fraction.
    461         int gcd = MathUtils.gcd(numerator, denominator);
    462         numerator /= gcd;
    463         denominator /= gcd;
    464         return new Fraction(numerator, denominator);
    465     }
    466
    467     /***
    468      * Reduce this fraction to lowest terms.  This is accomplished by dividing
    469      * both numerator and denominator by their greatest common divisor.
    470      */
    471     private void reduce() {
    472         // reduce numerator and denominator by greatest common denominator.
    473         int d = MathUtils.gcd(numerator, denominator);
    474         if (d > 1) {
    475             numerator /= d;
    476             denominator /= d;
    477         }
    478
    479         // move sign to numerator.
    480         if (denominator < 0) {
    481             numerator *= -1;
    482             denominator *= -1;
    483         }
    484     }
    485 }