/*
* 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.BigDecimal;
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.util.MathUtils;
import org.apache.commons.math.util.FastMath;
/**
* Representation of a rational number without any overflow. This class is
* immutable.
*
* @version $Revision: 1073687 $ $Date: 2011-02-23 11:39:25 +0100 (mer. 23 févr. 2011) $
* @since 2.0
*/
public class BigFraction
extends Number
implements FieldElement
* Create a {@link BigFraction} equivalent to the passed BigInteger, ie
* "num / 1".
*
* This constructor behaves differently from
* {@link #BigFraction(double, double, int)}. It converts the
* double value exactly, considering its internal bits representation.
* This does work for all values except NaN and infinities and does
* not requires any loop or convergence threshold.
*
* Since this conversion is exact and since double numbers are sometimes
* approximated, the fraction created may seem strange in some cases. For example
* calling
* References:
* BigInteger
representation of 100. */
private static final BigInteger ONE_HUNDRED_DOUBLE = BigInteger.valueOf(100);
/** The numerator. */
private final BigInteger numerator;
/** The denominator. */
private final BigInteger denominator;
/**
* new BigFraction(1.0 / 3.0)
does not create
* the fraction 1/3 but the fraction 6004799503160661 / 18014398509481984
* because the double number passed to the constructor is not exactly 1/3
* (this number cannot be stored exactly in IEEE754).
*
*
*
epsilon
of value
, in absolute terms.
* @param maxIterations
* maximum number of convergents.
* @throws FractionConversionException
* if the continued fraction failed to converge.
* @see #BigFraction(double)
*/
public BigFraction(final double value, final double epsilon,
final int maxIterations)
throws FractionConversionException {
this(value, epsilon, Integer.MAX_VALUE, maxIterations);
}
/**
* Create a fraction given the double value and either the maximum error
* allowed or the maximum number of denominator digits.
* * * 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). *
** * 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. *
* * 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 *epsilon
of value
, 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 BigFraction(final double value, final double epsilon,
final 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) {
numerator = BigInteger.valueOf(a0);
denominator = BigInteger.ONE;
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;
final double r1 = 1.0 / (r0 - a0);
final 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);
}
final 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) {
numerator = BigInteger.valueOf(p2);
denominator = BigInteger.valueOf(q2);
} else {
numerator = BigInteger.valueOf(p1);
denominator = BigInteger.valueOf(q1);
}
}
/**
* Create a fraction given the double value and maximum denominator.
* * References: *
* Create a {@link BigFraction} equivalent to the passed int, ie * "num / 1". *
* * @param num * the numerator. */ public BigFraction(final int num) { this(BigInteger.valueOf(num), BigInteger.ONE); } /** ** Create a {@link BigFraction} given the numerator and denominator as simple * int. The {@link BigFraction} is reduced to lowest terms. *
* * @param num * the numerator. * @param den * the denominator. */ public BigFraction(final int num, final int den) { this(BigInteger.valueOf(num), BigInteger.valueOf(den)); } /** ** Create a {@link BigFraction} equivalent to the passed long, ie "num / 1". *
* * @param num * the numerator. */ public BigFraction(final long num) { this(BigInteger.valueOf(num), BigInteger.ONE); } /** ** Create a {@link BigFraction} given the numerator and denominator as simple * long. The {@link BigFraction} is reduced to lowest terms. *
* * @param num * the numerator. * @param den * the denominator. */ public BigFraction(final long num, final long den) { this(BigInteger.valueOf(num), BigInteger.valueOf(den)); } /** *
* Creates a BigFraction
instance with the 2 parts of a fraction
* Y/Z.
*
* Any negative signs are resolved to be on the numerator. *
* * @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 iszero
.
*/
public static BigFraction getReducedFraction(final int numerator,
final int denominator) {
if (numerator == 0) {
return ZERO; // normalize zero.
}
return new BigFraction(numerator, denominator);
}
/**
* * Returns the absolute value of this {@link BigFraction}. *
* * @return the absolute value as a {@link BigFraction}. */ public BigFraction abs() { return (BigInteger.ZERO.compareTo(numerator) <= 0) ? this : negate(); } /** ** Adds the value of this fraction to the passed {@link BigInteger}, * returning the result in reduced form. *
* * @param bg * the {@link BigInteger} to add, must'nt benull
.
* @return a BigFraction
instance with the resulting values.
* @throws NullPointerException
* if the {@link BigInteger} is null
.
*/
public BigFraction add(final BigInteger bg) {
return new BigFraction(numerator.add(denominator.multiply(bg)), denominator);
}
/**
* * Adds the value of this fraction to the passed integer, returning * the result in reduced form. *
* * @param i * the integer to add. * @return aBigFraction
instance with the resulting values.
*/
public BigFraction add(final int i) {
return add(BigInteger.valueOf(i));
}
/**
* * Adds the value of this fraction to the passed long, returning * the result in reduced form. *
* * @param l * the long to add. * @return aBigFraction
instance with the resulting values.
*/
public BigFraction add(final long l) {
return add(BigInteger.valueOf(l));
}
/**
* * Adds the value of this fraction to another, returning the result in * reduced form. *
* * @param fraction * the {@link BigFraction} to add, must not benull
.
* @return a {@link BigFraction} instance with the resulting values.
* @throws NullPointerException if the {@link BigFraction} is {@code null}.
*/
public BigFraction add(final BigFraction fraction) {
if (fraction == null) {
throw new NullPointerException(LocalizedFormats.FRACTION.getSourceString());
}
if (ZERO.equals(fraction)) {
return this;
}
BigInteger num = null;
BigInteger den = null;
if (denominator.equals(fraction.denominator)) {
num = numerator.add(fraction.numerator);
den = denominator;
} else {
num = (numerator.multiply(fraction.denominator)).add((fraction.numerator).multiply(denominator));
den = denominator.multiply(fraction.denominator);
}
return new BigFraction(num, den);
}
/**
*
* Gets the fraction as a BigDecimal
. This calculates the
* fraction as the numerator divided by denominator.
*
BigDecimal
.
* @throws ArithmeticException
* if the exact quotient does not have a terminating decimal
* expansion.
* @see BigDecimal
*/
public BigDecimal bigDecimalValue() {
return new BigDecimal(numerator).divide(new BigDecimal(denominator));
}
/**
*
* Gets the fraction as a BigDecimal
following the passed
* rounding mode. This calculates the fraction as the numerator divided by
* denominator.
*
BigDecimal
.
* @throws IllegalArgumentException
* if roundingMode does not represent a valid rounding
* mode.
* @see BigDecimal
*/
public BigDecimal bigDecimalValue(final int roundingMode) {
return new BigDecimal(numerator).divide(new BigDecimal(denominator), roundingMode);
}
/**
*
* Gets the fraction as a BigDecimal
following the passed scale
* and rounding mode. This calculates the fraction as the numerator divided
* by denominator.
*
BigDecimal
quotient to be returned.
* see {@link BigDecimal} for more information.
* @param roundingMode
* rounding mode to apply. see {@link BigDecimal} constants.
* @return the fraction as a BigDecimal
.
* @see BigDecimal
*/
public BigDecimal bigDecimalValue(final int scale, final int roundingMode) {
return new BigDecimal(numerator).divide(new BigDecimal(denominator), scale, roundingMode);
}
/**
* * Compares this object to another based on size. *
* * @param object * the object to compare to, must not benull
.
* @return -1 if this is less than object, +1 if this is greater
* than object, 0 if they are equal.
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
public int compareTo(final BigFraction object) {
BigInteger nOd = numerator.multiply(object.denominator);
BigInteger dOn = denominator.multiply(object.numerator);
return nOd.compareTo(dOn);
}
/**
*
* Divide the value of this fraction by the passed BigInteger
,
* ie "this * 1 / bg", returning the result in reduced form.
*
BigInteger
to divide by, must not be
* null
.
* @return a {@link BigFraction} instance with the resulting values.
* @throws NullPointerException if the {@code BigInteger} is {@code null}.
* @throws ArithmeticException
* if the fraction to divide by is zero.
*/
public BigFraction divide(final BigInteger bg) {
if (BigInteger.ZERO.equals(bg)) {
throw MathRuntimeException.createArithmeticException(LocalizedFormats.ZERO_DENOMINATOR);
}
return new BigFraction(numerator, denominator.multiply(bg));
}
/**
* * Divide the value of this fraction by the passed int, ie * "this * 1 / i", returning the result in reduced form. *
* * @param i * the int to divide by. * @return a {@link BigFraction} instance with the resulting values. * @throws ArithmeticException * if the fraction to divide by is zero. */ public BigFraction divide(final int i) { return divide(BigInteger.valueOf(i)); } /** ** Divide the value of this fraction by the passed long, ie * "this * 1 / l", returning the result in reduced form. *
* * @param l * the long to divide by. * @return a {@link BigFraction} instance with the resulting values. * @throws ArithmeticException * if the fraction to divide by is zero. */ public BigFraction divide(final long l) { return divide(BigInteger.valueOf(l)); } /** ** Divide the value of this fraction by another, returning the result in * reduced form. *
* * @param fraction Fraction to divide by, must not be {@code null}. * @return a {@link BigFraction} instance with the resulting values. * @throws NullPointerException if the {@code fraction} is {@code null}. * @throws ArithmeticException if the fraction to divide by is zero. */ public BigFraction divide(final BigFraction fraction) { if (fraction == null) { throw new NullPointerException(LocalizedFormats.FRACTION.getSourceString()); } if (BigInteger.ZERO.equals(fraction.numerator)) { throw MathRuntimeException.createArithmeticException(LocalizedFormats.ZERO_DENOMINATOR); } return multiply(fraction.reciprocal()); } /** ** Gets the fraction as a double. This calculates the fraction as * the numerator divided by denominator. *
* * @return the fraction as a double * @see java.lang.Number#doubleValue() */ @Override public double doubleValue() { return numerator.doubleValue() / denominator.doubleValue(); } /** ** 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, can be *null
.
* @return true if two fractions are equal, false if object is
* null
, not an instance of {@link BigFraction}, or not
* equal to this fraction instance.
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
public boolean equals(final Object other) {
boolean ret = false;
if (this == other) {
ret = true;
} else if (other instanceof BigFraction) {
BigFraction rhs = ((BigFraction) other).reduce();
BigFraction thisOne = this.reduce();
ret = thisOne.numerator.equals(rhs.numerator) && thisOne.denominator.equals(rhs.denominator);
}
return ret;
}
/**
* * Gets the fraction as a float. This calculates the fraction as * the numerator divided by denominator. *
* * @return the fraction as a float. * @see java.lang.Number#floatValue() */ @Override public float floatValue() { return numerator.floatValue() / denominator.floatValue(); } /** *
* Access the denominator as a BigInteger
.
*
BigInteger
.
*/
public BigInteger getDenominator() {
return denominator;
}
/**
* * Access the denominator as a int. *
* * @return the denominator as a int. */ public int getDenominatorAsInt() { return denominator.intValue(); } /** ** Access the denominator as a long. *
* * @return the denominator as a long. */ public long getDenominatorAsLong() { return denominator.longValue(); } /** *
* Access the numerator as a BigInteger
.
*
BigInteger
.
*/
public BigInteger getNumerator() {
return numerator;
}
/**
* * Access the numerator as a int. *
* * @return the numerator as a int. */ public int getNumeratorAsInt() { return numerator.intValue(); } /** ** Access the numerator as a long. *
* * @return the numerator as a long. */ public long getNumeratorAsLong() { return numerator.longValue(); } /** ** Gets a hashCode for the fraction. *
* * @return a hash code value for this object. * @see java.lang.Object#hashCode() */ @Override public int hashCode() { return 37 * (37 * 17 + numerator.hashCode()) + denominator.hashCode(); } /** ** Gets the fraction as an int. This returns the whole number part * of the fraction. *
* * @return the whole number fraction part. * @see java.lang.Number#intValue() */ @Override public int intValue() { return numerator.divide(denominator).intValue(); } /** ** Gets the fraction as a long. This returns the whole number part * of the fraction. *
* * @return the whole number fraction part. * @see java.lang.Number#longValue() */ @Override public long longValue() { return numerator.divide(denominator).longValue(); } /** *
* Multiplies the value of this fraction by the passed
* BigInteger
, returning the result in reduced form.
*
* Multiply the value of this fraction by the passed int, returning * the result in reduced form. *
* * @param i * the int to multiply by. * @return a {@link BigFraction} instance with the resulting values. */ public BigFraction multiply(final int i) { return multiply(BigInteger.valueOf(i)); } /** ** Multiply the value of this fraction by the passed long, * returning the result in reduced form. *
* * @param l * the long to multiply by. * @return a {@link BigFraction} instance with the resulting values. */ public BigFraction multiply(final long l) { return multiply(BigInteger.valueOf(l)); } /** ** Multiplies the value of this fraction by another, returning the result in * reduced form. *
* * @param fraction Fraction to multiply by, must not be {@code null}. * @return a {@link BigFraction} instance with the resulting values. * @throws NullPointerException if {@code fraction} is {@code null}. */ public BigFraction multiply(final BigFraction fraction) { if (fraction == null) { throw new NullPointerException(LocalizedFormats.FRACTION.getSourceString()); } if (numerator.equals(BigInteger.ZERO) || fraction.numerator.equals(BigInteger.ZERO)) { return ZERO; } return new BigFraction(numerator.multiply(fraction.numerator), denominator.multiply(fraction.denominator)); } /** ** Return the additive inverse of this fraction, returning the result in * reduced form. *
* * @return the negation of this fraction. */ public BigFraction negate() { return new BigFraction(numerator.negate(), denominator); } /** ** Gets the fraction percentage as a double. This calculates the * fraction as the numerator divided by denominator multiplied by 100. *
* * @return the fraction percentage as a double. */ public double percentageValue() { return (numerator.divide(denominator)).multiply(ONE_HUNDRED_DOUBLE).doubleValue(); } /** ** Returns a integer whose value is * (thisexponent), returning the result in reduced form. *
* * @param exponent * exponent to which thisBigInteger
is to be
* raised.
* @return thisexponent.
*/
public BigFraction pow(final int exponent) {
if (exponent < 0) {
return new BigFraction(denominator.pow(-exponent), numerator.pow(-exponent));
}
return new BigFraction(numerator.pow(exponent), denominator.pow(exponent));
}
/**
*
* Returns a BigFraction
whose value is
* (thisexponent), returning the result in reduced form.
*
BigFraction
is to be raised.
* @return thisexponent as a BigFraction
.
*/
public BigFraction pow(final long exponent) {
if (exponent < 0) {
return new BigFraction(MathUtils.pow(denominator, -exponent),
MathUtils.pow(numerator, -exponent));
}
return new BigFraction(MathUtils.pow(numerator, exponent),
MathUtils.pow(denominator, exponent));
}
/**
*
* Returns a BigFraction
whose value is
* (thisexponent), returning the result in reduced form.
*
BigFraction
is to be raised.
* @return thisexponent as a BigFraction
.
*/
public BigFraction pow(final BigInteger exponent) {
if (exponent.compareTo(BigInteger.ZERO) < 0) {
final BigInteger eNeg = exponent.negate();
return new BigFraction(MathUtils.pow(denominator, eNeg),
MathUtils.pow(numerator, eNeg));
}
return new BigFraction(MathUtils.pow(numerator, exponent),
MathUtils.pow(denominator, exponent));
}
/**
*
* Returns a double
whose value is
* (thisexponent), returning the result in reduced form.
*
BigFraction
is to be raised.
* @return thisexponent.
*/
public double pow(final double exponent) {
return FastMath.pow(numerator.doubleValue(), exponent) /
FastMath.pow(denominator.doubleValue(), exponent);
}
/**
* * Return the multiplicative inverse of this fraction. *
* * @return the reciprocal fraction. */ public BigFraction reciprocal() { return new BigFraction(denominator, numerator); } /** *
* Reduce this BigFraction
to its lowest terms.
*
BigFraction
. It doesn't change anything if
* the fraction can be reduced.
*/
public BigFraction reduce() {
final BigInteger gcd = numerator.gcd(denominator);
return new BigFraction(numerator.divide(gcd), denominator.divide(gcd));
}
/**
* * Subtracts the value of an {@link BigInteger} from the value of this one, * returning the result in reduced form. *
* * @param bg the {@link BigInteger} to subtract, cannot be {@code null}. * @return a {@code BigFraction} instance with the resulting values. * @throws NullPointerException if the {@link BigInteger} is {@code null}. */ public BigFraction subtract(final BigInteger bg) { if (bg == null) { throw new NullPointerException(); } return new BigFraction(numerator.subtract(denominator.multiply(bg)), denominator); } /** ** Subtracts the value of an integer from the value of this one, * returning the result in reduced form. *
* * @param i * the integer to subtract. * @return aBigFraction
instance with the resulting values.
*/
public BigFraction subtract(final int i) {
return subtract(BigInteger.valueOf(i));
}
/**
* * Subtracts the value of an integer from the value of this one, * returning the result in reduced form. *
* * @param l * the long to subtract. * @return aBigFraction
instance with the resulting values, or
* this object if the long is zero.
*/
public BigFraction subtract(final long l) {
return subtract(BigInteger.valueOf(l));
}
/**
* * Subtracts the value of another fraction from the value of this one, * returning the result in reduced form. *
* * @param fraction {@link BigFraction} to subtract, must not be {@code null}. * @return a {@link BigFraction} instance with the resulting values * @throws NullPointerException if the {@code fraction} is {@code null}. */ public BigFraction subtract(final BigFraction fraction) { if (fraction == null) { throw new NullPointerException(LocalizedFormats.FRACTION.getSourceString()); } if (ZERO.equals(fraction)) { return this; } BigInteger num = null; BigInteger den = null; if (denominator.equals(fraction.denominator)) { num = numerator.subtract(fraction.numerator); den = denominator; } else { num = (numerator.multiply(fraction.denominator)).subtract((fraction.numerator).multiply(denominator)); den = denominator.multiply(fraction.denominator); } return new BigFraction(num, den); } /** *
* Returns the String
representing this fraction, ie
* "num / dem" or just "num" if the denominator is one.
*