You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2020/04/21 19:56:32 UTC
[commons-numbers] branch master updated: NUMBERS-147: Fix
conversion from double to support 2^31
This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
The following commit(s) were added to refs/heads/master by this push:
new ae6a5e3 NUMBERS-147: Fix conversion from double to support 2^31
ae6a5e3 is described below
commit ae6a5e39b4e4c424959fbfdd9dc13aa05c3e3517
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Thu Apr 16 22:32:15 2020 +0100
NUMBERS-147: Fix conversion from double to support 2^31
The value 2^31 can be in the numerator or denominator. Previously the
conversion from double supported up to Integer.MAX_VALUE which is
2^31-1.
Adds common test cases for conversion from double with a max
denominator.
Changed the conversion from a double to use the absolute value and
restore the sign at the end. The conversion is thus identical for
positive or negative values.
Throw an illegal argument exception if maxDenominator is zero. A zero
invalidates the conversion from a double with a restricted denominator.
Replace Math.abs with compareUnsigned. This is appropriate as the fraction p/q is
always positive.
Add test cases for overflow double conversions.
Fix the fall-back to always use p1/q1 when either p2 or q2 overflow.
Move the default max iterations to a constant.
Validate epsilon and max iterations are positive.
---
.../commons/numbers/fraction/BigFraction.java | 98 ++++++++++++-----
.../apache/commons/numbers/fraction/Fraction.java | 119 +++++++++++++++------
.../commons/numbers/fraction/BigFractionTest.java | 45 ++++++--
.../commons/numbers/fraction/CommonTestCases.java | 90 ++++++++++++++++
.../commons/numbers/fraction/FractionTest.java | 41 +++++--
5 files changed, 314 insertions(+), 79 deletions(-)
diff --git a/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/BigFraction.java b/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/BigFraction.java
index 996899f..a172d44 100644
--- a/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/BigFraction.java
+++ b/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/BigFraction.java
@@ -47,9 +47,15 @@ public final class BigFraction
/** Serializable version identifier. */
private static final long serialVersionUID = 20190701L;
+ /** The default iterations used for convergence. */
+ private static final int DEFAULT_MAX_ITERATIONS = 100;
+
/** Message for non-finite input double argument to factory constructors. */
private static final String NOT_FINITE = "Not finite: ";
+ /** The overflow limit for conversion from a double (2^31). */
+ private static final long OVERFLOW = 1L << 31;
+
/** The numerator of this fraction reduced to lowest terms. */
private final BigInteger numerator;
@@ -142,21 +148,28 @@ public final class BigFraction
return ZERO;
}
- final long overflow = Integer.MAX_VALUE;
- double r0 = value;
+ // Remove sign, this is restored at the end.
+ // (Assumes the value is not zero and thus signum(value) is not zero).
+ final double absValue = Math.abs(value);
+ double r0 = absValue;
long a0 = (long) Math.floor(r0);
-
- if (Math.abs(a0) > overflow) {
- throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, a0, 1L);
+ if (a0 > OVERFLOW) {
+ throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, a0, 1);
}
- // check for (almost) integer arguments, which should not go
- // to iterations.
- if (Math.abs(a0 - value) <= epsilon) {
- return new BigFraction(BigInteger.valueOf(a0),
- BigInteger.ONE);
+ // check for (almost) integer arguments, which should not go to iterations.
+ if (r0 - a0 <= epsilon) {
+ // Restore the sign.
+ if (value < 0) {
+ a0 = -a0;
+ }
+ return new BigFraction(BigInteger.valueOf(a0));
}
+ // Support 2^31 as maximum denominator.
+ // This is negative as an integer so convert to long.
+ final long maxDen = Math.abs((long) maxDenominator);
+
long p0 = 1;
long q0 = 0;
long p1 = a0;
@@ -169,16 +182,16 @@ public final class BigFraction
boolean stop = false;
do {
++n;
- final double r1 = 1d / (r0 - a0);
+ final double r1 = 1.0 / (r0 - a0);
final long a1 = (long) Math.floor(r1);
p2 = (a1 * p1) + p0;
q2 = (a1 * q1) + q0;
- if (p2 > overflow ||
- q2 > overflow) {
- // in maxDenominator mode, if the last fraction was very close to the actual value
- // q2 may overflow in the next iteration; in this case return the last one.
- if (epsilon == 0 &&
- Math.abs(q1) < maxDenominator) {
+ if (Long.compareUnsigned(p2, OVERFLOW) > 0 ||
+ Long.compareUnsigned(q2, OVERFLOW) > 0) {
+ // In maxDenominator mode, fall-back to the previous valid fraction.
+ if (epsilon == 0) {
+ p2 = p1;
+ q2 = q1;
break;
}
throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, p2, q2);
@@ -186,8 +199,8 @@ public final class BigFraction
final double convergent = (double) p2 / (double) q2;
if (n < maxIterations &&
- Math.abs(convergent - value) > epsilon &&
- q2 < maxDenominator) {
+ Math.abs(convergent - absValue) > epsilon &&
+ q2 < maxDen) {
p0 = p1;
p1 = p2;
q0 = q1;
@@ -203,11 +216,24 @@ public final class BigFraction
throw new FractionException(FractionException.ERROR_CONVERSION, value, maxIterations);
}
- return q2 < maxDenominator ?
- new BigFraction(BigInteger.valueOf(p2),
- BigInteger.valueOf(q2)) :
- new BigFraction(BigInteger.valueOf(p1),
- BigInteger.valueOf(q1));
+ // Use p2 / q2 or p1 / q1 if q2 has grown too large in maxDenominator mode
+ long num;
+ long den;
+ if (q2 <= maxDen) {
+ num = p2;
+ den = q2;
+ } else {
+ num = p1;
+ den = q1;
+ }
+
+ // Restore the sign.
+ if (Math.signum(num) * Math.signum(den) != Math.signum(value)) {
+ num = -num;
+ }
+
+ return new BigFraction(BigInteger.valueOf(num),
+ BigInteger.valueOf(den));
}
/**
@@ -290,18 +316,26 @@ public final class BigFraction
* @param epsilon Maximum error allowed. The resulting fraction is within
* {@code epsilon} of {@code value}, in absolute terms.
* @param maxIterations Maximum number of convergents.
- * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
+ * @throws IllegalArgumentException if the given {@code value} is NaN or infinite;
+ * {@code epsilon} is not positive; or {@code maxIterations < 1}.
* @throws ArithmeticException if the continued fraction failed to converge.
* @return a new instance.
*/
public static BigFraction from(final double value,
final double epsilon,
final int maxIterations) {
- return from(value, epsilon, Integer.MAX_VALUE, maxIterations);
+ if (maxIterations < 1) {
+ throw new IllegalArgumentException("Max iterations must be strictly positive: " + maxIterations);
+ }
+ if (epsilon >= 0) {
+ return from(value, epsilon, Integer.MIN_VALUE, maxIterations);
+ }
+ throw new IllegalArgumentException("Epsilon must be positive: " + maxIterations);
}
/**
* Create a fraction given the double value and maximum denominator.
+ *
* <p>
* References:
* <ul>
@@ -309,15 +343,23 @@ public final class BigFraction
* Continued Fraction</a> equations (11) and (22)-(26)</li>
* </ul>
*
+ * <p>Note: The magnitude of the {@code maxDenominator} is used allowing use of
+ * {@link Integer#MIN_VALUE} for a supported maximum denominator of 2<sup>31</sup>.
+ *
* @param value Value to convert to a fraction.
* @param maxDenominator Maximum allowed value for denominator.
- * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
+ * @throws IllegalArgumentException if the given {@code value} is NaN or infinite
+ * or {@code maxDenominator} is zero.
* @throws ArithmeticException if the continued fraction failed to converge.
* @return a new instance.
*/
public static BigFraction from(final double value,
final int maxDenominator) {
- return from(value, 0, maxDenominator, 100);
+ if (maxDenominator == 0) {
+ // Re-use the zero denominator message
+ throw new IllegalArgumentException(FractionException.ERROR_ZERO_DENOMINATOR);
+ }
+ return from(value, 0, maxDenominator, DEFAULT_MAX_ITERATIONS);
}
/**
diff --git a/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/Fraction.java b/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/Fraction.java
index 1974f1e..f1bc542 100644
--- a/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/Fraction.java
+++ b/commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/Fraction.java
@@ -47,9 +47,15 @@ public final class Fraction
/** The default epsilon used for convergence. */
private static final double DEFAULT_EPSILON = 1e-5;
+ /** The default iterations used for convergence. */
+ private static final int DEFAULT_MAX_ITERATIONS = 100;
+
/** Message for non-finite input double argument to factory constructors. */
private static final String NOT_FINITE = "Not finite: ";
+ /** The overflow limit for conversion from a double (2^31). */
+ private static final long OVERFLOW = 1L << 31;
+
/** The numerator of this fraction reduced to lowest terms. */
private final int numerator;
@@ -136,7 +142,11 @@ public final class Fraction
* https://issues.apache.org/jira/browse/MATH-181
* </p>
*
- * @param value Value to convert to a fraction.
+ * <p>
+ * Warning: This conversion assumes the value is not zero.
+ * </p>
+ *
+ * @param value Value to convert to a fraction. Must not be zero.
* @param epsilon Maximum error allowed.
* The resulting fraction is within {@code epsilon} of {@code value},
* in absolute terms.
@@ -153,20 +163,36 @@ public final class Fraction
throw new IllegalArgumentException(NOT_FINITE + value);
}
- final long overflow = Integer.MAX_VALUE;
- double r0 = value;
- long a0 = (long)Math.floor(r0);
- if (Math.abs(a0) > overflow) {
- throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, a0, 1L);
+ // Remove sign, this is restored at the end.
+ // (Assumes the value is not zero and thus signum(value) is not zero).
+ final double absValue = Math.abs(value);
+ double r0 = absValue;
+ long a0 = (long) Math.floor(r0);
+ if (a0 > OVERFLOW) {
+ throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, a0, 1);
}
// check for (almost) integer arguments, which should not go to iterations.
- if (Math.abs(a0 - value) <= epsilon) {
- this.numerator = (int) a0;
- this.denominator = 1;
+ if (r0 - a0 <= epsilon) {
+ int num = (int) a0;
+ int den = 1;
+ // Restore the sign.
+ if (Math.signum(num) != Math.signum(value)) {
+ if (num == Integer.MIN_VALUE) {
+ den = -den;
+ } else {
+ num = -num;
+ }
+ }
+ this.numerator = num;
+ this.denominator = den;
return;
}
+ // Support 2^31 as maximum denominator.
+ // This is negative as an integer so convert to long.
+ final long maxDen = Math.abs((long) maxDenominator);
+
long p0 = 1;
long q0 = 0;
long p1 = a0;
@@ -180,25 +206,25 @@ public final class Fraction
do {
++n;
final double r1 = 1.0 / (r0 - a0);
- final long a1 = (long)Math.floor(r1);
+ final long a1 = (long) Math.floor(r1);
p2 = (a1 * p1) + p0;
q2 = (a1 * q1) + q0;
- if (Math.abs(p2) > overflow ||
- Math.abs(q2) > overflow) {
- // in maxDenominator mode, if the last fraction was very close to the actual value
- // q2 may overflow in the next iteration; in this case return the last one.
- if (epsilon == 0.0 &&
- Math.abs(q1) < maxDenominator) {
+ if (Long.compareUnsigned(p2, OVERFLOW) > 0 ||
+ Long.compareUnsigned(q2, OVERFLOW) > 0) {
+ // In maxDenominator mode, fall-back to the previous valid fraction.
+ if (epsilon == 0.0) {
+ p2 = p1;
+ q2 = q1;
break;
}
throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, p2, q2);
}
- final double convergent = (double)p2 / (double)q2;
+ final double convergent = (double) p2 / (double) q2;
if (n < maxIterations &&
- Math.abs(convergent - value) > epsilon &&
- q2 < maxDenominator) {
+ Math.abs(convergent - absValue) > epsilon &&
+ q2 < maxDen) {
p0 = p1;
p1 = p2;
q0 = q1;
@@ -214,13 +240,30 @@ public final class Fraction
throw new FractionException(FractionException.ERROR_CONVERSION, value, maxIterations);
}
- if (q2 < maxDenominator) {
- this.numerator = (int) p2;
- this.denominator = (int) q2;
+ // Use p2 / q2 or p1 / q1 if q2 has grown too large in maxDenominator mode
+ // Note: Conversion of long 2^31 to an integer will create a negative. This could
+ // be either the numerator or denominator. This is handled by restoring the sign.
+ int num;
+ int den;
+ if (q2 <= maxDen) {
+ num = (int) p2;
+ den = (int) q2;
} else {
- this.numerator = (int) p1;
- this.denominator = (int) q1;
+ num = (int) p1;
+ den = (int) q1;
}
+
+ // Restore the sign.
+ if (Math.signum(num) * Math.signum(den) != Math.signum(value)) {
+ if (num == Integer.MIN_VALUE) {
+ den = -den;
+ } else {
+ num = -num;
+ }
+ }
+
+ this.numerator = num;
+ this.denominator = den;
}
/**
@@ -228,12 +271,11 @@ public final class Fraction
*
* @param value Value to convert to a fraction.
* @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
- * @throws ArithmeticException if the continued fraction failed to
- * converge.
+ * @throws ArithmeticException if the continued fraction failed to converge.
* @return a new instance.
*/
public static Fraction from(final double value) {
- return from(value, DEFAULT_EPSILON, 100);
+ return from(value, DEFAULT_EPSILON, DEFAULT_MAX_ITERATIONS);
}
/**
@@ -250,7 +292,8 @@ public final class Fraction
* @param epsilon Maximum error allowed. The resulting fraction is within
* {@code epsilon} of {@code value}, in absolute terms.
* @param maxIterations Maximum number of convergents.
- * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
+ * @throws IllegalArgumentException if the given {@code value} is NaN or infinite;
+ * {@code epsilon} is not positive; or {@code maxIterations < 1}.
* @throws ArithmeticException if the continued fraction failed to converge.
* @return a new instance.
*/
@@ -260,7 +303,13 @@ public final class Fraction
if (value == 0) {
return ZERO;
}
- return new Fraction(value, epsilon, Integer.MAX_VALUE, maxIterations);
+ if (maxIterations < 1) {
+ throw new IllegalArgumentException("Max iterations must be strictly positive: " + maxIterations);
+ }
+ if (epsilon >= 0) {
+ return new Fraction(value, epsilon, Integer.MIN_VALUE, maxIterations);
+ }
+ throw new IllegalArgumentException("Epsilon must be positive: " + maxIterations);
}
/**
@@ -273,9 +322,13 @@ public final class Fraction
* Continued Fraction</a> equations (11) and (22)-(26)</li>
* </ul>
*
+ * <p>Note: The magnitude of the {@code maxDenominator} is used allowing use of
+ * {@link Integer#MIN_VALUE} for a supported maximum denominator of 2<sup>31</sup>.
+ *
* @param value Value to convert to a fraction.
* @param maxDenominator Maximum allowed value for denominator.
- * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
+ * @throws IllegalArgumentException if the given {@code value} is NaN or infinite
+ * or {@code maxDenominator} is zero.
* @throws ArithmeticException if the continued fraction failed to converge.
* @return a new instance.
*/
@@ -284,7 +337,11 @@ public final class Fraction
if (value == 0) {
return ZERO;
}
- return new Fraction(value, 0, maxDenominator, 100);
+ if (maxDenominator == 0) {
+ // Re-use the zero denominator message
+ throw new IllegalArgumentException(FractionException.ERROR_ZERO_DENOMINATOR);
+ }
+ return new Fraction(value, 0, maxDenominator, DEFAULT_MAX_ITERATIONS);
}
/**
diff --git a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/BigFractionTest.java b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/BigFractionTest.java
index add8efd..f0bcd27 100644
--- a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/BigFractionTest.java
+++ b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/BigFractionTest.java
@@ -146,23 +146,29 @@ public class BigFractionTest {
}
// MATH-181
+ // NUMBERS-147
@Test
public void testDoubleConstructorWithMaxDenominator() throws Exception {
- assertFraction(2, 5, BigFraction.from(0.4, 9));
- assertFraction(2, 5, BigFraction.from(0.4, 99));
- assertFraction(2, 5, BigFraction.from(0.4, 999));
+ for (final CommonTestCases.DoubleToFractionTestCase testCase : CommonTestCases.doubleMaxDenomConstructorTestCases()) {
+ assertFraction(
+ testCase.expectedNumerator,
+ testCase.expectedDenominator,
+ BigFraction.from(testCase.operand, testCase.maxDenominator)
+ );
+ }
- assertFraction(3, 5, BigFraction.from(0.6152, 9));
- assertFraction(8, 13, BigFraction.from(0.6152, 99));
- assertFraction(510, 829, BigFraction.from(0.6152, 999));
- assertFraction(769, 1250, BigFraction.from(0.6152, 9999));
+ // Cases with different exact results from Fraction
+ final long pow31 = 1L << 31;
+ assertFraction(pow31, 1, BigFraction.from(Integer.MIN_VALUE * -1.0, 2));
+ assertFraction(pow31, 3, BigFraction.from(Integer.MIN_VALUE / -3.0, 10));
+ assertFraction(-1, pow31, BigFraction.from(1.0 / Integer.MIN_VALUE, Integer.MIN_VALUE));
+ assertFraction(1, pow31, BigFraction.from(-1.0 / Integer.MIN_VALUE, Integer.MIN_VALUE));
- // MATH-996
- assertFraction(1, 2, BigFraction.from(0.5000000001, 10));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> BigFraction.from(1.0, 0));
}
@Test
- public void testDoubleConstructorThrowsWithNonFinite() {
+ public void testDoubleConstructorThrows() {
final double eps = 1e-5;
final int maxIterations = Integer.MAX_VALUE;
final int maxDenominator = Integer.MAX_VALUE;
@@ -171,6 +177,11 @@ public class BigFractionTest {
Assertions.assertThrows(IllegalArgumentException.class, () -> BigFraction.from(value, eps, maxIterations));
Assertions.assertThrows(IllegalArgumentException.class, () -> BigFraction.from(value, maxDenominator));
}
+ Assertions.assertThrows(IllegalArgumentException.class, () -> BigFraction.from(1.0, Double.NaN, maxIterations));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> BigFraction.from(1.0, -1.0, maxIterations));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> BigFraction.from(1.0, eps, 0));
+ // Test a zero epsilon is allowed
+ assertFraction(1, 1, BigFraction.from(1.0, 0, maxIterations));
}
@Test
@@ -193,6 +204,20 @@ public class BigFractionTest {
}
@Test
+ public void testDoubleConstructorOverflow() {
+ assertDoubleConstructorOverflow(0.75000000001455192);
+ assertDoubleConstructorOverflow(1.0e10);
+ assertDoubleConstructorOverflow(-1.0e10);
+ assertDoubleConstructorOverflow(-43979.60679604749);
+ }
+
+ private void assertDoubleConstructorOverflow(final double a) {
+ Assertions.assertThrows(ArithmeticException.class,
+ () -> BigFraction.from(a, 1.0e-12, 1000)
+ );
+ }
+
+ @Test
public void testDoubleConstructorWithEpsilonLimit() throws Exception {
assertFraction(2, 5, BigFraction.from(0.4, 1.0e-5, 100));
diff --git a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/CommonTestCases.java b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/CommonTestCases.java
index 59bd68e..d6e58dc 100644
--- a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/CommonTestCases.java
+++ b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/CommonTestCases.java
@@ -38,6 +38,11 @@ final class CommonTestCases {
private static final List<DoubleToFractionTestCase> doubleConstructorTestCasesList;
/**
+ * See {@link #doubleMaxDenomConstructorTestCases()}
+ */
+ private static final List<DoubleToFractionTestCase> doubleMaxDenomConstructorTestCasesList;
+
+ /**
* See {@link #absTestCases()}
*/
private static final List<UnaryOperatorTestCase> absTestCasesList;
@@ -100,6 +105,7 @@ final class CommonTestCases {
static {
numDenConstructorTestCasesList = collectNumDenConstructorTestCases();
doubleConstructorTestCasesList = collectDoubleConstructorTestCases();
+ doubleMaxDenomConstructorTestCasesList = collectDoubleMaxDenomConstructorTestCases();
absTestCasesList = collectAbsTestCases();
reciprocalTestCasesList = collectReciprocalTestCases();
negateTestCasesList = collectNegateTestCases();
@@ -206,6 +212,63 @@ final class CommonTestCases {
}
/**
+ * Defines test cases as described in
+ * {@link #doubleMaxDenomConstructorTestCases()} and collects them into a {@code List}.
+ * @return a list of test cases as described above
+ */
+ private static List<DoubleToFractionTestCase> collectDoubleMaxDenomConstructorTestCases() {
+ final List<DoubleToFractionTestCase> testCases = new ArrayList<>();
+ testCases.add(new DoubleToFractionTestCase(0.4, 9, 2, 5));
+ testCases.add(new DoubleToFractionTestCase(0.4, 99, 2, 5));
+ testCases.add(new DoubleToFractionTestCase(0.4, 999, 2, 5));
+ testCases.add(new DoubleToFractionTestCase(-0.4, 9, -2, 5));
+ testCases.add(new DoubleToFractionTestCase(-0.4, 99, -2, 5));
+ testCases.add(new DoubleToFractionTestCase(-0.4, 999, -2, 5));
+
+ testCases.add(new DoubleToFractionTestCase(0.6152, 9, 3, 5));
+ testCases.add(new DoubleToFractionTestCase(0.6152, 99, 8, 13));
+ testCases.add(new DoubleToFractionTestCase(0.6152, 999, 510, 829));
+ testCases.add(new DoubleToFractionTestCase(0.6152, 9999, 769, 1250));
+ testCases.add(new DoubleToFractionTestCase(-0.6152, 9, -3, 5));
+ testCases.add(new DoubleToFractionTestCase(-0.6152, 99, -8, 13));
+ testCases.add(new DoubleToFractionTestCase(-0.6152, 999, -510, 829));
+ testCases.add(new DoubleToFractionTestCase(-0.6152, 9999, -769, 1250));
+
+ // Underflow
+ testCases.add(new DoubleToFractionTestCase(0x1.0p-40, Integer.MAX_VALUE, 0, 1));
+ testCases.add(new DoubleToFractionTestCase(-0x1.0p-40, Integer.MAX_VALUE, 0, 1));
+
+ // Overflow
+ testCases.add(new DoubleToFractionTestCase(Math.nextUp((double) Integer.MAX_VALUE), Integer.MIN_VALUE, Integer.MAX_VALUE, 1));
+ testCases.add(new DoubleToFractionTestCase(-Math.nextUp((double) Integer.MAX_VALUE), Integer.MIN_VALUE, -Integer.MAX_VALUE, 1));
+ testCases.add(new DoubleToFractionTestCase(Math.nextUp((double) Integer.MAX_VALUE) / (1 << 15), Integer.MIN_VALUE, Integer.MAX_VALUE, 1 << 15));
+ testCases.add(new DoubleToFractionTestCase(-Math.nextUp((double) Integer.MAX_VALUE) / (1 << 15), Integer.MIN_VALUE, -Integer.MAX_VALUE, 1 << 15));
+ testCases.add(new DoubleToFractionTestCase(Math.nextUp(1.0), Integer.MIN_VALUE, 1, 1));
+ testCases.add(new DoubleToFractionTestCase(-Math.nextUp(1.0), Integer.MIN_VALUE, -1, 1));
+
+ // MATH-996
+ testCases.add(new DoubleToFractionTestCase(0.5000000001, 10, 1, 2));
+ testCases.add(new DoubleToFractionTestCase(-0.5000000001, 10, -1, 2));
+
+ // NUMBERS-147
+ testCases.add(new DoubleToFractionTestCase(Integer.MAX_VALUE * 1.0, 2, Integer.MAX_VALUE, 1));
+ testCases.add(new DoubleToFractionTestCase(Integer.MAX_VALUE * -1.0, 2, -Integer.MAX_VALUE, 1));
+ testCases.add(new DoubleToFractionTestCase(1.0 / Integer.MAX_VALUE, Integer.MAX_VALUE, 1, Integer.MAX_VALUE));
+ testCases.add(new DoubleToFractionTestCase(-1.0 / Integer.MAX_VALUE, Integer.MAX_VALUE, -1, Integer.MAX_VALUE));
+ testCases.add(new DoubleToFractionTestCase(Integer.MIN_VALUE * 1.0, 2, Integer.MIN_VALUE, 1));
+
+ // Using 2^31:
+ // Representations in Fraction and BigFraction are different since BigFraction
+ // can use +2^31 but Fraction is limited to -2^31
+ // .from(Integer.MIN_VALUE * -1.0, 2)
+ // .from(Integer.MIN_VALUE / -3.0, Integer.MIN_VALUE)
+ // .from(1.0 / Integer.MIN_VALUE, Integer.MIN_VALUE)
+ // .from(-1.0 / Integer.MIN_VALUE, Integer.MIN_VALUE)
+
+ return testCases;
+ }
+
+ /**
* Defines test cases as described in {@link #absTestCases()} and
* collects them into a {@code List}.
* @return a list of test cases as described above
@@ -528,6 +591,8 @@ final class CommonTestCases {
* allowed, and the expected numerator and denominator of the resulting
* fraction are in the {@code int} range.
*
+ * <p>The maximum denominator in the test cases will be zero and should be ignored.
+ *
* @return a list of test cases as described above
*/
static List<DoubleToFractionTestCase> doubleConstructorTestCases() {
@@ -535,6 +600,18 @@ final class CommonTestCases {
}
/**
+ * Provides a list of test cases where a {@code double} value should be
+ * converted to a fraction with a specified maximum denominator, and the
+ * expected numerator and denominator of the resulting fraction are in the
+ * {@code int} range.
+ *
+ * @return a list of test cases as described above
+ */
+ static List<DoubleToFractionTestCase> doubleMaxDenomConstructorTestCases() {
+ return Collections.unmodifiableList(doubleMaxDenomConstructorTestCasesList);
+ }
+
+ /**
* Provides a list of test cases where the absolute value of a fraction
* created from a specified numerator and denominator, both in the {@code
* int} range, should be calculated, and the expected numerator and
@@ -791,19 +868,32 @@ final class CommonTestCases {
* should be performed on a {@code double} value and the numerator and
* denominator of the expected result
* are in the {@code int} range.
+ *
+ * <p>Optionally captures a maximum denominator. This will be zero if
+ * not required in the test case.
*/
static class DoubleToFractionTestCase {
final double operand;
+ final int maxDenominator;
final int expectedNumerator;
final int expectedDenominator;
DoubleToFractionTestCase(
double operand,
+ int maxDenominator,
int expectedNumerator,
int expectedDenominator) {
this.operand = operand;
+ this.maxDenominator = maxDenominator;
this.expectedNumerator = expectedNumerator;
this.expectedDenominator = expectedDenominator;
}
+
+ DoubleToFractionTestCase(
+ double operand,
+ int expectedNumerator,
+ int expectedDenominator) {
+ this(operand, 0, expectedNumerator, expectedDenominator);
+ }
}
}
diff --git a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/FractionTest.java b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/FractionTest.java
index 80628fa..f26a616 100644
--- a/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/FractionTest.java
+++ b/commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/FractionTest.java
@@ -99,23 +99,28 @@ public class FractionTest {
}
// MATH-181
+ // NUMBERS-147
@Test
public void testDoubleConstructorWithMaxDenominator() throws Exception {
- assertFraction(2, 5, Fraction.from(0.4, 9));
- assertFraction(2, 5, Fraction.from(0.4, 99));
- assertFraction(2, 5, Fraction.from(0.4, 999));
+ for (final CommonTestCases.DoubleToFractionTestCase testCase : CommonTestCases.doubleMaxDenomConstructorTestCases()) {
+ assertFraction(
+ testCase.expectedNumerator,
+ testCase.expectedDenominator,
+ Fraction.from(testCase.operand, testCase.maxDenominator)
+ );
+ }
- assertFraction(3, 5, Fraction.from(0.6152, 9));
- assertFraction(8, 13, Fraction.from(0.6152, 99));
- assertFraction(510, 829, Fraction.from(0.6152, 999));
- assertFraction(769, 1250, Fraction.from(0.6152, 9999));
+ // Cases with different exact results from BigFraction
+ assertFraction(Integer.MIN_VALUE, -1, Fraction.from(Integer.MIN_VALUE * -1.0, 2));
+ assertFraction(Integer.MIN_VALUE, -3, Fraction.from(Integer.MIN_VALUE / -3.0, 10));
+ assertFraction(1, Integer.MIN_VALUE, Fraction.from(1.0 / Integer.MIN_VALUE, Integer.MIN_VALUE));
+ assertFraction(-1, Integer.MIN_VALUE, Fraction.from(-1.0 / Integer.MIN_VALUE, Integer.MIN_VALUE));
- // MATH-996
- assertFraction(1, 2, Fraction.from(0.5000000001, 10));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> Fraction.from(1.0, 0));
}
@Test
- public void testDoubleConstructorThrowsWithNonFinite() {
+ public void testDoubleConstructorThrows() {
final double eps = 1e-5;
final int maxIterations = Integer.MAX_VALUE;
final int maxDenominator = Integer.MAX_VALUE;
@@ -124,6 +129,11 @@ public class FractionTest {
Assertions.assertThrows(IllegalArgumentException.class, () -> Fraction.from(value, eps, maxIterations));
Assertions.assertThrows(IllegalArgumentException.class, () -> Fraction.from(value, maxDenominator));
}
+ Assertions.assertThrows(IllegalArgumentException.class, () -> Fraction.from(1.0, Double.NaN, maxIterations));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> Fraction.from(1.0, -1.0, maxIterations));
+ Assertions.assertThrows(IllegalArgumentException.class, () -> Fraction.from(1.0, eps, 0));
+ // Test a zero epsilon is allowed
+ assertFraction(1, 1, Fraction.from(1.0, 0, maxIterations));
}
@Test
@@ -134,6 +144,17 @@ public class FractionTest {
);
}
+ // MATH-1029
+ @Test
+ public void testDoubleConstructorWithMaxDenominatorOverFlow() {
+ Assertions.assertThrows(ArithmeticException.class,
+ () -> Fraction.from(1e10, 1000)
+ );
+ Assertions.assertThrows(ArithmeticException.class,
+ () -> Fraction.from(-1e10, 1000)
+ );
+ }
+
@Test
public void testDoubleConstructorOverflow() {
assertDoubleConstructorOverflow(0.75000000001455192);