This is an automated email from the ASF dual-hosted git repository.
garydgregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-lang.git
The following commit(s) were added to refs/heads/master by this push:
new e213b85ce Fix Fraction.add and subtract for operands not in lowest
terms (#1784)
e213b85ce is described below
commit e213b85ce46aca72b284813c74a15e9ac9d55d90
Author: Jeff Lenamon <[email protected]>
AuthorDate: Tue Sep 8 19:31:34 2026 -0400
Fix Fraction.add and subtract for operands not in lowest terms (#1784)
* Fix Fraction.add and subtract for operands not in lowest terms
* Add subtraction, cancellation and Integer.MIN_VALUE cases to FractionTest
---
.../org/apache/commons/lang3/math/Fraction.java | 22 ++++++---
.../apache/commons/lang3/math/FractionTest.java | 54 ++++++++++++++++++++++
2 files changed, 69 insertions(+), 7 deletions(-)
diff --git a/src/main/java/org/apache/commons/lang3/math/Fraction.java
b/src/main/java/org/apache/commons/lang3/math/Fraction.java
index 49b313a1e..cb18b130d 100644
--- a/src/main/java/org/apache/commons/lang3/math/Fraction.java
+++ b/src/main/java/org/apache/commons/lang3/math/Fraction.java
@@ -556,23 +556,31 @@ private Fraction addSub(final Fraction fraction, final
boolean isAdd) {
if (fraction.numerator == 0) {
return this;
}
+ // Knuth 4.5.1 assumes operands in lowest terms and this class does
not reduce on
+ // construction, so reduce both first, as multiplyBy does.
+ final int thisGcd = greatestCommonDivisor(numerator, denominator);
+ final int thatGcd = greatestCommonDivisor(fraction.numerator,
fraction.denominator);
+ final int thisNumerator = numerator / thisGcd;
+ final int thisDenominator = denominator / thisGcd;
+ final int thatNumerator = fraction.numerator / thatGcd;
+ final int thatDenominator = fraction.denominator / thatGcd;
// if denominators are randomly distributed, d1 will be 1 about 61%
// of the time.
- final int d1 = greatestCommonDivisor(denominator,
fraction.denominator);
+ final int d1 = greatestCommonDivisor(thisDenominator, thatDenominator);
if (d1 == 1) {
// result is ((u*v' +/- u'v) / u'v')
// the int cross products u*v' and u'*v can overflow even when the
reduced result
// fits an int, so widen to long and let Math narrow the final
numerator back.
- final long uvp = (long) numerator * fraction.denominator;
- final long upv = (long) fraction.numerator * denominator;
+ final long uvp = (long) thisNumerator * thatDenominator;
+ final long upv = (long) thatNumerator * thisDenominator;
final long t = isAdd ? Math.addExact(uvp, upv) :
Math.subtractExact(uvp, upv);
- return new Fraction(Math.toIntExact(t),
mulPosAndCheck(denominator, fraction.denominator));
+ return new Fraction(Math.toIntExact(t),
mulPosAndCheck(thisDenominator, thatDenominator));
}
// 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)
- final BigInteger uvp =
BigInteger.valueOf(numerator).multiply(BigInteger.valueOf(fraction.denominator
/ d1));
- final BigInteger upv =
BigInteger.valueOf(fraction.numerator).multiply(BigInteger.valueOf(denominator
/ d1));
+ final BigInteger uvp =
BigInteger.valueOf(thisNumerator).multiply(BigInteger.valueOf(thatDenominator /
d1));
+ final BigInteger upv =
BigInteger.valueOf(thatNumerator).multiply(BigInteger.valueOf(thisDenominator /
d1));
final 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)
@@ -584,7 +592,7 @@ private Fraction addSub(final Fraction fraction, final
boolean isAdd) {
if (w.bitLength() > 31) {
throw new ArithmeticException("overflow: numerator too large after
multiply");
}
- return new Fraction(w.intValue(), mulPosAndCheck(denominator / d1,
fraction.denominator / d2));
+ return new Fraction(w.intValue(), mulPosAndCheck(thisDenominator / d1,
thatDenominator / d2));
}
/**
diff --git a/src/test/java/org/apache/commons/lang3/math/FractionTest.java
b/src/test/java/org/apache/commons/lang3/math/FractionTest.java
index e2f583a78..57ec9d3a4 100644
--- a/src/test/java/org/apache/commons/lang3/math/FractionTest.java
+++ b/src/test/java/org/apache/commons/lang3/math/FractionTest.java
@@ -64,6 +64,60 @@ void testAbs() {
assertThrows(ArithmeticException.class, () ->
Fraction.getFraction(Integer.MIN_VALUE, 1).abs());
}
+ @Test
+ void testAddSubtractUnreducedOperands() {
+ // 1073741823/2147483646 is 1/2, and 1/2 + 3/5 is 11/10.
+ Fraction f = Fraction.getFraction(1073741823,
2147483646).add(Fraction.getFraction(3, 5));
+ assertEquals(11, f.getNumerator());
+ assertEquals(10, f.getDenominator());
+
+ f = Fraction.getFraction(1073741823,
2147483646).subtract(Fraction.getFraction(3, 5));
+ assertEquals(-1, f.getNumerator());
+ assertEquals(10, f.getDenominator());
+
+ // 2147483646/2147483646 is 1, and 1 + -11 is -10.
+ f = Fraction.getFraction(2147483646,
2147483646).add(Fraction.getFraction(-11, 1));
+ assertEquals(-10, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
+ // add() returns the result in reduced form.
+ f = Fraction.getFraction(50, 100).add(Fraction.getFraction(1, 3));
+ assertEquals(5, f.getNumerator());
+ assertEquals(6, f.getDenominator());
+
+ f = Fraction.getFraction(2, 4).add(Fraction.getFraction(1, 2));
+ assertEquals(1, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
+ // Reducing the operands by hand must not change the answer.
+ assertEquals(Fraction.getFraction(7,
13).reduce().add(Fraction.getFraction(46341, 1073741823).reduce()),
+ Fraction.getFraction(7, 13).add(Fraction.getFraction(46341,
1073741823)));
+
+ // Both operands unreduced: 2/4 + 2/6 is 1/2 + 1/3.
+ f = Fraction.getFraction(2, 4).add(Fraction.getFraction(2, 6));
+ assertEquals(5, f.getNumerator());
+ assertEquals(6, f.getDenominator());
+
+ // Reduced denominators share a factor: 2/4 - 2/12 is 1/2 - 1/6.
+ f = Fraction.getFraction(2, 4).subtract(Fraction.getFraction(2, 12));
+ assertEquals(1, f.getNumerator());
+ assertEquals(3, f.getDenominator());
+
+ // Equal values cancel to 0/1.
+ f = Fraction.getFraction(2, 4).subtract(Fraction.getFraction(3, 6));
+ assertEquals(0, f.getNumerator());
+ assertEquals(1, f.getDenominator());
+
+ // Integer.MIN_VALUE/2 reduces to -1073741824/1 without overflowing.
+ f = Fraction.getFraction(Integer.MIN_VALUE,
2).add(Fraction.getFraction(2, 4));
+ assertEquals(-Integer.MAX_VALUE, f.getNumerator());
+ assertEquals(2, f.getDenominator());
+
+ // A result that genuinely does not fit an int still overflows.
+ final Fraction maxValue = Fraction.getFraction(-Integer.MAX_VALUE, 1);
+ assertThrows(ArithmeticException.class, () -> maxValue.add(maxValue));
+ }
+
@Test
void testAdd() {
Fraction f;
