You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2019/07/05 22:24:21 UTC
[commons-numbers] 01/04: NUMBERS-129: Use long instead of int for
intermediate results in Fraction.addSub(Fraction, boolean)
This is an automated email from the ASF dual-hosted git repository.
erans pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
commit 510e23218f51e4391827b8121ba7c4c0cc9c52f9
Author: Schamschi <he...@gmx.at>
AuthorDate: Fri Jul 5 16:56:21 2019 +0200
NUMBERS-129: Use long instead of int for intermediate results in Fraction.addSub(Fraction, boolean)
---
.../apache/commons/numbers/fraction/Fraction.java | 58 +++++++++++++++-------
.../commons/numbers/fraction/CommonTestCases.java | 6 +++
2 files changed, 45 insertions(+), 19 deletions(-)
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 b544192..fd5eb5f 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
@@ -46,10 +46,13 @@ public class Fraction
/** The default epsilon used for convergence. */
private static final double DEFAULT_EPSILON = 1e-5;
- /** The denominator. */
+ /** The denominator of this fraction reduced to lowest terms. Always positive. */
private final int denominator;
- /** The numerator. */
+ /**
+ * The numerator of this fraction reduced to lowest terms. Negative if this
+ * fraction's value is negative.
+ */
private final int numerator;
/**
@@ -450,15 +453,9 @@ public class Fraction
}
/**
- * Implement add and subtract. This algorithm is similar to that
- * 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
- * with 64-bit longs and the BigFraction class is recommended for numbers
- * that may grow large enough to be in danger of overflow.
+ * Implement add and subtract using algorithm described in Knuth 4.5.1.
*
- * @param fraction the fraction to subtract, must not be {@code null}
+ * @param fraction the fraction to add or subtract, must not be {@code null}
* @param isAdd true to add, false to subtract
* @return a {@code Fraction} instance with the resulting values
* @throws NullPointerException if the fraction is {@code null}
@@ -476,17 +473,40 @@ public class Fraction
if (fraction.numerator == 0) {
return this;
}
- // t = u(v'/gcd) +/- v(u'/gcd)
+
+ /*
+ * Let the two fractions be u/u' and v/v', and d1 = gcd(u', v').
+ * First, compute t, defined as:
+ *
+ * t = u(v'/d1) +/- v(u'/d1)
+ */
int d1 = ArithmeticUtils.gcd(denominator, fraction.denominator);
- int uvp = Math.multiplyExact(numerator, fraction.denominator / d1);
- int upv = Math.multiplyExact(fraction.numerator, denominator / d1);
- int t = isAdd ? Math.addExact(uvp, upv) : Math.subtractExact(uvp, upv);
- int tmodd1 = t % d1;
- int d2 = (tmodd1==0)?d1:ArithmeticUtils.gcd(tmodd1, d1);
+ long uvp = (long) numerator * (long) (fraction.denominator / d1);
+ long upv = (long) fraction.numerator * (long) (denominator / d1);
+
+ /*
+ * The largest possible absolute value of a product of two ints is 2^62,
+ * which can only happen as a result of -2^31 * -2^31 = 2^62, so a
+ * product of -2^62 is not possible. It follows that (uvp - upv) cannot
+ * overflow, and (uvp + upv) could only overflow if uvp = upv = 2^62.
+ * But for this to happen, the terms u, v, v'/d1 and u'/d1 would all
+ * have to be -2^31, which is not possible because v'/d1 and u'/d1
+ * are necessarily coprime.
+ */
+ long t = isAdd ? uvp + upv : uvp - upv;
+
+ /*
+ * Because u is coprime to u' and v is coprime to v', t is necessarily
+ * coprime to both v'/d1 and u'/d1. However, it might have a common
+ * factor with d1.
+ */
+ long d2 = ArithmeticUtils.gcd(t, (long) d1);
// result is (t/d2) / (u'/d1)(v'/d2)
- int w = t / d2;
- return new Fraction (w, Math.multiplyExact(denominator/d1,
- fraction.denominator/d2));
+ return of(Math.toIntExact(t / d2),
+ Math.multiplyExact(
+ denominator / d1,
+ fraction.denominator / (int) d2)
+ );
}
/**
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 d28ef63..805de0c 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
@@ -230,6 +230,12 @@ class CommonTestCases {
1, 1,
Integer.MAX_VALUE, 1));
+ //NUMBERS-129
+ testCases.add(new BinaryOperatorTestCase(
+ 362564597, 10,
+ 274164323, 6,
+ 1229257703, 15));
+
return testCases;
}