You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ea...@apache.org on 2019/06/07 04:05:12 UTC
[commons-numbers] 01/01: Merge branch 'master' of
http://gitbox.apache.org/repos/asf/commons-numbers into
eax/simple-migrate-map
This is an automated email from the ASF dual-hosted git repository.
eax pushed a commit to branch eax/simple-migrate-map
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
commit 8508164a4135167a41be3f9645db8f9cf3448007
Merge: a28928f 7a3f962
Author: Eitan Adler <li...@eitanadler.com>
AuthorDate: Thu Jun 6 21:04:19 2019 -0700
Merge branch 'master' of http://gitbox.apache.org/repos/asf/commons-numbers into eax/simple-migrate-map
.../commons/numbers/fraction/AbstractFormat.java | 205 -----------
.../commons/numbers/fraction/BigFraction.java | 366 +++++++++----------
.../numbers/fraction/BigFractionFormat.java | 282 ---------------
.../apache/commons/numbers/fraction/Fraction.java | 318 ++++++++---------
.../commons/numbers/fraction/FractionFormat.java | 260 --------------
.../numbers/fraction/ProperBigFractionFormat.java | 233 ------------
.../numbers/fraction/ProperFractionFormat.java | 225 ------------
.../numbers/fraction/BigFractionFormatTest.java | 332 -----------------
.../commons/numbers/fraction/BigFractionTest.java | 391 +++++++++++----------
.../numbers/fraction/FractionFormatTest.java | 350 ------------------
.../commons/numbers/fraction/FractionTest.java | 378 ++++++++++----------
11 files changed, 721 insertions(+), 2619 deletions(-)
diff --cc commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/BigFraction.java
index be45cc0,eedb910..476972b
--- 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
@@@ -26,16 -26,7 +26,7 @@@ import org.apache.commons.numbers.core.
* Representation of a rational number without any overflow. This class is
* immutable.
*/
- public class BigFraction
- extends Number
- implements Comparable<BigFraction>, Serializable {
-
- /** A fraction representing "2 / 1". */
- public static final BigFraction TWO = new BigFraction(2);
-
- /** A fraction representing "1". */
- public static final BigFraction ONE = new BigFraction(1);
-
-public class BigFraction extends Number implements Comparable<BigFraction>, Serializable {
++public class BigFraction extends Number implements Comparable<BigFraction>, Serializable {
/** A fraction representing "0". */
public static final BigFraction ZERO = new BigFraction(0);
@@@ -328,8 -189,143 +189,143 @@@
denominator = BigInteger.valueOf(q1);
}
}
-
+
/**
+ * Create a fraction given the double value.
+ * <p>
+ * This constructor behaves <em>differently</em> from
+ * {@link #BigFraction(double, double, int)}. It converts the double value
+ * exactly, considering its internal bits representation. This works for all
+ * values except NaN and infinities and does not requires any loop or
+ * convergence threshold.
+ * </p>
+ * <p>
+ * Since this conversion is exact and since double numbers are sometimes
+ * approximated, the fraction created may seem strange in some cases. For example,
+ * calling <code>new BigFraction(1.0 / 3.0)</code> does <em>not</em> 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).
+ * </p>
+ * @see #BigFraction(double, double, int)
+ * @param value the double value to convert to a fraction.
+ * @exception IllegalArgumentException if value is NaN or infinite
+ */
+ private BigFraction(final double value) throws IllegalArgumentException {
+ if (Double.isNaN(value)) {
+ throw new IllegalArgumentException("cannot convert NaN value");
+ }
+ if (Double.isInfinite(value)) {
+ throw new IllegalArgumentException("cannot convert infinite value");
+ }
+
+ // compute m and k such that value = m * 2^k
+ final long bits = Double.doubleToLongBits(value);
+ final long sign = bits & 0x8000000000000000L;
+ final long exponent = bits & 0x7ff0000000000000L;
+ long m = bits & 0x000fffffffffffffL;
+ if (exponent != 0) {
+ // this was a normalized number, add the implicit most significant bit
+ m |= 0x0010000000000000L;
+ }
+ if (sign != 0) {
+ m = -m;
+ }
+ int k = ((int) (exponent >> 52)) - 1075;
+ while (((m & 0x001ffffffffffffeL) != 0) && ((m & 0x1) == 0)) {
+ m >>= 1;
+ ++k;
+ }
+
+ if (k < 0) {
+ numerator = BigInteger.valueOf(m);
+ denominator = BigInteger.ZERO.flipBit(-k);
+ } else {
+ numerator = BigInteger.valueOf(m).multiply(BigInteger.ZERO.flipBit(k));
+ denominator = BigInteger.ONE;
+ }
+
+ }
+
+ /**
+ * <p>
+ * Create a {@link BigFraction} equivalent to the passed {@code BigInteger}, ie
+ * "num / 1".
+ * </p>
+ *
+ * @param num the numerator.
+ * @return {@link BigFraction instance
+ */
+ public static BigFraction of(final BigInteger num) {
+ return new BigFraction(num, BigInteger.ONE);
+ }
+
+ /**
+ * Create a {@link BigFraction} given the numerator and denominator as
+ * {@code BigInteger}. The {@link BigFraction} is reduced to lowest terms.
+ *
+ * @param num the numerator, must not be {@code null}.
+ * @param den the denominator, must not be {@code null}.
+ * @throws ArithmeticException if the denominator is zero.
+ * @return {@link BigFraction instance
+ */
+ public static BigFraction of(BigInteger num, BigInteger den) {
- return new BigFraction(num, den);
++ return new BigFraction(num, den);
+ }
+
+ /**
+ * Create a fraction given the double value.
+ * <p>
+ * This factory method behaves <em>differently</em> from
+ * {@link #from(double, double, int)}. It converts the double value
+ * exactly, considering its internal bits representation. This works for all
+ * values except NaN and infinities and does not requires any loop or
+ * convergence threshold.
+ * </p>
+ * <p>
+ * Since this conversion is exact and since double numbers are sometimes
+ * approximated, the fraction created may seem strange in some cases. For example,
+ * calling <code>new BigFraction(1.0 / 3.0)</code> does <em>not</em> 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).
+ * </p>
+ * @see #BigFraction(double, double, int)
+ * @param value the double value to convert to a fraction.
+ * @exception IllegalArgumentException if value is NaN or infinite
+ * @return {@link BigFraction instance
+ */
+ public static BigFraction from(final double value) throws IllegalArgumentException {
- return new BigFraction(value);
++ return new BigFraction(value);
+ }
+
+ /**
+ * Create a fraction given the double value and maximum error allowed.
+ * <p>
+ * References:
+ * <ul>
+ * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
+ * Continued Fraction</a> equations (11) and (22)-(26)</li>
+ * </ul>
+ *
+ * @param value
+ * the double value to convert to a fraction.
+ * @param epsilon
+ * maximum error allowed. The resulting fraction is within
+ * <code>epsilon</code> of <code>value</code>, in absolute terms.
+ * @param maxIterations
+ * maximum number of convergents.
+ * @throws ArithmeticException
+ * if the continued fraction failed to converge.
+ * @see #BigFraction(double)
+ * @return {@link BigFraction instance
+ */
+ public static BigFraction from(final double value, final double epsilon,
+ final int maxIterations) {
+ return new BigFraction(value, epsilon, Integer.MAX_VALUE, maxIterations);
+ }
+
+ /**
* Create a fraction given the double value and maximum denominator.
* <p>
* References:
@@@ -1188,8 -1172,32 +1172,32 @@@
}
return str;
}
-
+
/**
+ * Parses a string that would be produced by {@link #toString()}
+ * and instantiates the corresponding object.
+ *
+ * @param s String representation.
+ * @return an instance.
+ * @throws FractionException if the string does not
+ * conform to the specification.
+ */
+ public static BigFraction parse(String s) {
+ s = s.replace(",", "");
+ final int slashLoc = s.indexOf("/");
+ // if no slash, parse as single number
+ if (slashLoc == -1) {
+ return BigFraction.of(new BigInteger(s.trim()));
+ } else {
+ final BigInteger num = new BigInteger(
+ s.substring(0, slashLoc).trim());
+ final BigInteger denom = new BigInteger(s.substring(slashLoc + 1).trim());
+ return of(num, denom);
+ }
+ }
+
+
+ /**
* Check that the argument is not null and throw a NullPointerException
* if it is.
* @param arg the argument to check
diff --cc commons-numbers-fraction/src/main/java/org/apache/commons/numbers/fraction/Fraction.java
index 308f930,c6ed60e..8bef75b
--- 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
@@@ -234,21 -146,10 +146,10 @@@ public class Fractio
this.numerator = (int) p1;
this.denominator = (int) q1;
}
-
- }
-
- /**
- * Create a fraction from an int.
- * The fraction is num / 1.
- * @param num the numerator.
- */
- public Fraction(int num) {
- this(num, 1);
}
-
+
/**
- * Create a fraction given the numerator and denominator. The fraction is
- * reduced to lowest terms.
+ * Private constructor for integer fractions.
* @param num the numerator.
* @param den the denominator.
* @throws ArithmeticException if the denominator is {@code zero}
@@@ -281,6 -182,82 +182,82 @@@
this.numerator = num;
this.denominator = den;
}
+ /**
+ * Create a fraction given the double value.
+ * @param value the double value to convert to a fraction.
+ * @throws IllegalArgumentException if the continued fraction failed to
+ * converge.
+ * @return {@link Fraction} instance
+ */
+ public static Fraction from(double value) {
+ return from(value, DEFAULT_EPSILON, 100);
+ }
+
+ /**
+ * Create a fraction given the double value and maximum error allowed.
+ * <p>
+ * References:
+ * <ul>
+ * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
+ * Continued Fraction</a> equations (11) and (22)-(26)</li>
+ * </ul>
+ *
+ * @param value the double value to convert to a 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 continued fraction failed to
+ * converge.
+ * @return {@link Fraction} instance
+ */
+ public static Fraction from(double value, double epsilon, int maxIterations)
+ {
+ return new Fraction(value, epsilon, Integer.MAX_VALUE, maxIterations);
+ }
+
+ /**
+ * Create a fraction given the double value and maximum denominator.
+ * <p>
+ * References:
+ * <ul>
+ * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
+ * Continued Fraction</a> equations (11) and (22)-(26)</li>
+ * </ul>
+ *
+ * @param value the double value to convert to a fraction.
+ * @param maxDenominator The maximum allowed value for denominator
+ * @throws IllegalArgumentException if the continued fraction failed to
+ * converge
+ * @return {@link Fraction} instance
+ */
+ public static Fraction from(double value, int maxDenominator)
+ {
+ return new Fraction(value, 0, maxDenominator, 100);
+ }
+
+
+ /**
+ * Create a fraction from an int.
+ * The fraction is num / 1.
+ * @param num the numerator.
+ * @return {@link Fraction} instance
+ */
+ public static Fraction of(int num) {
+ return of(num, 1);
+ }
+
+ /**
+ * Return a fraction given the numerator and denominator. The fraction is
+ * reduced to lowest terms.
+ * @param num the numerator.
+ * @param den the denominator.
+ * @throws ArithmeticException if the denominator is {@code zero}
+ * or if integer overflow occurs
+ * @return {@link Fraction} instance
+ */
+ public static Fraction of(int num, int den) {
- return new Fraction(num, den);
++ return new Fraction(num, den);
+ }
/**
* Returns the absolute value of this fraction.
@@@ -476,7 -441,13 +441,13 @@@
}
/**
- * Implement add and subtract using algorithm described in Knuth 4.5.1.
+ * Implement add and subtract. This algorithm is similar to that
- * described in Knuth 4.5.1. while making some concessions to
++ * described in Knuth 4.5.1. while making some concessions to
+ * performance. Note Knuth 4.5.1 Exercise 7, which observes that
+ * adding two fractions with 32-bit numerators and denominators
- * requires 65 bits in extreme cases. Here calculations are performed
++ * requires 65 bits in extreme cases. Here calculations are performed
+ * with 64-bit longs and the BigFraction class is recommended for numbers
+ * that may grow large enough to be in danger of overflow.
*
* @param fraction the fraction to subtract, must not be {@code null}
* @param isAdd true to add, false to subtract
@@@ -685,4 -621,26 +621,26 @@@
}
return str;
}
-
++
+ /**
+ * Parses a string that would be produced by {@link #toString()}
+ * and instantiates the corresponding object.
+ *
+ * @param s String representation.
+ * @return an instance.
+ * @throws FractionException if the string does not
+ * conform to the specification.
+ */
+ public static Fraction parse(String s) {
+ final int slashLoc = s.indexOf("/");
+ // if no slash, parse as single number
+ if (slashLoc == -1) {
+ return Fraction.of(Integer.parseInt(s.trim()));
+ } else {
+ final int num = Integer.parseInt(s.substring(0, slashLoc).trim());
+ final int denom = Integer.parseInt(s.substring(slashLoc + 1).trim());
+ return of(num, denom);
+ }
+ }
+
}
diff --cc commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/BigFractionTest.java
index 8a32785,7b69a61..2234b1b
--- 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
@@@ -661,4 -649,28 +656,28 @@@ public class BigFractionTest
Assert.assertEquals(fraction, TestUtils.serializeAndRecover(fraction));
}
}
-
-
++
++
+ @Test
- public void testParse() {
++ public void testParse() {
+ String[] validExpressions = new String[] {
- "3",
- "1 / 2",
++ "3",
++ "1 / 2",
+ "2147,483,647 / 2,147,483,648", //over largest int value
+ "9,223,372,036,854,775,807 / 9,223,372,036,854,775,808" //over largest long value
+ };
+ BigFraction[] fractions = {
+ BigFraction.of(3),
+ BigFraction.of(1, 2),
+ BigFraction.of(2147483647, 2147483648L),
+ BigFraction.of(new BigInteger("9223372036854775807"),
+ new BigInteger("9223372036854775808"))
+ };
+ int inc = 0;
+ for (BigFraction fraction: fractions) {
- Assert.assertEquals(fraction,
++ Assert.assertEquals(fraction,
+ BigFraction.parse(validExpressions[inc]));
+ inc++;
+ }
+ }
}
diff --cc commons-numbers-fraction/src/test/java/org/apache/commons/numbers/fraction/FractionTest.java
index cb8eb28,10c3a20..444f2ef
--- 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
@@@ -57,17 -56,15 +57,17 @@@ public class FractionTest
// success
}
- assertFraction(0, 1, new Fraction(0.00000000000001));
- assertFraction(2, 5, new Fraction(0.40000000000001));
- assertFraction(15, 1, new Fraction(15.0000000000001));
+ assertFraction(0, 1, Fraction.from(0.00000000000001));
+ assertFraction(2, 5, Fraction.from(0.40000000000001));
+ assertFraction(15, 1, Fraction.from(15.0000000000001));
}
- @Test(expected=ArithmeticException.class)
+ @Test()
public void testGoldenRatio() {
// the golden ratio is notoriously a difficult number for continuous fraction
- Fraction.from((1 + Math.sqrt(5)) / 2, 1.0e-12, 25);
+ Assertions.assertThrows(ArithmeticException.class,
+ () -> new Fraction((1 + Math.sqrt(5)) / 2, 1.0e-12, 25)
+ );
}
// MATH-179
@@@ -644,4 -627,23 +630,22 @@@
Assert.assertEquals(fraction, TestUtils.serializeAndRecover(fraction));
}
}
-
++
+ @Test
+ public void testParse() {
+ String[] validExpressions = new String[] {
+ "1 / 2", "15 / 16", "-2 / 3", "8 / 7"
+ };
+ Fraction[] fractions = {
+ Fraction.of(1, 2),
+ Fraction.of(15, 16),
+ Fraction.of(-2, 3),
+ Fraction.of(8, 7),
+ };
+ int inc = 0;
+ for (Fraction fraction: fractions) {
- Assert.assertEquals(fraction,
- Fraction.parse(validExpressions[inc]));
++ Assert.assertEquals(fraction,Fraction.parse(validExpressions[inc]));
+ inc++;
+ }
+ }
}