You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by ps...@apache.org on 2004/07/12 01:20:17 UTC
cvs commit: jakarta-commons/lang/src/test/org/apache/commons/lang/math FractionTest.java
psteitz 2004/07/11 16:20:17
Modified: lang/src/java/org/apache/commons/lang/math Fraction.java
lang/src/test/org/apache/commons/lang/math FractionTest.java
Log:
Fixed numeric problems reported in PR #29294
Submitted by: C. Scott Ananian
Reviewed by: Phil Steitz
Revision Changes Path
1.14 +274 -109 jakarta-commons/lang/src/java/org/apache/commons/lang/math/Fraction.java
Index: Fraction.java
===================================================================
RCS file: /home/cvs/jakarta-commons/lang/src/java/org/apache/commons/lang/math/Fraction.java,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -r1.13 -r1.14
--- Fraction.java 18 Feb 2004 22:56:13 -0000 1.13
+++ Fraction.java 11 Jul 2004 23:20:17 -0000 1.14
@@ -16,6 +16,7 @@
package org.apache.commons.lang.math;
import java.io.Serializable;
+import java.math.BigInteger;
/**
* <p><code>Fraction</code> is a <code>Number</code> implementation that
@@ -28,6 +29,7 @@
* @author Stephen Colebourne
* @author Tim O'Brien
* @author Pete Gieser
+ * @author C. Scott Ananian
* @since 2.0
* @version $Id$
*/
@@ -137,6 +139,10 @@
throw new ArithmeticException("The denominator must not be zero");
}
if (denominator < 0) {
+ if (numerator==Integer.MIN_VALUE ||
+ denominator==Integer.MIN_VALUE) {
+ throw new ArithmeticException("overflow: can't negate");
+ }
numerator = -numerator;
denominator = -denominator;
}
@@ -154,7 +160,7 @@
* @param denominator the denominator, for example the seven in 'one and three sevenths'
* @return a new fraction instance
* @throws ArithmeticException if the denomiator is <code>zero</code>
- * @throws ArithmeticException if the denomiator is negative
+ * @throws ArithmeticException if the denominator is negative
* @throws ArithmeticException if the numerator is negative
* @throws ArithmeticException if the resulting numerator exceeds
* <code>Integer.MAX_VALUE</code>
@@ -169,13 +175,14 @@
if (numerator < 0) {
throw new ArithmeticException("The numerator must not be negative");
}
- double numeratorValue = 0;
+ long numeratorValue;
if (whole < 0) {
- numeratorValue = (double) whole * denominator - numerator;
+ numeratorValue = whole * (long)denominator - numerator;
} else {
- numeratorValue = (double) whole * denominator + numerator;
+ numeratorValue = whole * (long)denominator + numerator;
}
- if (Math.abs(numeratorValue) > Integer.MAX_VALUE) {
+ if (numeratorValue < Integer.MIN_VALUE ||
+ numeratorValue > Integer.MAX_VALUE) {
throw new ArithmeticException("Numerator too large to represent as an Integer.");
}
return new Fraction((int) numeratorValue, denominator);
@@ -190,18 +197,32 @@
* @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 denomiator is <code>zero</code>
+ * @throws ArithmeticException if the denominator is <code>zero</code>
*/
public static Fraction getReducedFraction(int numerator, int denominator) {
if (denominator == 0) {
throw new ArithmeticException("The denominator must not be zero");
}
+ 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 new ArithmeticException("overflow: can't negate");
+ }
numerator = -numerator;
denominator = -denominator;
}
- int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
- return new Fraction(numerator / gcd, denominator / gcd);
+ // simplify fraction.
+ int gcd = greatestCommonDivisor(numerator, denominator);
+ numerator /= gcd;
+ denominator /= gcd;
+ return new Fraction(numerator, denominator);
}
/**
@@ -215,7 +236,7 @@
* @return a new fraction instance that is close to the value
* @throws ArithmeticException if <code>|value| > Integer.MAX_VALUE</code>
* or <code>value = NaN</code>
- * @throws ArithmeticException if the calculated denomiator is <code>zero</code>
+ * @throws ArithmeticException if the calculated denominator is <code>zero</code>
* @throws ArithmeticException if the the algorithm does not converge
*/
public static Fraction getFraction(double value) {
@@ -275,11 +296,11 @@
*
* <p>The formats accepted are:</p>
*
- * <p>
* <ol>
* <li><code>double</code> String containing a dot</li>
* <li>'X Y/Z'</li>
* <li>'Y/Z'</li>
+ * <li>'X' (a simple whole number)</li>
* </ol>
* and a .</p>
*
@@ -307,11 +328,9 @@
if (pos < 0) {
throw new NumberFormatException("The fraction could not be parsed as the format X Y/Z");
} else {
+ int numer = Integer.parseInt(str.substring(0, pos));
int denom = Integer.parseInt(str.substring(pos + 1));
- return getFraction(
- Integer.parseInt(str.substring(0, pos)) + whole * denom,
- denom
- );
+ return getFraction(whole, numer, denom);
}
}
@@ -321,10 +340,9 @@
// simple whole number
return getFraction(Integer.parseInt(str), 1);
} else {
- return getFraction(
- Integer.parseInt(str.substring(0, pos)),
- Integer.parseInt(str.substring(pos + 1))
- );
+ int numer = Integer.parseInt(str.substring(0, pos));
+ int denom = Integer.parseInt(str.substring(pos + 1));
+ return getFraction(numer, denom);
}
}
@@ -440,18 +458,26 @@
}
/**
- * <p>Gets a fraction that is the invert (1/fraction) of this one.</p>
- *
+ * <p>Gets a fraction that is the inverse (1/fraction) of this one.</p>
+ *
* <p>The returned fraction is not reduced.</p>
*
- * @return a new fraction instance with the numerator and denominator inverted
- * @throws ArithmeticException if the numerator is <code>zero</code>
+ * @return a new fraction instance with the numerator and denominator
+ * inverted.
+ * @throws ArithmeticException if the fraction represents zero.
*/
public Fraction invert() {
if (numerator == 0) {
- throw new ArithmeticException("Unable to invert a fraction with a zero numerator");
+ throw new ArithmeticException("Unable to invert zero.");
+ }
+ if (numerator==Integer.MIN_VALUE) {
+ throw new ArithmeticException("overflow: can't negate numerator");
+ }
+ if (numerator<0) {
+ return new Fraction(-denominator, -numerator);
+ } else {
+ return new Fraction(denominator, numerator);
}
- return getFraction(denominator, numerator);
}
/**
@@ -462,12 +488,16 @@
* @return a new fraction instance with the opposite signed numerator
*/
public Fraction negate() {
- return getFraction(-numerator, denominator);
+ // the positive range is one smaller than the negative range of an int.
+ if (numerator==Integer.MIN_VALUE) {
+ throw new ArithmeticException("overflow: too large to negate");
+ }
+ return new Fraction(-numerator, denominator);
}
/**
* <p>Gets a fraction that is the positive equivalent of this one.</p>
- * <p>More precisely: <pre>(fraction >= 0 ? this : -fraction)</pre></p>
+ * <p>More precisely: <code>(fraction >= 0 ? this : -fraction)</code></p>
*
* <p>The returned fraction is not reduced.</p>
*
@@ -478,13 +508,13 @@
if (numerator >= 0) {
return this;
}
- return getFraction(-numerator, denominator);
+ return negate();
}
/**
* <p>Gets a fraction that is raised to the passed in power.</p>
*
- * <p>The returned fraction is not reduced.</p>
+ * <p>The returned fraction is in reduced form.</p>
*
* @param power the power to raise the fraction to
* @return <code>this</code> if the power is one, <code>ONE</code> if the power
@@ -498,44 +528,150 @@
return this;
} else if (power == 0) {
return ONE;
- } else {
- double denominatorValue = Math.pow(denominator, power);
- double numeratorValue = Math.pow(numerator, power);
- if (numeratorValue > Integer.MAX_VALUE || denominatorValue > Integer.MAX_VALUE) {
- throw new ArithmeticException("Integer overflow");
+ } else if (power < 0) {
+ if (power==Integer.MIN_VALUE) { // MIN_VALUE can't be negated.
+ return this.invert().pow(2).pow(-(power/2));
}
- if (power < 0) {
- return getFraction((int) Math.pow(denominator, -power),
- (int) Math.pow(numerator, -power));
+ return this.invert().pow(-power);
+ } else {
+ Fraction f = this.multiplyBy(this);
+ if ((power % 2) == 0) { // if even...
+ return f.pow(power/2);
+ } else { // if odd...
+ return f.pow(power/2).multiplyBy(this);
}
- return getFraction((int) Math.pow(numerator, power),
- (int) Math.pow(denominator, power));
}
}
/**
- * <p>Gets the greatest common divisor of two numbers.</p>
+ * <p>Gets the greatest common divisor of the absolute value of
+ * two numbers, using the "binary gcd" method which avoids
+ * division and modulo operations. See Knuth 4.5.2 algorithm B.
+ * This algorithm is due to Josef Stein (1961).</p>
*
- * @param number1 a positive number
- * @param number2 a positive number
+ * @param u a non-zero number
+ * @param v a non-zero number
* @return the greatest common divisor, never zero
*/
- private static int greatestCommonDivisor(int number1, int number2) {
- int remainder = number1 % number2;
- while (remainder != 0) {
- number1 = number2;
- number2 = remainder;
- remainder = number1 % number2;
- }
- return number2;
+ private static int greatestCommonDivisor(int u, int v) {
+ // keep u and v negative, as negative integers range down to
+ // -2^31, while positive numbers can only be as large as 2^31-1
+ // (i.e. we can't necessarily negate a negative number without
+ // overflow)
+ /* assert u!=0 && v!=0; */
+ if (u>0) { u=-u; } // make u negative
+ if (v>0) { v=-v; } // make v negative
+ // B1. [Find power of 2]
+ int k=0;
+ while ((u&1)==0 && (v&1)==0 && k<31) { // while u and v are both even...
+ u/=2; v/=2; k++; // cast out twos.
+ }
+ if (k==31) {
+ throw new ArithmeticException("overflow: gcd is 2^31");
+ }
+ // B2. Initialize: u and v have been divided by 2^k and at least
+ // one is odd.
+ int t = ((u&1)==1) ? v : -(u/2)/*B3*/;
+ // t negative: u was odd, v may be even (t replaces v)
+ // t positive: u was even, v is odd (t replaces u)
+ do {
+ /* assert u<0 && v<0; */
+ // B4/B3: cast out twos from t.
+ while ((t&1)==0) { // while t is even..
+ t/=2; // cast out twos
+ }
+ // B5 [reset max(u,v)]
+ if (t>0) {
+ u = -t;
+ } else {
+ v = t;
+ }
+ // B6/B3. at this point both u and v should be odd.
+ t = (v - u)/2;
+ // |u| larger: t positive (replace u)
+ // |v| larger: t negative (replace v)
+ } while (t!=0);
+ return -u*(1<<k); // gcd is u*2^k
}
// Arithmetic
//-------------------------------------------------------------------
+ /**
+ * Multiply two integers, checking for overflow.
+ *
+ * @param x a factor
+ * @param y a factor
+ * @return the product <code>x*y</code>
+ * @throws ArithmeticException if the result can not be represented as
+ * an int
+ */
+ private static int mulAndCheck(int x, int y) {
+ long m = ((long)x)*((long)y);
+ if (m < Integer.MIN_VALUE ||
+ m > Integer.MAX_VALUE) {
+ throw new ArithmeticException("overflow: mul");
+ }
+ return (int)m;
+ }
+
+ /**
+ * Multiply two non-negative integers, checking for overflow.
+ *
+ * @param x a non-negative factor
+ * @param y a non-negative factor
+ * @return the product <code>x*y</code>
+ * @throws ArithmeticException if the result can not be represented as
+ * an int
+ */
+ private static int mulPosAndCheck(int x, int y) {
+ /* assert x>=0 && y>=0; */
+ long m = ((long)x)*((long)y);
+ if (m > Integer.MAX_VALUE) {
+ throw new ArithmeticException("overflow: mulPos");
+ }
+ return (int)m;
+ }
+
+ /**
+ * Add two integers, checking for overflow.
+ *
+ * @param x an addend
+ * @param y an addend
+ * @return the sum <code>x+y</code>
+ * @throws ArithmeticException if the result can not be represented as
+ * an int
+ */
+ private static int addAndCheck(int x, int y) {
+ long s = (long)x+(long)y;
+ if (s < Integer.MIN_VALUE ||
+ s > Integer.MAX_VALUE) {
+ throw new ArithmeticException("overflow: add");
+ }
+ return (int)s;
+ }
+
+ /**
+ * Subtract two integers, checking for overflow.
+ *
+ * @param x the minuend
+ * @param y the subtrahend
+ * @return the difference <code>x-y</code>
+ * @throws ArithmeticException if the result can not be represented as
+ * an int
+ */
+ private static int subAndCheck(int x, int y) {
+ long s = (long)x-(long)y;
+ if (s < Integer.MIN_VALUE ||
+ s > Integer.MAX_VALUE) {
+ throw new ArithmeticException("overflow: add");
+ }
+ return (int)s;
+ }
+
/**
- * <p>Adds the value of this fraction to another, returning the result in
- * reduced form.</p>
+ * <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
@@ -544,48 +680,82 @@
* <code>Integer.MAX_VALUE</code>
*/
public Fraction add(Fraction fraction) {
- if (fraction == null) {
- throw new IllegalArgumentException("The fraction must not be null");
- }
- if (numerator == 0) {
- return fraction;
- }
- if (fraction.numerator == 0) {
- return this;
- }
- // Compute lcd explicitly to limit overflow
- int gcd = greatestCommonDivisor(Math.abs(fraction.denominator), Math.abs(denominator));
- int thisResidue = denominator/gcd;
- int thatResidue = fraction.denominator/gcd;
- double denominatorValue = Math.abs((double) gcd * thisResidue * thatResidue);
- double numeratorValue = (double) numerator * thatResidue + fraction.numerator * thisResidue;
- if (Math.abs(numeratorValue) > Integer.MAX_VALUE ||
- Math.abs(denominatorValue) > Integer.MAX_VALUE) {
- throw new ArithmeticException("Integer overflow");
- }
- return Fraction.getReducedFraction((int) numeratorValue, (int) denominatorValue);
+ return addSub(fraction, true /* add */);
}
/**
- * <p>Subtracts the value of another fraction from the value of this one,
+ * <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 exceeds
- * <code>Integer.MAX_VALUE</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 */);
+ }
+
+ /**
+ * 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 IllegalArgumentException("The fraction must not be null");
}
- return add(fraction.negate());
+ // 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 = greatestCommonDivisor(denominator, fraction.denominator);
+ if (d1==1) {
+ // result is ( (u*v' +/- u'v) / u'v')
+ int uvp = mulAndCheck(numerator, fraction.denominator);
+ int upv = mulAndCheck(fraction.numerator, denominator);
+ return new Fraction
+ (isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv),
+ mulPosAndCheck(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:greatestCommonDivisor(tmodd1, d1);
+
+ // result is (t/d2) / (u'/d1)(v'/d2)
+ BigInteger w = t.divide(BigInteger.valueOf(d2));
+ if (w.bitLength() > 31) {
+ throw new ArithmeticException
+ ("overflow: numerator too large after multiply");
+ }
+ return new Fraction
+ (w.intValue(),
+ mulPosAndCheck(denominator/d1, fraction.denominator/d2));
}
/**
- * <p>Multiplies the value of this fraction by another, returning the result
- * in reduced form.</p>
+ * <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
@@ -600,18 +770,17 @@
if (numerator == 0 || fraction.numerator == 0) {
return ZERO;
}
- double numeratorValue = (double) numerator * fraction.numerator;
- double denominatorValue = (double) denominator * fraction.denominator;
- if (Math.abs(numeratorValue) > Integer.MAX_VALUE ||
- Math.abs(denominatorValue) > Integer.MAX_VALUE) {
- throw new ArithmeticException("Integer overflow");
- }
- return getReducedFraction((int) numeratorValue, (int) denominatorValue);
+ // knuth 4.5.1
+ // make sure we don't overflow unless the result *must* overflow.
+ int d1 = greatestCommonDivisor(numerator, fraction.denominator);
+ int d2 = greatestCommonDivisor(fraction.numerator, denominator);
+ return getReducedFraction
+ (mulAndCheck(numerator/d1, fraction.numerator/d2),
+ mulPosAndCheck(denominator/d2, fraction.denominator/d1));
}
/**
- * <p>Divide the value of this fraction by another, returning the result
- * in reduced form.</p>
+ * <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
@@ -627,16 +796,7 @@
if (fraction.numerator == 0) {
throw new ArithmeticException("The fraction to divide by must not be zero");
}
- if (numerator == 0) {
- return ZERO;
- }
- double numeratorValue = (double) numerator * fraction.denominator;
- double denominatorValue = (double) denominator * fraction.numerator;
- if (Math.abs(numeratorValue) > Integer.MAX_VALUE ||
- Math.abs(denominatorValue) > Integer.MAX_VALUE) {
- throw new ArithmeticException("Integer overflow");
- }
- return getReducedFraction((int) numeratorValue, (int) denominatorValue);
+ return multiplyBy(fraction.invert());
}
// Basics
@@ -658,8 +818,8 @@
return false;
}
Fraction other = (Fraction) obj;
- return (numerator == other.numerator &&
- denominator == other.denominator);
+ return (getNumerator() == other.getNumerator() &&
+ getDenominator() == other.getDenominator());
}
/**
@@ -669,9 +829,8 @@
*/
public int hashCode() {
if (hashCode == 0) {
- hashCode = 17;
- hashCode = 37 * hashCode + numerator;
- hashCode = 37 * hashCode + denominator;
+ // hashcode update should be atomic.
+ hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator();
}
return hashCode;
}
@@ -686,6 +845,9 @@
*/
public int compareTo(Object object) {
Fraction other = (Fraction) object;
+ if (this==other) {
+ return 0;
+ }
if (numerator == other.numerator && denominator == other.denominator) {
return 0;
}
@@ -712,9 +874,9 @@
public String toString() {
if (toString == null) {
toString = new StringBuffer(32)
- .append(numerator)
+ .append(getNumerator())
.append('/')
- .append(denominator).toString();
+ .append(getDenominator()).toString();
}
return toString;
}
@@ -734,7 +896,11 @@
toProperString = "0";
} else if (numerator == denominator) {
toProperString = "1";
- } else if (Math.abs(numerator) > denominator) {
+ } else if ((numerator>0?-numerator:numerator) < -denominator) {
+ // note that we do the magnitude comparison test above with
+ // NEGATIVE (not positive) numbers, since negative numbers
+ // have a larger range. otherwise numerator==Integer.MIN_VALUE
+ // is handled incorrectly.
int properNumerator = getProperNumerator();
if (properNumerator == 0) {
toProperString = Integer.toString(getProperWhole());
@@ -742,15 +908,14 @@
toProperString = new StringBuffer(32)
.append(getProperWhole()).append(' ')
.append(properNumerator).append('/')
- .append(denominator).toString();
+ .append(getDenominator()).toString();
}
} else {
toProperString = new StringBuffer(32)
- .append(numerator).append('/')
- .append(denominator).toString();
+ .append(getNumerator()).append('/')
+ .append(getDenominator()).toString();
}
}
return toProperString;
}
-
}
1.7 +335 -17 jakarta-commons/lang/src/test/org/apache/commons/lang/math/FractionTest.java
Index: FractionTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons/lang/src/test/org/apache/commons/lang/math/FractionTest.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- FractionTest.java 18 Feb 2004 23:02:38 -0000 1.6
+++ FractionTest.java 11 Jul 2004 23:20:17 -0000 1.7
@@ -18,15 +18,21 @@
import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
/**
- * Test cases for the {@link Fraction} classes.
+ * Test cases for the {@link Fraction} class
*
* @author Stephen Colebourne
+ * @author C. Scott Ananian
* @version $Id$
*/
public class FractionTest extends TestCase {
- private static final int SKIP = 53;
+ private static final int SKIP = 500; //53
public FractionTest(String name) {
super(name);
@@ -80,7 +86,7 @@
assertEquals(4, Fraction.FOUR_FIFTHS.getNumerator());
assertEquals(5, Fraction.FOUR_FIFTHS.getDenominator());
}
-
+
public void testFactory_int_int() {
Fraction f = null;
@@ -139,6 +145,16 @@
f = Fraction.getFraction(-3, 0);
fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
+
+ // very large: can't represent as unsimplified fraction, although
+ try {
+ f = Fraction.getFraction(4, Integer.MIN_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+ try {
+ f = Fraction.getFraction(1, Integer.MIN_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
}
public void testFactory_int_int_int() {
@@ -223,8 +239,26 @@
f = Fraction.getFraction(-Integer.MAX_VALUE, 1, 2);
fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
- }
+ // very large
+ f = Fraction.getFraction(-1, 0, Integer.MAX_VALUE);
+ assertEquals(-Integer.MAX_VALUE, f.getNumerator());
+ assertEquals(Integer.MAX_VALUE, f.getDenominator());
+
+ try {
+ // negative denominators not allowed in this constructor.
+ f = Fraction.getFraction(0, 4, Integer.MIN_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+ try {
+ f = Fraction.getFraction(1, 1, Integer.MAX_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+ try {
+ f = Fraction.getFraction(-1, 2, Integer.MAX_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+ }
public void testReducedFactory_int_int() {
Fraction f = null;
@@ -296,6 +330,18 @@
f = Fraction.getReducedFraction(121, 22);
assertEquals(11, f.getNumerator());
assertEquals(2, f.getDenominator());
+
+ // Extreme values
+ // OK, can reduce before negating
+ f = Fraction.getReducedFraction(-2, Integer.MIN_VALUE);
+ assertEquals(1, f.getNumerator());
+ assertEquals(-(Integer.MIN_VALUE / 2), f.getDenominator());
+
+ // Can't reduce, negation will throw
+ try {
+ f = Fraction.getReducedFraction(-7, Integer.MIN_VALUE);
+ fail("Expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
}
public void testFactory_double() {
@@ -391,7 +437,7 @@
public void testFactory_String() {
try {
Fraction.getFraction(null);
- fail("expecting ArithmeticException");
+ fail("expecting IllegalArgumentException");
} catch (IllegalArgumentException ex) {}
}
@@ -417,6 +463,7 @@
try {
f = Fraction.getFraction("2.3R");
+ fail("Expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
@@ -426,6 +473,7 @@
try {
f = Fraction.getFraction(".");
+ fail("Expecting NumberFormatException");
} catch (NumberFormatException ex) {}
}
@@ -448,34 +496,42 @@
assertEquals(6, f.getNumerator());
assertEquals(4, f.getDenominator());
+ f = Fraction.getFraction("-7 1/2");
+ assertEquals(-15, f.getNumerator());
+ assertEquals(2, f.getDenominator());
+
+ f = Fraction.getFraction("-1 2/4");
+ assertEquals(-6, f.getNumerator());
+ assertEquals(4, f.getDenominator());
+
try {
f = Fraction.getFraction("2 3");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("a 3");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("2 b/4");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("2 ");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction(" 3");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction(" ");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
}
@@ -508,22 +564,22 @@
try {
f = Fraction.getFraction("2/d");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("2e/3");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("2/");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("/");
- fail("expecting NumberFomatException");
+ fail("expecting NumberFormatException");
} catch (NumberFormatException ex) {}
}
@@ -541,6 +597,12 @@
assertEquals(-3, f.getProperWhole());
assertEquals(5, f.getProperNumerator());
assertEquals(6, f.getDenominator());
+
+ f = Fraction.getFraction(Integer.MIN_VALUE, 0, 1);
+ assertEquals(Integer.MIN_VALUE, f.getNumerator());
+ assertEquals(Integer.MIN_VALUE, f.getProperWhole());
+ assertEquals(0, f.getProperNumerator());
+ assertEquals(1, f.getDenominator());
}
public void testConversions() {
@@ -560,6 +622,11 @@
f = f.reduce();
assertEquals(2, f.getNumerator());
assertEquals(3, f.getDenominator());
+
+ f = Fraction.getFraction(2, 3);
+ f = f.reduce();
+ assertEquals(2, f.getNumerator());
+ assertEquals(3, f.getDenominator());
}
public void testInvert() {
@@ -575,10 +642,28 @@
assertEquals(3, f.getNumerator());
assertEquals(4, f.getDenominator());
+ f = Fraction.getFraction(-15, 47);
+ f = f.invert();
+ assertEquals(-47, f.getNumerator());
+ assertEquals(15, f.getDenominator());
+
f = Fraction.getFraction(0, 3);
try {
f = f.invert();
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
+
+ // large values
+ f = Fraction.getFraction(Integer.MIN_VALUE, 1);
+ try {
+ f = f.invert();
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ f = Fraction.getFraction(Integer.MAX_VALUE, 1);
+ f = f.invert();
+ assertEquals(1, f.getNumerator());
+ assertEquals(Integer.MAX_VALUE, f.getDenominator());
}
public void testNegate() {
@@ -593,6 +678,18 @@
f = f.negate();
assertEquals(50, f.getNumerator());
assertEquals(75, f.getDenominator());
+
+ // large values
+ f = Fraction.getFraction(Integer.MAX_VALUE-1, Integer.MAX_VALUE);
+ f = f.negate();
+ assertEquals(Integer.MIN_VALUE+2, f.getNumerator());
+ assertEquals(Integer.MAX_VALUE, f.getDenominator());
+
+ f = Fraction.getFraction(Integer.MIN_VALUE, 1);
+ try {
+ f = f.negate();
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
}
public void testAbs() {
@@ -607,6 +704,22 @@
f = f.abs();
assertEquals(50, f.getNumerator());
assertEquals(75, f.getDenominator());
+
+ f = Fraction.getFraction(Integer.MAX_VALUE, 1);
+ f = f.abs();
+ assertEquals(Integer.MAX_VALUE, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
+ f = Fraction.getFraction(Integer.MAX_VALUE, -1);
+ f = f.abs();
+ assertEquals(Integer.MAX_VALUE, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
+ f = Fraction.getFraction(Integer.MIN_VALUE, 1);
+ try {
+ f = f.abs();
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
}
public void testPow() {
@@ -617,6 +730,7 @@
f = Fraction.getFraction(3, 5);
assertSame(f, f.pow(1));
+ assertEquals(f, f.pow(1));
f = Fraction.getFraction(3, 5);
f = f.pow(2);
@@ -638,7 +752,82 @@
assertEquals(25, f.getNumerator());
assertEquals(9, f.getDenominator());
- f = Fraction.getFraction(Integer.MAX_VALUE);
+ // check unreduced fractions stay that way.
+ f = Fraction.getFraction(6, 10);
+ assertEquals(Fraction.ONE, f.pow(0));
+
+ f = Fraction.getFraction(6, 10);
+ assertEquals(f, f.pow(1));
+ assertFalse(f.pow(1).equals(Fraction.getFraction(3,5)));
+
+ f = Fraction.getFraction(6, 10);
+ f = f.pow(2);
+ assertEquals(9, f.getNumerator());
+ assertEquals(25, f.getDenominator());
+
+ f = Fraction.getFraction(6, 10);
+ f = f.pow(3);
+ assertEquals(27, f.getNumerator());
+ assertEquals(125, f.getDenominator());
+
+ f = Fraction.getFraction(6, 10);
+ f = f.pow(-1);
+ assertEquals(10, f.getNumerator());
+ assertEquals(6, f.getDenominator());
+
+ f = Fraction.getFraction(6, 10);
+ f = f.pow(-2);
+ assertEquals(25, f.getNumerator());
+ assertEquals(9, f.getDenominator());
+
+ // zero to any positive power is still zero.
+ f = Fraction.getFraction(0, 1231);
+ f = f.pow(1);
+ assertTrue(0==f.compareTo(Fraction.ZERO));
+ assertEquals(0, f.getNumerator());
+ assertEquals(1231, f.getDenominator());
+ f = f.pow(2);
+ assertTrue(0==f.compareTo(Fraction.ZERO));
+ assertEquals(0, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
+ // zero to negative powers should throw an exception
+ try {
+ f = f.pow(-1);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+ try {
+ f = f.pow(Integer.MIN_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ // one to any power is still one.
+ f = Fraction.getFraction(1, 1);
+ f = f.pow(0);
+ assertEquals(f, Fraction.ONE);
+ f = f.pow(1);
+ assertEquals(f, Fraction.ONE);
+ f = f.pow(-1);
+ assertEquals(f, Fraction.ONE);
+ f = f.pow(Integer.MAX_VALUE);
+ assertEquals(f, Fraction.ONE);
+ f = f.pow(Integer.MIN_VALUE);
+ assertEquals(f, Fraction.ONE);
+
+ f = Fraction.getFraction(Integer.MAX_VALUE, 1);
+ try {
+ f = f.pow(2);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ // Numerator growing too negative during the pow operation.
+ f = Fraction.getFraction(Integer.MIN_VALUE, 1);
+ try {
+ f = f.pow(3);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ f = Fraction.getFraction(65536, 1);
try {
f = f.pow(2);
fail("expecting ArithmeticException");
@@ -699,11 +888,31 @@
f = f2.add(f1);
assertSame(f2, f);
+ f1 = Fraction.getFraction(-1, 13*13*2*2);
+ f2 = Fraction.getFraction(-2, 13*17*2);
+ f = f1.add(f2);
+ assertEquals(13*13*17*2*2, f.getDenominator());
+ assertEquals(-17 - 2*13*2, f.getNumerator());
+
try {
f.add(null);
fail("expecting IllegalArgumentException");
} catch (IllegalArgumentException ex) {}
+ // if this fraction is added naively, it will overflow.
+ // check that it doesn't.
+ f1 = Fraction.getFraction(1,32768*3);
+ f2 = Fraction.getFraction(1,59049);
+ f = f1.add(f2);
+ assertEquals(52451, f.getNumerator());
+ assertEquals(1934917632, f.getDenominator());
+
+ f1 = Fraction.getFraction(Integer.MIN_VALUE, 3);
+ f2 = Fraction.ONE_THIRD;
+ f = f1.add(f2);
+ assertEquals(Integer.MIN_VALUE+1, f.getNumerator());
+ assertEquals(3, f.getDenominator());
+
f1 = Fraction.getFraction(Integer.MAX_VALUE - 1, 1);
f2 = Fraction.ONE;
f = f1.add(f2);
@@ -715,12 +924,32 @@
fail("expecting ArithmeticException but got: " + f.toString());
} catch (ArithmeticException ex) {}
+ // denominator should not be a multiple of 2 or 3 to trigger overflow
+ f1 = Fraction.getFraction(Integer.MIN_VALUE, 5);
+ f2 = Fraction.getFraction(-1,5);
+ try {
+ f = f1.add(f2); // should overflow
+ fail("expecting ArithmeticException but got: " + f.toString());
+ } catch (ArithmeticException ex) {}
+
try {
f= Fraction.getFraction(-Integer.MAX_VALUE, 1);
f = f.add(f);
fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
+ try {
+ f= Fraction.getFraction(-Integer.MAX_VALUE, 1);
+ f = f.add(f);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ f1 = Fraction.getFraction(3,327680);
+ f2 = Fraction.getFraction(2,59049);
+ try {
+ f = f1.add(f2); // should overflow
+ fail("expecting ArithmeticException but got: " + f.toString());
+ } catch (ArithmeticException ex) {}
}
public void testSubtract() {
@@ -780,6 +1009,26 @@
fail("expecting IllegalArgumentException");
} catch (IllegalArgumentException ex) {}
+ // if this fraction is subtracted naively, it will overflow.
+ // check that it doesn't.
+ f1 = Fraction.getFraction(1,32768*3);
+ f2 = Fraction.getFraction(1,59049);
+ f = f1.subtract(f2);
+ assertEquals(-13085, f.getNumerator());
+ assertEquals(1934917632, f.getDenominator());
+
+ f1 = Fraction.getFraction(Integer.MIN_VALUE, 3);
+ f2 = Fraction.ONE_THIRD.negate();
+ f = f1.subtract(f2);
+ assertEquals(Integer.MIN_VALUE+1, f.getNumerator());
+ assertEquals(3, f.getDenominator());
+
+ f1 = Fraction.getFraction(Integer.MAX_VALUE, 1);
+ f2 = Fraction.ONE;
+ f = f1.subtract(f2);
+ assertEquals(Integer.MAX_VALUE-1, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
try {
f1 = Fraction.getFraction(1, Integer.MAX_VALUE);
f2 = Fraction.getFraction(1, Integer.MAX_VALUE - 1);
@@ -787,6 +1036,32 @@
fail("expecting ArithmeticException"); //should overflow
} catch (ArithmeticException ex) {}
+ // denominator should not be a multiple of 2 or 3 to trigger overflow
+ f1 = Fraction.getFraction(Integer.MIN_VALUE, 5);
+ f2 = Fraction.getFraction(1,5);
+ try {
+ f = f1.subtract(f2); // should overflow
+ fail("expecting ArithmeticException but got: " + f.toString());
+ } catch (ArithmeticException ex) {}
+
+ try {
+ f= Fraction.getFraction(Integer.MIN_VALUE, 1);
+ f = f.subtract(Fraction.ONE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ try {
+ f= Fraction.getFraction(Integer.MAX_VALUE, 1);
+ f = f.subtract(Fraction.ONE.negate());
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ f1 = Fraction.getFraction(3,327680);
+ f2 = Fraction.getFraction(2,59049);
+ try {
+ f = f1.subtract(f2); // should overflow
+ fail("expecting ArithmeticException but got: " + f.toString());
+ } catch (ArithmeticException ex) {}
}
public void testMultiply() {
@@ -800,6 +1075,15 @@
assertEquals(6, f.getNumerator());
assertEquals(25, f.getDenominator());
+ f1 = Fraction.getFraction(6, 10);
+ f2 = Fraction.getFraction(6, 10);
+ f = f1.multiplyBy(f2);
+ assertEquals(9, f.getNumerator());
+ assertEquals(25, f.getDenominator());
+ f = f.multiplyBy(f2);
+ assertEquals(27, f.getNumerator());
+ assertEquals(125, f.getDenominator());
+
f1 = Fraction.getFraction(3, 5);
f2 = Fraction.getFraction(-2, 5);
f = f1.multiplyBy(f2);
@@ -812,6 +1096,7 @@
assertEquals(6, f.getNumerator());
assertEquals(25, f.getDenominator());
+
f1 = Fraction.getFraction(0, 5);
f2 = Fraction.getFraction(2, 7);
f = f1.multiplyBy(f2);
@@ -823,6 +1108,12 @@
assertEquals(2, f.getNumerator());
assertEquals(7, f.getDenominator());
+ f1 = Fraction.getFraction(Integer.MAX_VALUE, 1);
+ f2 = Fraction.getFraction(Integer.MIN_VALUE, Integer.MAX_VALUE);
+ f = f1.multiplyBy(f2);
+ assertEquals(Integer.MIN_VALUE, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
try {
f.multiplyBy(null);
fail("expecting IllegalArgumentException");
@@ -875,6 +1166,12 @@
assertEquals(1, f.getNumerator());
assertEquals(1, f.getDenominator());
+ f1 = Fraction.getFraction(Integer.MIN_VALUE, Integer.MAX_VALUE);
+ f2 = Fraction.getFraction(1, Integer.MAX_VALUE);
+ f = f1.divideBy(f2);
+ assertEquals(Integer.MIN_VALUE, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
try {
f.divideBy(null);
fail("IllegalArgumentException");
@@ -932,6 +1229,7 @@
Fraction f2 = null;
f1 = Fraction.getFraction(3, 5);
+ assertTrue(f1.compareTo(f1) == 0);
try {
f1.compareTo(null);
@@ -945,15 +1243,24 @@
f2 = Fraction.getFraction(2, 5);
assertTrue(f1.compareTo(f2) > 0);
+ assertTrue(f2.compareTo(f2) == 0);
f2 = Fraction.getFraction(4, 5);
assertTrue(f1.compareTo(f2) < 0);
+ assertTrue(f2.compareTo(f2) == 0);
f2 = Fraction.getFraction(3, 5);
assertTrue(f1.compareTo(f2) == 0);
+ assertTrue(f2.compareTo(f2) == 0);
f2 = Fraction.getFraction(6, 10);
assertTrue(f1.compareTo(f2) == 0);
+ assertTrue(f2.compareTo(f2) == 0);
+
+ f2 = Fraction.getFraction(-1, 1, Integer.MAX_VALUE);
+ assertTrue(f1.compareTo(f2) > 0);
+ assertTrue(f2.compareTo(f2) == 0);
+
}
public void testToString() {
@@ -975,6 +1282,12 @@
f = Fraction.getFraction(2, 2);
assertEquals("2/2", f.toString());
+
+ f = Fraction.getFraction(Integer.MIN_VALUE, 0, 1);
+ assertEquals("-2147483648/1", f.toString());
+
+ f = Fraction.getFraction(-1, 1, Integer.MAX_VALUE);
+ assertEquals("-2147483648/2147483647", f.toString());
}
public void testToProperString() {
@@ -1002,6 +1315,11 @@
f = Fraction.getFraction(-7, 5);
assertEquals("-1 2/5", f.toProperString());
+
+ f = Fraction.getFraction(Integer.MIN_VALUE, 0, 1);
+ assertEquals("-2147483648", f.toProperString());
+
+ f = Fraction.getFraction(-1, 1, Integer.MAX_VALUE);
+ assertEquals("-1 1/2147483647", f.toProperString());
}
-
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org