scolebourne 2003/08/13 16:42:17
Modified: lang/src/test/org/apache/commons/lang/math FractionTest.java
lang/src/java/org/apache/commons/lang/math Fraction.java
Log:
Improve Fraction Javadoc, implementation and tests
bug 22386, from Phil Steitz
Revision Changes Path
1.4 +144 -3
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.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- FractionTest.java 4 Aug 2003 02:01:53 -0000 1.3
+++ FractionTest.java 13 Aug 2003 23:42:17 -0000 1.4
@@ -64,7 +64,7 @@
*/
public class FractionTest extends TestCase {
- private static final int SKIP = 17;
+ private static final int SKIP = 53;
public FractionTest(String name) {
super(name);
@@ -165,14 +165,17 @@
// zero denominator
try {
f = Fraction.getFraction(1, 0);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(2, 0);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(-3, 0);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
}
@@ -200,14 +203,17 @@
// negatives
try {
f = Fraction.getFraction(1, -6, -10);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(1, -6, -10);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(1, -6, -10);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
// negative whole
@@ -217,27 +223,43 @@
try {
f = Fraction.getFraction(-1, -6, 10);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(-1, 6, -10);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(-1, -6, -10);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
// zero denominator
try {
f = Fraction.getFraction(0, 1, 0);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(1, 2, 0);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(-1, -3, 0);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ try {
+ f = Fraction.getFraction(Integer.MAX_VALUE, 1, 2);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ try {
+ f = Fraction.getFraction(-Integer.MAX_VALUE, 1, 2);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
}
@@ -279,14 +301,17 @@
// zero denominator
try {
f = Fraction.getReducedFraction(1, 0);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getReducedFraction(2, 0);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getReducedFraction(-3, 0);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
// reduced
@@ -316,14 +341,22 @@
try {
f = Fraction.getFraction(Double.NaN);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(Double.POSITIVE_INFINITY);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
try {
f = Fraction.getFraction(Double.NEGATIVE_INFINITY);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ try {
+ f = Fraction.getFraction((double) Integer.MAX_VALUE + 1);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
// zero
@@ -377,7 +410,7 @@
assertEquals(f2.getDenominator(), f.getDenominator());
}
}
- // save time by skipping some tests!
+ // save time by skipping some tests! (
for (int i = 1001; i <= 10000; i+=SKIP) { // denominator
for (int j = 1; j <= i; j++) { // numerator
try {
@@ -396,9 +429,11 @@
public void testFactory_String() {
try {
Fraction.getFraction(null);
+ fail("expecting ArithmeticException");
} catch (IllegalArgumentException ex) {}
}
+
public void testFactory_String_double() {
Fraction f = null;
@@ -423,6 +458,11 @@
} catch (NumberFormatException ex) {}
try {
+ f = Fraction.getFraction("2147483648"); // too big
+ fail("Expecting NumberFormatException");
+ } catch (NumberFormatException ex) {}
+
+ try {
f = Fraction.getFraction(".");
} catch (NumberFormatException ex) {}
}
@@ -448,26 +488,32 @@
try {
f = Fraction.getFraction("2 3");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("a 3");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("2 b/4");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("2 ");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction(" 3");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction(" ");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
}
@@ -500,18 +546,22 @@
try {
f = Fraction.getFraction("2/d");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("2e/3");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("2/");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
try {
f = Fraction.getFraction("/");
+ fail("expecting NumberFomatException");
} catch (NumberFormatException ex) {}
}
@@ -625,6 +675,12 @@
f = f.pow(-2);
assertEquals(25, f.getNumerator());
assertEquals(9, f.getDenominator());
+
+ f = Fraction.getFraction(Integer.MAX_VALUE);
+ try {
+ f = f.pow(2);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
}
public void testAdd() {
@@ -656,12 +712,24 @@
assertEquals(-1, f.getNumerator());
assertEquals(5, f.getDenominator());
+ f1 = Fraction.getFraction(Integer.MAX_VALUE - 1, 1);
+ f2 = Fraction.ONE;
+ f = f1.add(f2);
+ assertEquals(Integer.MAX_VALUE, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
f1 = Fraction.getFraction(3, 5);
f2 = Fraction.getFraction(1, 2);
f = f1.add(f2);
assertEquals(11, f.getNumerator());
assertEquals(10, f.getDenominator());
+ f1 = Fraction.getFraction(3, 8);
+ f2 = Fraction.getFraction(1, 6);
+ f = f1.add(f2);
+ assertEquals(13, f.getNumerator());
+ assertEquals(24, f.getDenominator());
+
f1 = Fraction.getFraction(0, 5);
f2 = Fraction.getFraction(1, 5);
f = f1.add(f2);
@@ -671,7 +739,26 @@
try {
f.add(null);
+ fail("expecting IllegalArgumentException");
} catch (IllegalArgumentException ex) {}
+
+ f1 = Fraction.getFraction(Integer.MAX_VALUE - 1, 1);
+ f2 = Fraction.ONE;
+ f = f1.add(f2);
+ assertEquals(Integer.MAX_VALUE, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
+ try {
+ f = f.add(Fraction.ONE); // 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) {}
+
}
public void testSubtract() {
@@ -728,7 +815,16 @@
try {
f.subtract(null);
+ fail("expecting IllegalArgumentException");
} catch (IllegalArgumentException ex) {}
+
+ try {
+ f1 = Fraction.getFraction(1, Integer.MAX_VALUE);
+ f2 = Fraction.getFraction(1, Integer.MAX_VALUE - 1);
+ f = f1.subtract(f2);
+ fail("expecting ArithmeticException"); //should overflow
+ } catch (ArithmeticException ex) {}
+
}
public void testMultiply() {
@@ -759,9 +855,28 @@
f = f1.multiplyBy(f2);
assertSame(Fraction.ZERO, f);
+ f1 = Fraction.getFraction(2, 7);
+ f2 = Fraction.ONE;
+ f = f1.multiplyBy(f2);
+ assertEquals(2, f.getNumerator());
+ assertEquals(7, f.getDenominator());
+
try {
f.multiplyBy(null);
+ fail("expecting IllegalArgumentException");
} catch (IllegalArgumentException ex) {}
+
+ try {
+ f1 = Fraction.getFraction(1, Integer.MAX_VALUE);
+ f = f1.multiplyBy(f1); // should overflow
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+
+ try {
+ f1 = Fraction.getFraction(1, -Integer.MAX_VALUE);
+ f = f1.multiplyBy(f1); // should overflow
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
}
public void testDivide() {
@@ -779,6 +894,7 @@
f2 = Fraction.ZERO;
try {
f = f1.divideBy(f2);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException ex) {}
f1 = Fraction.getFraction(0, 5);
@@ -786,9 +902,32 @@
f = f1.divideBy(f2);
assertSame(Fraction.ZERO, f);
+ f1 = Fraction.getFraction(2, 7);
+ f2 = Fraction.ONE;
+ f = f1.divideBy(f2);
+ assertEquals(2, f.getNumerator());
+ assertEquals(7, f.getDenominator());
+
+ f1 = Fraction.getFraction(1, Integer.MAX_VALUE);
+ f = f1.divideBy(f1);
+ assertEquals(1, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
try {
f.divideBy(null);
+ fail("IllegalArgumentException");
} catch (IllegalArgumentException ex) {}
+
+ try {
+ f1 = Fraction.getFraction(1, Integer.MAX_VALUE);
+ f = f1.divideBy(f1.invert()); // should overflow
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
+ try {
+ f1 = Fraction.getFraction(1, -Integer.MAX_VALUE);
+ f = f1.divideBy(f1.invert()); // should overflow
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException ex) {}
}
public void testEquals() {
@@ -834,10 +973,12 @@
try {
f1.compareTo(null);
+ fail("expecting NullPointerException");
} catch (NullPointerException ex) {}
try {
f1.compareTo(new Object());
+ fail("expecting ClassCastException");
} catch (ClassCastException ex) {}
f2 = Fraction.getFraction(2, 5);
1.9 +84 -67
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.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- Fraction.java 4 Aug 2003 02:01:53 -0000 1.8
+++ Fraction.java 13 Aug 2003 23:42:17 -0000 1.9
@@ -161,6 +161,8 @@
* @throws ArithmeticException if the denomiator is <code>zero</code>
* @throws ArithmeticException if the denomiator is negative
* @throws ArithmeticException if the numerator is negative
+ * @throws ArithmeticException if the resulting numerator exceeds
+ * <code>Integer.MAX_VALUE</code>
*/
public static Fraction getFraction(int whole, int numerator, int denominator) {
if (denominator == 0) {
@@ -172,12 +174,16 @@
if (numerator < 0) {
throw new ArithmeticException("The numerator must not be negative");
}
+ double numeratorValue = 0;
if (whole < 0) {
- numerator = whole * denominator - numerator;
+ numeratorValue = (double) whole * denominator - numerator;
} else {
- numerator = whole * denominator + numerator;
+ numeratorValue = (double) whole * denominator + numerator;
}
- return new Fraction(numerator, denominator);
+ if (Math.abs(numeratorValue) > Integer.MAX_VALUE) {
+ throw new ArithmeticException("Numerator too large to represent as an
Integer.");
+ }
+ return new Fraction((int) numeratorValue, denominator);
}
/**
@@ -199,30 +205,34 @@
numerator = -numerator;
denominator = -denominator;
}
- int gcd = greatestCommonDenominator(Math.abs(numerator), denominator);
+ int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
return new Fraction(numerator / gcd, denominator / gcd);
}
/**
* <p>Creates a <code>Fraction</code> instance from a <code>double</code>
value.</p>
*
- * <p>This method uses the continued fraction algorithm.</p>
+ * <p>This method uses the <a
href="http://archives.math.utk.edu/articles/atuyl/confrac/";>
+ * continued fraction algorithm</a>, computing a maximum of
+ * 25 convergents and bounding the denominator by 10,000.</p>
*
* @param value the double value to convert
* @return a new fraction instance that is close to the value
- * @throws ArithmeticException if the value is infinite or <code>NaN</code>
+ * @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 the algorithm does not converge
*/
public static Fraction getFraction(double value) {
- if (Double.isInfinite(value) || Double.isNaN(value)) {
- throw new ArithmeticException("The value must not be infinite or NaN");
- }
int sign = (value < 0 ? -1 : 1);
value = Math.abs(value);
+ if (value > Integer.MAX_VALUE || Double.isNaN(value)) {
+ throw new ArithmeticException
+ ("The value must not be greater than Integer.MAX_VALUE or NaN");
+ }
int wholeNumber = (int) value;
value -= wholeNumber;
-
- // http://archives.math.utk.edu/articles/atuyl/confrac/
+
int numer0 = 0; // the pre-previous
int denom0 = 1; // the pre-previous
int numer1 = 1; // the previous
@@ -430,7 +440,7 @@
* @return a new reduce fraction instance, or this if no simplification possible
*/
public Fraction reduce() {
- int gcd = greatestCommonDenominator(Math.abs(numerator), denominator);
+ int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
return Fraction.getFraction(numerator / gcd, denominator / gcd);
}
@@ -483,27 +493,39 @@
*
* @param power the power to raise the fraction to
* @return <code>this</code> if the power is one, <code>ONE</code> if the power
- * is zero or a new fraction instance raised to the appropriate power
+ * is zero (even if the fraction equals ZERO) or a new fraction instance
+ * raised to the appropriate power
+ * @throws ArithmeticException if the resulting numerator or denominator exceeds
+ * <code>Integer.MAX_VALUE</code>
*/
public Fraction pow(int power) {
if (power == 1) {
return this;
} else if (power == 0) {
return ONE;
- } else if (power < 0) {
- return getFraction((int) Math.pow(denominator, -power), (int)
Math.pow(numerator, -power));
+ } 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");
+ }
+ if (power < 0) {
+ return getFraction((int) Math.pow(denominator, -power),
+ (int) Math.pow(numerator, -power));
+ }
+ return getFraction((int) Math.pow(numerator, power),
+ (int) Math.pow(denominator, power));
}
- return getFraction((int) Math.pow(numerator, power), (int)
Math.pow(denominator, power));
}
/**
- * <p>Gets the greatest common denominator of two numbers.</p>
+ * <p>Gets the greatest common divisor of two numbers.</p>
*
* @param number1 a positive number
* @param number2 a positive number
- * @return the greatest common denominator, never zero
+ * @return the greatest common divisor, never zero
*/
- private static int greatestCommonDenominator(int number1, int number2) {
+ private static int greatestCommonDivisor(int number1, int number2) {
int remainder = number1 % number2;
while (remainder != 0) {
number1 = number2;
@@ -517,15 +539,14 @@
//-------------------------------------------------------------------
/**
- * <p>Adds the value of this fraction to another, returning the result.</p>
- *
- * <p>The implementation spots common cases of zero numerators and equal
- * denominators. Otherwise, it uses <code>(a/b) + (c/d) = (a*d + b*c) /
(b*d)</code>
- * and then reduces the result.</p>
+ * <p>Adds the value of this fraction to another, returning the result in
+ * reduced form.</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) {
if (fraction == null) {
@@ -536,56 +557,46 @@
}
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");
}
- if (denominator == fraction.denominator) {
- return getReducedFraction(numerator + fraction.numerator, denominator);
- }
- return getReducedFraction(
- numerator * fraction.denominator + denominator * fraction.numerator,
- denominator * fraction.denominator
- );
+ return Fraction.getReducedFraction((int) numeratorValue, (int)
denominatorValue);
}
/**
* <p>Subtracts the value of another fraction from the value of this one,
- * returning the result.</p>
- *
- * <p>The implementation spots common cases of zero numerators and equal
- * denominators. Otherwise, it uses <code>(a/b) - (c/d) = (a*d - b*c) /
(b*d)</code>
- * and then reduces the result.</p>
+ * 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>
*/
public Fraction subtract(Fraction fraction) {
if (fraction == null) {
throw new IllegalArgumentException("The fraction must not be null");
}
- if (numerator == 0) {
- return fraction.negate();
- }
- if (fraction.numerator == 0) {
- return this;
- }
- if (denominator == fraction.denominator) {
- return getReducedFraction(numerator - fraction.numerator, denominator);
- }
- return getReducedFraction(
- numerator * fraction.denominator - denominator * fraction.numerator,
- denominator * fraction.denominator
- );
+ return add(fraction.negate());
}
/**
- * <p>Multiplies the value of this fraction by another, returning the
result.</p>
- *
- * <p>The implementation uses <code>(a/b)*(c/d) = (a*c)/(b*d)</code>
- * and then reduces the result.</p>
+ * <p>Multiplies the value of this fraction by another, returning the result
+ * in reduced form.</p>
*
* @param fraction the fraction to multipy 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 multiplyBy(Fraction fraction) {
if (fraction == null) {
@@ -594,22 +605,25 @@
if (numerator == 0 || fraction.numerator == 0) {
return ZERO;
}
- return getReducedFraction(
- numerator * fraction.numerator,
- denominator * fraction.denominator
- );
+ 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);
}
/**
- * <p>Divide the value of this fraction by another, returning the result.</p>
- *
- * <p>The implementation uses <code>(a/b)/(c/d) = a/b * d/c = (a*d)/(b*c)</code>
- * and then reduces the result.</p>
+ * <p>Divide the value of this fraction by another, returning the result
+ * in reduced form.</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 divideBy(Fraction fraction) {
if (fraction == null) {
@@ -620,11 +634,14 @@
}
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(
- numerator * fraction.denominator,
- denominator * fraction.numerator
- );
+ return getReducedFraction((int) numeratorValue, (int) denominatorValue);
}
// Basics
@@ -668,7 +685,7 @@
* <p>Compares this object to another based on size.</p>
*
* @param object the object to compare to
- * @return -ve if this is less, 0 if equal, +ve if greater
+ * @return -1 if this is less, 0 if equal, +1 if greater
* @throws ClassCastException if the object is not a <code>Fraction</code>
* @throws NullPointerException if the object is <code>null</code>
*/
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
