diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math/fraction/Fraction.java')
| -rw-r--r-- | src/main/java/org/apache/commons/math/fraction/Fraction.java | 655 |
1 files changed, 655 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math/fraction/Fraction.java b/src/main/java/org/apache/commons/math/fraction/Fraction.java new file mode 100644 index 0000000..82ecf63 --- /dev/null +++ b/src/main/java/org/apache/commons/math/fraction/Fraction.java @@ -0,0 +1,655 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math.fraction; + +import java.io.Serializable; +import java.math.BigInteger; + +import org.apache.commons.math.FieldElement; +import org.apache.commons.math.MathRuntimeException; +import org.apache.commons.math.exception.util.LocalizedFormats; +import org.apache.commons.math.exception.NullArgumentException; +import org.apache.commons.math.util.MathUtils; +import org.apache.commons.math.util.FastMath; + +/** + * Representation of a rational number. + * + * implements Serializable since 2.0 + * + * @since 1.1 + * @version $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $ + */ +public class Fraction + extends Number + implements FieldElement<Fraction>, Comparable<Fraction>, Serializable { + + /** A fraction representing "2 / 1". */ + public static final Fraction TWO = new Fraction(2, 1); + + /** A fraction representing "1". */ + public static final Fraction ONE = new Fraction(1, 1); + + /** A fraction representing "0". */ + public static final Fraction ZERO = new Fraction(0, 1); + + /** A fraction representing "4/5". */ + public static final Fraction FOUR_FIFTHS = new Fraction(4, 5); + + /** A fraction representing "1/5". */ + public static final Fraction ONE_FIFTH = new Fraction(1, 5); + + /** A fraction representing "1/2". */ + public static final Fraction ONE_HALF = new Fraction(1, 2); + + /** A fraction representing "1/4". */ + public static final Fraction ONE_QUARTER = new Fraction(1, 4); + + /** A fraction representing "1/3". */ + public static final Fraction ONE_THIRD = new Fraction(1, 3); + + /** A fraction representing "3/5". */ + public static final Fraction THREE_FIFTHS = new Fraction(3, 5); + + /** A fraction representing "3/4". */ + public static final Fraction THREE_QUARTERS = new Fraction(3, 4); + + /** A fraction representing "2/5". */ + public static final Fraction TWO_FIFTHS = new Fraction(2, 5); + + /** A fraction representing "2/4". */ + public static final Fraction TWO_QUARTERS = new Fraction(2, 4); + + /** A fraction representing "2/3". */ + public static final Fraction TWO_THIRDS = new Fraction(2, 3); + + /** A fraction representing "-1 / 1". */ + public static final Fraction MINUS_ONE = new Fraction(-1, 1); + + /** Serializable version identifier */ + private static final long serialVersionUID = 3698073679419233275L; + + /** The denominator. */ + private final int denominator; + + /** The numerator. */ + private final int numerator; + + /** + * Create a fraction given the double value. + * @param value the double value to convert to a fraction. + * @throws FractionConversionException if the continued fraction failed to + * converge. + */ + public Fraction(double value) throws FractionConversionException { + this(value, 1.0e-5, 100); + } + + /** + * Create a fraction given the double value and maximum error allowed. + * <p> + * References: + * <ul> + * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html"> + * Continued Fraction</a> equations (11) and (22)-(26)</li> + * </ul> + * </p> + * @param value the double value to convert to a fraction. + * @param epsilon maximum error allowed. The resulting fraction is within + * <code>epsilon</code> of <code>value</code>, in absolute terms. + * @param maxIterations maximum number of convergents + * @throws FractionConversionException if the continued fraction failed to + * converge. + */ + public Fraction(double value, double epsilon, int maxIterations) + throws FractionConversionException + { + this(value, epsilon, Integer.MAX_VALUE, maxIterations); + } + + /** + * Create a fraction given the double value and maximum denominator. + * <p> + * References: + * <ul> + * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html"> + * Continued Fraction</a> equations (11) and (22)-(26)</li> + * </ul> + * </p> + * @param value the double value to convert to a fraction. + * @param maxDenominator The maximum allowed value for denominator + * @throws FractionConversionException if the continued fraction failed to + * converge + */ + public Fraction(double value, int maxDenominator) + throws FractionConversionException + { + this(value, 0, maxDenominator, 100); + } + + /** + * Create a fraction given the double value and either the maximum error + * allowed or the maximum number of denominator digits. + * <p> + * + * NOTE: This constructor is called with EITHER + * - a valid epsilon value and the maxDenominator set to Integer.MAX_VALUE + * (that way the maxDenominator has no effect). + * OR + * - a valid maxDenominator value and the epsilon value set to zero + * (that way epsilon only has effect if there is an exact match before + * the maxDenominator value is reached). + * </p><p> + * + * It has been done this way so that the same code can be (re)used for both + * scenarios. However this could be confusing to users if it were part of + * the public API and this constructor should therefore remain PRIVATE. + * </p> + * + * See JIRA issue ticket MATH-181 for more details: + * + * https://issues.apache.org/jira/browse/MATH-181 + * + * @param value the double value to convert to a fraction. + * @param epsilon maximum error allowed. The resulting fraction is within + * <code>epsilon</code> of <code>value</code>, in absolute terms. + * @param maxDenominator maximum denominator value allowed. + * @param maxIterations maximum number of convergents + * @throws FractionConversionException if the continued fraction failed to + * converge. + */ + private Fraction(double value, double epsilon, int maxDenominator, int maxIterations) + throws FractionConversionException + { + long overflow = Integer.MAX_VALUE; + double r0 = value; + long a0 = (long)FastMath.floor(r0); + if (a0 > overflow) { + throw new FractionConversionException(value, a0, 1l); + } + + // check for (almost) integer arguments, which should not go + // to iterations. + if (FastMath.abs(a0 - value) < epsilon) { + this.numerator = (int) a0; + this.denominator = 1; + return; + } + + long p0 = 1; + long q0 = 0; + long p1 = a0; + long q1 = 1; + + long p2 = 0; + long q2 = 1; + + int n = 0; + boolean stop = false; + do { + ++n; + double r1 = 1.0 / (r0 - a0); + long a1 = (long)FastMath.floor(r1); + p2 = (a1 * p1) + p0; + q2 = (a1 * q1) + q0; + if ((p2 > overflow) || (q2 > overflow)) { + throw new FractionConversionException(value, p2, q2); + } + + double convergent = (double)p2 / (double)q2; + if (n < maxIterations && FastMath.abs(convergent - value) > epsilon && q2 < maxDenominator) { + p0 = p1; + p1 = p2; + q0 = q1; + q1 = q2; + a0 = a1; + r0 = r1; + } else { + stop = true; + } + } while (!stop); + + if (n >= maxIterations) { + throw new FractionConversionException(value, maxIterations); + } + + if (q2 < maxDenominator) { + this.numerator = (int) p2; + this.denominator = (int) q2; + } else { + this.numerator = (int) p1; + this.denominator = (int) q1; + } + + } + + /** + * Create a fraction from an int. + * The fraction is num / 1. + * @param num the numerator. + */ + public Fraction(int num) { + this(num, 1); + } + + /** + * Create a fraction given the numerator and denominator. The fraction is + * reduced to lowest terms. + * @param num the numerator. + * @param den the denominator. + * @throws ArithmeticException if the denominator is <code>zero</code> + */ + public Fraction(int num, int den) { + if (den == 0) { + throw MathRuntimeException.createArithmeticException( + LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION, num, den); + } + if (den < 0) { + if (num == Integer.MIN_VALUE || den == Integer.MIN_VALUE) { + throw MathRuntimeException.createArithmeticException( + LocalizedFormats.OVERFLOW_IN_FRACTION, num, den); + } + num = -num; + den = -den; + } + // reduce numerator and denominator by greatest common denominator. + final int d = MathUtils.gcd(num, den); + if (d > 1) { + num /= d; + den /= d; + } + + // move sign to numerator. + if (den < 0) { + num = -num; + den = -den; + } + this.numerator = num; + this.denominator = den; + } + + /** + * Returns the absolute value of this fraction. + * @return the absolute value. + */ + public Fraction abs() { + Fraction ret; + if (numerator >= 0) { + ret = this; + } else { + ret = negate(); + } + return ret; + } + + /** + * Compares this object to another based on size. + * @param object the object to compare to + * @return -1 if this is less than <tt>object</tt>, +1 if this is greater + * than <tt>object</tt>, 0 if they are equal. + */ + public int compareTo(Fraction object) { + long nOd = ((long) numerator) * object.denominator; + long dOn = ((long) denominator) * object.numerator; + return (nOd < dOn) ? -1 : ((nOd > dOn) ? +1 : 0); + } + + /** + * Gets the fraction as a <tt>double</tt>. This calculates the fraction as + * the numerator divided by denominator. + * @return the fraction as a <tt>double</tt> + */ + @Override + public double doubleValue() { + return (double)numerator / (double)denominator; + } + + /** + * Test for the equality of two fractions. If the lowest term + * numerator and denominators are the same for both fractions, the two + * fractions are considered to be equal. + * @param other fraction to test for equality to this fraction + * @return true if two fractions are equal, false if object is + * <tt>null</tt>, not an instance of {@link Fraction}, or not equal + * to this fraction instance. + */ + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } + if (other instanceof Fraction) { + // since fractions are always in lowest terms, numerators and + // denominators can be compared directly for equality. + Fraction rhs = (Fraction)other; + return (numerator == rhs.numerator) && + (denominator == rhs.denominator); + } + return false; + } + + /** + * Gets the fraction as a <tt>float</tt>. This calculates the fraction as + * the numerator divided by denominator. + * @return the fraction as a <tt>float</tt> + */ + @Override + public float floatValue() { + return (float)doubleValue(); + } + + /** + * Access the denominator. + * @return the denominator. + */ + public int getDenominator() { + return denominator; + } + + /** + * Access the numerator. + * @return the numerator. + */ + public int getNumerator() { + return numerator; + } + + /** + * Gets a hashCode for the fraction. + * @return a hash code value for this object + */ + @Override + public int hashCode() { + return 37 * (37 * 17 + numerator) + denominator; + } + + /** + * Gets the fraction as an <tt>int</tt>. This returns the whole number part + * of the fraction. + * @return the whole number fraction part + */ + @Override + public int intValue() { + return (int)doubleValue(); + } + + /** + * Gets the fraction as a <tt>long</tt>. This returns the whole number part + * of the fraction. + * @return the whole number fraction part + */ + @Override + public long longValue() { + return (long)doubleValue(); + } + + /** + * Return the additive inverse of this fraction. + * @return the negation of this fraction. + */ + public Fraction negate() { + if (numerator==Integer.MIN_VALUE) { + throw MathRuntimeException.createArithmeticException( + LocalizedFormats.OVERFLOW_IN_FRACTION, numerator, denominator); + } + return new Fraction(-numerator, denominator); + } + + /** + * Return the multiplicative inverse of this fraction. + * @return the reciprocal fraction + */ + public Fraction reciprocal() { + return new Fraction(denominator, numerator); + } + + /** + * <p>Adds the value of this fraction to another, returning the result in reduced form. + * The algorithm follows Knuth, 4.5.1.</p> + * + * @param fraction the fraction to add, must not be <code>null</code> + * @return a <code>Fraction</code> instance with the resulting values + * @throws IllegalArgumentException if the fraction is <code>null</code> + * @throws ArithmeticException if the resulting numerator or denominator exceeds + * <code>Integer.MAX_VALUE</code> + */ + public Fraction add(Fraction fraction) { + return addSub(fraction, true /* add */); + } + + /** + * Add an integer to the fraction. + * @param i the <tt>integer</tt> to add. + * @return this + i + */ + public Fraction add(final int i) { + return new Fraction(numerator + i * denominator, denominator); + } + + /** + * <p>Subtracts the value of another fraction from the value of this one, + * returning the result in reduced form.</p> + * + * @param fraction the fraction to subtract, must not be <code>null</code> + * @return a <code>Fraction</code> instance with the resulting values + * @throws IllegalArgumentException if the fraction is <code>null</code> + * @throws ArithmeticException if the resulting numerator or denominator + * cannot be represented in an <code>int</code>. + */ + public Fraction subtract(Fraction fraction) { + return addSub(fraction, false /* subtract */); + } + + /** + * Subtract an integer from the fraction. + * @param i the <tt>integer</tt> to subtract. + * @return this - i + */ + public Fraction subtract(final int i) { + return new Fraction(numerator - i * denominator, denominator); + } + + /** + * Implement add and subtract using algorithm described in Knuth 4.5.1. + * + * @param fraction the fraction to subtract, must not be <code>null</code> + * @param isAdd true to add, false to subtract + * @return a <code>Fraction</code> instance with the resulting values + * @throws IllegalArgumentException if the fraction is <code>null</code> + * @throws ArithmeticException if the resulting numerator or denominator + * cannot be represented in an <code>int</code>. + */ + private Fraction addSub(Fraction fraction, boolean isAdd) { + if (fraction == null) { + throw new NullArgumentException(LocalizedFormats.FRACTION); + } + // zero is identity for addition. + if (numerator == 0) { + return isAdd ? fraction : fraction.negate(); + } + if (fraction.numerator == 0) { + return this; + } + // if denominators are randomly distributed, d1 will be 1 about 61% + // of the time. + int d1 = MathUtils.gcd(denominator, fraction.denominator); + if (d1==1) { + // result is ( (u*v' +/- u'v) / u'v') + int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator); + int upv = MathUtils.mulAndCheck(fraction.numerator, denominator); + return new Fraction + (isAdd ? MathUtils.addAndCheck(uvp, upv) : + MathUtils.subAndCheck(uvp, upv), + MathUtils.mulAndCheck(denominator, fraction.denominator)); + } + // the quantity 't' requires 65 bits of precision; see knuth 4.5.1 + // exercise 7. we're going to use a BigInteger. + // t = u(v'/d1) +/- v(u'/d1) + BigInteger uvp = BigInteger.valueOf(numerator) + .multiply(BigInteger.valueOf(fraction.denominator/d1)); + BigInteger upv = BigInteger.valueOf(fraction.numerator) + .multiply(BigInteger.valueOf(denominator/d1)); + BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv); + // but d2 doesn't need extra precision because + // d2 = gcd(t,d1) = gcd(t mod d1, d1) + int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue(); + int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1); + + // result is (t/d2) / (u'/d1)(v'/d2) + BigInteger w = t.divide(BigInteger.valueOf(d2)); + if (w.bitLength() > 31) { + throw MathRuntimeException.createArithmeticException(LocalizedFormats.NUMERATOR_OVERFLOW_AFTER_MULTIPLY, + w); + } + return new Fraction (w.intValue(), + MathUtils.mulAndCheck(denominator/d1, + fraction.denominator/d2)); + } + + /** + * <p>Multiplies the value of this fraction by another, returning the + * result in reduced form.</p> + * + * @param fraction the fraction to multiply by, must not be <code>null</code> + * @return a <code>Fraction</code> instance with the resulting values + * @throws IllegalArgumentException if the fraction is <code>null</code> + * @throws ArithmeticException if the resulting numerator or denominator exceeds + * <code>Integer.MAX_VALUE</code> + */ + public Fraction multiply(Fraction fraction) { + if (fraction == null) { + throw new NullArgumentException(LocalizedFormats.FRACTION); + } + if (numerator == 0 || fraction.numerator == 0) { + return ZERO; + } + // knuth 4.5.1 + // make sure we don't overflow unless the result *must* overflow. + int d1 = MathUtils.gcd(numerator, fraction.denominator); + int d2 = MathUtils.gcd(fraction.numerator, denominator); + return getReducedFraction + (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2), + MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1)); + } + + /** + * Multiply the fraction by an integer. + * @param i the <tt>integer</tt> to multiply by. + * @return this * i + */ + public Fraction multiply(final int i) { + return new Fraction(numerator * i, denominator); + } + + /** + * <p>Divide the value of this fraction by another.</p> + * + * @param fraction the fraction to divide by, must not be <code>null</code> + * @return a <code>Fraction</code> instance with the resulting values + * @throws IllegalArgumentException if the fraction is <code>null</code> + * @throws ArithmeticException if the fraction to divide by is zero + * @throws ArithmeticException if the resulting numerator or denominator exceeds + * <code>Integer.MAX_VALUE</code> + */ + public Fraction divide(Fraction fraction) { + if (fraction == null) { + throw new NullArgumentException(LocalizedFormats.FRACTION); + } + if (fraction.numerator == 0) { + throw MathRuntimeException.createArithmeticException( + LocalizedFormats.ZERO_FRACTION_TO_DIVIDE_BY, + fraction.numerator, fraction.denominator); + } + return multiply(fraction.reciprocal()); + } + + /** + * Divide the fraction by an integer. + * @param i the <tt>integer</tt> to divide by. + * @return this * i + */ + public Fraction divide(final int i) { + return new Fraction(numerator, denominator * i); + } + + /** + * <p>Creates a <code>Fraction</code> instance with the 2 parts + * of a fraction Y/Z.</p> + * + * <p>Any negative signs are resolved to be on the numerator.</p> + * + * @param numerator the numerator, for example the three in 'three sevenths' + * @param denominator the denominator, for example the seven in 'three sevenths' + * @return a new fraction instance, with the numerator and denominator reduced + * @throws ArithmeticException if the denominator is <code>zero</code> + */ + public static Fraction getReducedFraction(int numerator, int denominator) { + if (denominator == 0) { + throw MathRuntimeException.createArithmeticException( + LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION, numerator, denominator); + } + if (numerator==0) { + return ZERO; // normalize zero. + } + // allow 2^k/-2^31 as a valid fraction (where k>0) + if (denominator==Integer.MIN_VALUE && (numerator&1)==0) { + numerator/=2; denominator/=2; + } + if (denominator < 0) { + if (numerator==Integer.MIN_VALUE || + denominator==Integer.MIN_VALUE) { + throw MathRuntimeException.createArithmeticException( + LocalizedFormats.OVERFLOW_IN_FRACTION, numerator, denominator); + } + numerator = -numerator; + denominator = -denominator; + } + // simplify fraction. + int gcd = MathUtils.gcd(numerator, denominator); + numerator /= gcd; + denominator /= gcd; + return new Fraction(numerator, denominator); + } + + /** + * <p> + * Returns the <code>String</code> representing this fraction, ie + * "num / dem" or just "num" if the denominator is one. + * </p> + * + * @return a string representation of the fraction. + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + String str = null; + if (denominator == 1) { + str = Integer.toString(numerator); + } else if (numerator == 0) { + str = "0"; + } else { + str = numerator + " / " + denominator; + } + return str; + } + + /** {@inheritDoc} */ + public FractionField getField() { + return FractionField.getInstance(); + } + +} |