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/08/08 17:30:23 UTC
[commons-numbers] branch master updated (08962e8 -> 5a0d8f5)
This is an automated email from the ASF dual-hosted git repository.
erans pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git.
from 08962e8 Fix the site's source repository link.
new 89ce65d NUMBERS-132: Perform gcd algorithm on negative numbers in ArithmeticUtils.gcd(int, int)
new f1f4ddc Merge branch 'NUMBERS-132__heinrich'
new 7c20513 NUMBERS-120: Repair BigFraction.doubleValue() to produce correctly rounded result with maximum precision
new 28fa56d NUMBERS-120: Add mad corner case to unit tests to enforce maximum precision in doubleValue()
new 1712ee6 NUMBERS-120: Extract functionality of doubleValue() to helper method for reuse in floatValue()
new fd1292e NUMBERS-120: Repair BigFraction.floatValue()
new 0c070c1 NUMBERS-120: Make doubleValue() tests independent of double constructor
new 167f004 NUMBERS-120: Don't calculate more bits than necessary in toFloatingPointBits(int, int)
new f6a2e09 NUMBERS-120: Add unit tests
new 504f82b NUMBERS-120: Remove redundant conditional branch
new 1abb1d8 NUMBERS-120: Satisfy checkstyle requirements
new 6ebd569 NUMBERS-120: Create assertion helper methods for readability
new e6de6fc NUMBERS-120: Simplify roundAndRightShift(BigInteger, int, boolean)
new e89aaad NUMBERS-120: Add comment about previously neglected corner case that was luckily already handled correctly
new 404ff82 NUMBERS-120: Add unit test for rounding up from subnormal to normal number
new 26c9e7f NUMBERS-120: Report argument values in IllegalArgumentException messages
new 5d4485d Javadoc and formatting nits.
new 5a0d8f5 Merge branch 'NUMBERS-120__heinrich'
The 18 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../commons/numbers/core/ArithmeticUtils.java | 142 ++++---------
.../commons/numbers/fraction/BigFraction.java | 219 ++++++++++++++++++---
.../commons/numbers/fraction/BigFractionTest.java | 133 +++++++++++--
3 files changed, 351 insertions(+), 143 deletions(-)
[commons-numbers] 13/18: NUMBERS-120: Simplify
roundAndRightShift(BigInteger, int, boolean)
Posted by er...@apache.org.
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 e6de6fc654b0fba45e838b35787a8fa46a8b9f4f
Author: Schamschi <he...@gmx.at>
AuthorDate: Wed Jul 3 01:01:55 2019 +0200
NUMBERS-120: Simplify roundAndRightShift(BigInteger, int, boolean)
---
.../java/org/apache/commons/numbers/fraction/BigFraction.java | 8 ++------
1 file changed, 2 insertions(+), 6 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 7737228..a73a643 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
@@ -836,16 +836,12 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
if (bits <= 0) {
throw new IllegalArgumentException();
}
- boolean roundUp = false;
+ BigInteger result = value.shiftRight(bits);
if (value.testBit(bits - 1) &&
(hasFractionalBits ||
(value.getLowestSetBit() < bits - 1) ||
value.testBit(bits))) {
- roundUp = true;
- }
- BigInteger result = value.shiftRight(bits);
- if (roundUp) {
- result = result.add(BigInteger.ONE);
+ result = result.add(BigInteger.ONE); //round up
}
return result;
}
[commons-numbers] 17/18: Javadoc and formatting nits.
Posted by er...@apache.org.
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 5d4485d2be5f96bbbb74fa4655152c57ad5a4ccd
Author: Gilles Sadowski <gi...@harfang.homelinux.org>
AuthorDate: Thu Aug 8 19:16:16 2019 +0200
Javadoc and formatting nits.
---
.../commons/numbers/fraction/BigFraction.java | 48 +++++++++++++---------
1 file changed, 28 insertions(+), 20 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 f2bac32..ae1e284 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
@@ -116,6 +116,7 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* in absolute terms.
* @param maxDenominator Maximum denominator value allowed.
* @param maxIterations Maximum number of convergents.
+ * @return a new instance.
* @throws ArithmeticException if the continued fraction failed to converge.
*/
private static BigFraction from(final double value,
@@ -683,15 +684,18 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* criteria described above
*/
private long toFloatingPointBits(int exponentLength, int significandLength) {
- if (exponentLength < 1 ||significandLength < 1 || exponentLength > Math.min(32, 63 - significandLength)) {
- throw new IllegalArgumentException("exponent length: " + exponentLength + "; significand length: " + significandLength);
+ if (exponentLength < 1 ||
+ significandLength < 1 ||
+ exponentLength > Math.min(32, 63 - significandLength)) {
+ throw new IllegalArgumentException("exponent length: " + exponentLength +
+ "; significand length: " + significandLength);
}
if (numerator.signum() == 0) {
return 0L;
}
- long sign = numerator.signum() == -1 ? 1L : 0L;
- BigInteger positiveNumerator = numerator.abs();
+ final long sign = numerator.signum() == -1 ? 1L : 0L;
+ final BigInteger positiveNumerator = numerator.abs();
/*
* The most significant 1-bit of a non-zero number is not explicitly
@@ -706,8 +710,8 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* are not relevant for the significand of the prospective binary
* floating-point value.
*/
- int denRightShift = denominator.getLowestSetBit();
- BigInteger divisor = denominator.shiftRight(denRightShift);
+ final int denRightShift = denominator.getLowestSetBit();
+ final BigInteger divisor = denominator.shiftRight(denRightShift);
/*
* Now, we're going to calculate the (significandLength + 2) most
@@ -730,12 +734,13 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* denominator).
*/
int numRightShift = positiveNumerator.bitLength() - divisor.bitLength() - (significandLength + 2);
- if (numRightShift > 0 && divisor.equals(BigInteger.ONE)) {
+ if (numRightShift > 0 &&
+ divisor.equals(BigInteger.ONE)) {
numRightShift = Math.min(numRightShift, positiveNumerator.getLowestSetBit());
}
- BigInteger dividend = positiveNumerator.shiftRight(numRightShift);
+ final BigInteger dividend = positiveNumerator.shiftRight(numRightShift);
- BigInteger quotient = dividend.divide(divisor);
+ final BigInteger quotient = dividend.divide(divisor);
int quotRightShift = quotient.bitLength() - (significandLength + 1);
long significand = roundAndRightShift(
@@ -765,9 +770,9 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* fractional part. To convert the unbiased exponent to a biased
* exponent, we also need to add the exponent bias.
*/
- int exponentBias = (1 << (exponentLength - 1)) - 1;
+ final int exponentBias = (1 << (exponentLength - 1)) - 1;
long exponent = numRightShift - denRightShift + quotRightShift + significandLength + exponentBias;
- long maxExponent = (1L << exponentLength) - 1L; //special exponent for infinities and NaN
+ final long maxExponent = (1L << exponentLength) - 1L; //special exponent for infinities and NaN
if (exponent >= maxExponent) { //infinity
exponent = maxExponent;
@@ -796,11 +801,9 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* normalized floating-point number, and (- significandLength)
* because the significand will be treated as the fractional part).
*/
- significand = roundAndRightShift(
- quotient,
- (1 - exponentBias - significandLength) - (numRightShift - denRightShift),
- !divisor.equals(BigInteger.ONE)
- ).longValue();
+ significand = roundAndRightShift(quotient,
+ (1 - exponentBias - significandLength) - (numRightShift - denRightShift),
+ !divisor.equals(BigInteger.ONE)).longValue();
exponent = 0L;
/*
@@ -813,7 +816,10 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* leading 1-bit.
*/
}
- return (sign << (significandLength + exponentLength)) | (exponent << significandLength) | significand;
+
+ return (sign << (significandLength + exponentLength)) |
+ (exponent << significandLength) |
+ significand;
}
/**
@@ -849,13 +855,15 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
if (bits <= 0) {
throw new IllegalArgumentException("bits: " + bits);
}
+
BigInteger result = value.shiftRight(bits);
if (value.testBit(bits - 1) &&
- (hasFractionalBits ||
- (value.getLowestSetBit() < bits - 1) ||
- value.testBit(bits))) {
+ (hasFractionalBits ||
+ (value.getLowestSetBit() < bits - 1) ||
+ value.testBit(bits))) {
result = result.add(BigInteger.ONE); //round up
}
+
return result;
}
[commons-numbers] 03/18: NUMBERS-120: Repair
BigFraction.doubleValue() to produce correctly rounded result with maximum
precision
Posted by er...@apache.org.
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 7c20513b8cf82e0e485c1a953f9cb95f0f277908
Author: Schamschi <he...@gmx.at>
AuthorDate: Mon Jun 24 22:58:58 2019 +0200
NUMBERS-120: Repair BigFraction.doubleValue() to produce correctly rounded result with maximum precision
---
.../commons/numbers/fraction/BigFraction.java | 155 +++++++++++++++++++--
.../commons/numbers/fraction/BigFractionTest.java | 53 ++++++-
2 files changed, 189 insertions(+), 19 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 7c8ce9c..d9efcaf 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
@@ -671,20 +671,149 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
*/
@Override
public double doubleValue() {
- double doubleNum = numerator.doubleValue();
- double doubleDen = denominator.doubleValue();
- double result = doubleNum / doubleDen;
- if (Double.isInfinite(doubleNum) ||
- Double.isInfinite(doubleDen) ||
- Double.isNaN(result)) {
- // Numerator and/or denominator must be out of range:
- // Calculate how far to shift them to put them in range.
- int shift = Math.max(numerator.bitLength(),
- denominator.bitLength()) - Math.getExponent(Double.MAX_VALUE);
- result = numerator.shiftRight(shift).doubleValue() /
- denominator.shiftRight(shift).doubleValue();
+ if (numerator.signum() == 0) {
+ return 0;
+ }
+
+ /*
+ * We will manually construct a long from which to create the double to
+ * ensure maximum precision. First, we set the sign:
+ */
+ long sign = numerator.signum() == -1 ? 1L : 0L;
+ BigInteger positiveNumerator = numerator.abs();
+
+ /*
+ * The significand of a double value consists of 52 bits for the
+ * fractional part, plus the implicit leading 1 bit for the
+ * non-fractional part, which makes 53 bits in total. So we need to
+ * calculate the most significant 54 bits of this fraction's quotient,
+ * and then, based on the 54th most significant bit, find out whether
+ * we need to round up or down.
+ *
+ * First, we'll remove all powers of 2 from the denominator because they
+ * are not relevant for the significand of the prospective double value.
+ */
+ int denRightShift = denominator.getLowestSetBit();
+ BigInteger divisor = denominator.shiftRight(denRightShift);
+
+ /*
+ * Now, we're going to calculate the 54 most significant bits of the
+ * quotient using integer division. To guarantee that the quotient has
+ * at least 54 bits, the bit length of the dividend must exceed that
+ * of the divisor by at least 54. If the numerator has powers of 2
+ * beyond this limit, they can be removed as well.
+ */
+ int numRightShift = positiveNumerator.bitLength() - divisor.bitLength() - 54;
+ if (numRightShift > 0) {
+ numRightShift = Math.min(numRightShift, positiveNumerator.getLowestSetBit());
+ }
+ BigInteger dividend = positiveNumerator.shiftRight(numRightShift);
+
+ BigInteger quotient = dividend.divide(divisor);
+ int quotRightShift = quotient.bitLength() - 53;
+
+ /*
+ * If the denominator was a power of two, then the divisor was reduced
+ * 1, meaning the quotient was calculated exactly. Otherwise, the
+ * fractional part of the precise quotient's binary representation does
+ * not terminate.
+ */
+ long significand = roundAndRightShift(
+ quotient,
+ quotRightShift,
+ !divisor.equals(BigInteger.ONE)
+ ).longValue();
+
+ /*
+ * If the significand had to be rounded up, this could have caused an
+ * overflow into the 54th least significant bit.
+ */
+ if ((significand & (1L << 53)) != 0) {
+ significand >>= 1;
+ quotRightShift++;
+ }
+
+ /*
+ * Now comes the exponent. The absolute value of this fraction based
+ * on the current local variables is:
+ *
+ * significand * 2^(numRightShift - denRightShift + quotRightShift)
+ *
+ * To get the unbiased exponent for the double value, we need to add 52
+ * to the above exponent, because the 52 least significant bits of
+ * significant will be treated as a fractional part. To convert the
+ * unbiased exponent to a biased exponent, we need to add 1023.
+ */
+ long exponent = numRightShift - denRightShift + quotRightShift + 52 + 1023;
+
+ if (exponent > 2046) { //infinity
+ exponent = 2047;
+ significand = 0;
+ } else if (exponent > 0) { //normalized number
+ significand &= 0x000FFFFFFFFFFFFFL; //remove implicit leading 1-bit
+ } else { //smaller than the smallest normalized number
+ /*
+ * We need to round the quotient to fewer than 53 bits. This must
+ * be done with the original quotient and not with the current
+ * significand, because the loss of precision in the rounding to 53
+ * bits might cause a rounding of the current significand's value
+ * to produce a different result than a rounding of the
+ * original quotient.
+ *
+ * So we find out how many high-order bits from the quotient we can
+ * squeeze into the significand. The absolute value of the fraction
+ * is:
+ *
+ * quotient * 2^(numRightShift - denRightShift)
+ *
+ * To get the significand, we need to right shift the quotient so
+ * that the above exponent becomes (- 1022 - 52) = -1074 (-1022 is
+ * the unbiased exponent of a subnormal double value, and 52 because
+ * the significand will be treated as the fractional part)
+ */
+ significand = roundAndRightShift(
+ quotient,
+ - 1074 - (numRightShift - denRightShift),
+ !divisor.equals(BigInteger.ONE)
+ ).longValue();
+ exponent = 0L;
+ }
+ return Double.longBitsToDouble((sign << 63) | (exponent << 52) | significand);
+ }
+
+ /**
+ * Rounds an integer to the specified power of two (i.e. the minimum number of
+ * low-order bits that must be zero) and performs a right-shift by this
+ * amount. The rounding mode applied is round to nearest, with ties rounding
+ * to even (meaning the prospective least significant bit must be zero). The
+ * number can optionally be treated as though it contained at
+ * least one 0-bit and one 1-bit in its fractional part, to influence the result in cases
+ * that would otherwise be a tie.
+ * @param value the number to round and right-shift
+ * @param bits the power of two to which to round; must be positive
+ * @param hasFractionalBits whether the number should be treated as though
+ * it contained a non-zero fractional part
+ * @return a {@code BigInteger} as described above
+ */
+ private static BigInteger roundAndRightShift(BigInteger value, int bits, boolean hasFractionalBits) {
+ if (bits <= 0) {
+ throw new IllegalArgumentException();
+ } else if (bits > value.bitLength()) {
+ return BigInteger.ZERO;
+ } else {
+ boolean roundUp = false;
+ if (value.testBit(bits - 1)
+ && (hasFractionalBits
+ || (value.getLowestSetBit() < bits - 1)
+ || value.testBit(bits))) {
+ roundUp = true;
+ }
+ BigInteger result = value.shiftRight(bits);
+ if (roundUp) {
+ result = result.add(BigInteger.ONE);
+ }
+ return result;
}
- return result;
}
/**
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 74aefc4..7c4afdf 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
@@ -178,6 +178,35 @@ public class BigFractionTest {
Assertions.assertEquals(1.0 / 3.0, second.doubleValue(), 0.0);
}
+ @Test
+ public void testDoubleValueForSubnormalNumbers() {
+ {
+ double min = Double.MIN_VALUE;
+ double min1Up = Math.nextUp(min);
+ double min2Up = Math.nextUp(min1Up);
+ Assertions.assertEquals(
+ min,
+ BigFraction.from(min).doubleValue());
+ Assertions.assertEquals(
+ min1Up,
+ BigFraction.from(min1Up).doubleValue());
+ Assertions.assertEquals(
+ min2Up,
+ BigFraction.from(min2Up).doubleValue());
+ }
+
+ {
+ double minNormal1Down = Math.nextDown(Double.MIN_NORMAL);
+ double minNormal2Down = Math.nextDown(minNormal1Down);
+ Assertions.assertEquals(
+ minNormal1Down,
+ BigFraction.from(minNormal1Down).doubleValue());
+ Assertions.assertEquals(
+ minNormal2Down,
+ BigFraction.from(minNormal2Down).doubleValue());
+ }
+ }
+
// MATH-744
@Test
public void testDoubleValueForLargeNumeratorAndDenominator() {
@@ -202,15 +231,27 @@ public class BigFractionTest {
Assertions.assertEquals(5, large.floatValue(), 1e-15);
}
- // NUMBERS-15
@Test
public void testDoubleValueForLargeNumeratorAndSmallDenominator() {
- final BigInteger pow300 = BigInteger.TEN.pow(300);
- final BigInteger pow330 = BigInteger.TEN.pow(330);
- final BigFraction large = BigFraction.of(pow330.add(BigInteger.ONE),
- pow300);
+ // NUMBERS-15
+ {
+ final BigInteger pow300 = BigInteger.TEN.pow(300);
+ final BigInteger pow330 = BigInteger.TEN.pow(330);
+ final BigFraction large = BigFraction.of(pow330.add(BigInteger.ONE),
+ pow300);
- Assertions.assertEquals(1e30, large.doubleValue(), 1e-15);
+ Assertions.assertEquals(1e30, large.doubleValue(), 1e-15);
+ }
+
+ // NUMBERS-120
+ {
+ BigFraction f = BigFraction.of(
+ BigInteger.ONE.shiftLeft(1024)
+ .subtract(BigInteger.ONE.shiftLeft(970))
+ .add(BigInteger.ONE),
+ BigInteger.valueOf(3));
+ Assertions.assertEquals(5.992310449541053E307, f.doubleValue());
+ }
}
// NUMBERS-15
[commons-numbers] 09/18: NUMBERS-120: Add unit tests
Posted by er...@apache.org.
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 f6a2e09df40f8d93f808e6072e48c2c144b70b8c
Author: Schamschi <he...@gmx.at>
AuthorDate: Thu Jun 27 23:45:23 2019 +0200
NUMBERS-120: Add unit tests
---
.../commons/numbers/fraction/BigFractionTest.java | 61 +++++++++++++++++++---
1 file changed, 55 insertions(+), 6 deletions(-)
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 950e7cc..cb6061d 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
@@ -171,6 +171,8 @@ public class BigFractionTest {
@Test
public void testDoubleValue() {
+ Assertions.assertEquals(0d, BigFraction.ZERO.doubleValue(), 0d);
+
{
BigFraction first = BigFraction.of(1, 2);
BigFraction second = BigFraction.of(1, 3);
@@ -180,16 +182,37 @@ public class BigFractionTest {
}
//NUMBERS-120
- {
- BigFraction f = BigFraction.of(
- BigInteger.ONE.shiftLeft(54),
- BigInteger.ONE.shiftLeft(53).add(BigInteger.ONE));
- Assertions.assertEquals(2d - 0x1P-52, f.doubleValue());
- }
+ Assertions.assertEquals(
+ 2d - 0x1P-52,
+ BigFraction.of(
+ BigInteger.ONE.shiftLeft(54),
+ BigInteger.ONE.shiftLeft(53).add(BigInteger.ONE)
+ ).doubleValue());
+
+ Assertions.assertEquals(
+ 2d,
+ BigFraction.of(
+ BigInteger.ONE.shiftLeft(54).subtract(BigInteger.ONE),
+ BigInteger.ONE.shiftLeft(53)
+ ).doubleValue());
+ Assertions.assertEquals(
+ 1d,
+ BigFraction.of(
+ BigInteger.ONE.shiftLeft(53).add(BigInteger.ONE),
+ BigInteger.ONE.shiftLeft(53)
+ ).doubleValue());
}
@Test
public void testDoubleValueForSubnormalNumbers() {
+ //test Double.MIN_VALUE * 2/3
+ Assertions.assertEquals(
+ Double.MIN_VALUE,
+ BigFraction.of(
+ BigInteger.ONE,
+ BigInteger.ONE.shiftLeft(1073).multiply(BigInteger.valueOf(3L))
+ ).doubleValue());
+
Assertions.assertEquals(
Double.MIN_VALUE,
BigFraction.of(
@@ -223,6 +246,23 @@ public class BigFractionTest {
).doubleValue());
}
+ @Test
+ public void testDoubleValueForInfinities() {
+ Assertions.assertEquals(
+ Double.NEGATIVE_INFINITY,
+ BigFraction.of(
+ BigInteger.ONE.shiftLeft(1024)
+ .subtract(BigInteger.ONE.shiftLeft(970))
+ .negate()
+ ).doubleValue());
+ Assertions.assertEquals(
+ Double.POSITIVE_INFINITY,
+ BigFraction.of(
+ BigInteger.ONE.shiftLeft(1024)
+ .subtract(BigInteger.ONE.shiftLeft(970))
+ ).doubleValue());
+ }
+
// MATH-744
@Test
public void testDoubleValueForLargeNumeratorAndDenominator() {
@@ -268,6 +308,15 @@ public class BigFractionTest {
BigInteger.valueOf(3));
Assertions.assertEquals(5.992310449541053E307, f.doubleValue());
}
+
+ {
+ BigFraction f = BigFraction.of(
+ BigInteger.ONE.shiftLeft(1025)
+ .subtract(BigInteger.ONE.shiftLeft(972))
+ .subtract(BigInteger.ONE),
+ BigInteger.valueOf(2));
+ Assertions.assertEquals(Double.MAX_VALUE, f.doubleValue());
+ }
}
// NUMBERS-15
[commons-numbers] 04/18: NUMBERS-120: Add mad corner case to unit
tests to enforce maximum precision in doubleValue()
Posted by er...@apache.org.
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 28fa56dcb3d1f41bdc84809cd00e710d43993a01
Author: Schamschi <he...@gmx.at>
AuthorDate: Mon Jun 24 23:08:56 2019 +0200
NUMBERS-120: Add mad corner case to unit tests to enforce maximum precision in doubleValue()
---
.../commons/numbers/fraction/BigFractionTest.java | 18 ++++++++++++++----
1 file changed, 14 insertions(+), 4 deletions(-)
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 7c4afdf..e20113e 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
@@ -171,11 +171,21 @@ public class BigFractionTest {
@Test
public void testDoubleValue() {
- BigFraction first = BigFraction.of(1, 2);
- BigFraction second = BigFraction.of(1, 3);
+ {
+ BigFraction first = BigFraction.of(1, 2);
+ BigFraction second = BigFraction.of(1, 3);
+
+ Assertions.assertEquals(0.5, first.doubleValue(), 0.0);
+ Assertions.assertEquals(1.0 / 3.0, second.doubleValue(), 0.0);
+ }
- Assertions.assertEquals(0.5, first.doubleValue(), 0.0);
- Assertions.assertEquals(1.0 / 3.0, second.doubleValue(), 0.0);
+ //NUMBERS-120
+ {
+ BigFraction f = BigFraction.of(
+ BigInteger.ONE.shiftLeft(54),
+ BigInteger.ONE.shiftLeft(53).add(BigInteger.ONE));
+ Assertions.assertEquals(2d - 0x1P-52, f.doubleValue());
+ }
}
@Test
[commons-numbers] 12/18: NUMBERS-120: Create assertion helper
methods for readability
Posted by er...@apache.org.
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 6ebd56951f4736b3cb5cf4b87d5ed3a6df5a496c
Author: Schamschi <he...@gmx.at>
AuthorDate: Mon Jul 1 23:29:11 2019 +0200
NUMBERS-120: Create assertion helper methods for readability
---
.../commons/numbers/fraction/BigFractionTest.java | 160 ++++++++++-----------
1 file changed, 78 insertions(+), 82 deletions(-)
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 cb6061d..1663964 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
@@ -27,16 +27,25 @@ import org.junit.jupiter.api.Test;
public class BigFractionTest {
- private void assertFraction(long expectedNumerator, long expectedDenominator, BigFraction actual) {
+ private static void assertFraction(long expectedNumerator, long expectedDenominator, BigFraction actual) {
Assertions.assertEquals(BigInteger.valueOf(expectedNumerator), actual.getNumerator());
Assertions.assertEquals(BigInteger.valueOf(expectedDenominator), actual.getDenominator());
}
- private void assertFraction(BigInteger expectedNumerator, BigInteger expectedDenominator, BigFraction actual) {
+ private static void assertFraction(BigInteger expectedNumerator, BigInteger expectedDenominator, BigFraction actual) {
Assertions.assertEquals(expectedNumerator, actual.getNumerator());
Assertions.assertEquals(expectedDenominator, actual.getDenominator());
}
+ private static void assertDoubleValue(double expected, BigInteger numerator, BigInteger denominator) {
+ BigFraction f = BigFraction.of(numerator, denominator);
+ Assertions.assertEquals(expected, f.doubleValue());
+ }
+
+ private static void assertDoubleValue(double expected, long numerator, long denominator) {
+ assertDoubleValue(expected, BigInteger.valueOf(numerator), BigInteger.valueOf(denominator));
+ }
+
@Test
public void testConstructor() {
for (CommonTestCases.UnaryOperatorTestCase testCase : CommonTestCases.numDenConstructorTestCases()) {
@@ -173,94 +182,81 @@ public class BigFractionTest {
public void testDoubleValue() {
Assertions.assertEquals(0d, BigFraction.ZERO.doubleValue(), 0d);
- {
- BigFraction first = BigFraction.of(1, 2);
- BigFraction second = BigFraction.of(1, 3);
-
- Assertions.assertEquals(0.5, first.doubleValue(), 0.0);
- Assertions.assertEquals(1.0 / 3.0, second.doubleValue(), 0.0);
- }
+ assertDoubleValue(0.5, 1, 2);
+ assertDoubleValue(1.0 / 3.0, 1, 3);
//NUMBERS-120
- Assertions.assertEquals(
+ assertDoubleValue(
2d - 0x1P-52,
- BigFraction.of(
- BigInteger.ONE.shiftLeft(54),
- BigInteger.ONE.shiftLeft(53).add(BigInteger.ONE)
- ).doubleValue());
+ 1L << 54,
+ (1L << 53) + 1L
+ );
- Assertions.assertEquals(
+ assertDoubleValue(
2d,
- BigFraction.of(
- BigInteger.ONE.shiftLeft(54).subtract(BigInteger.ONE),
- BigInteger.ONE.shiftLeft(53)
- ).doubleValue());
- Assertions.assertEquals(
+ (1L << 54) - 1L,
+ 1L << 53
+ );
+ assertDoubleValue(
1d,
- BigFraction.of(
- BigInteger.ONE.shiftLeft(53).add(BigInteger.ONE),
- BigInteger.ONE.shiftLeft(53)
- ).doubleValue());
+ (1L << 53) + 1L,
+ 1L << 53
+ );
}
@Test
public void testDoubleValueForSubnormalNumbers() {
- //test Double.MIN_VALUE * 2/3
- Assertions.assertEquals(
+ assertDoubleValue( //Double.MIN_VALUE * 2/3
Double.MIN_VALUE,
- BigFraction.of(
- BigInteger.ONE,
- BigInteger.ONE.shiftLeft(1073).multiply(BigInteger.valueOf(3L))
- ).doubleValue());
+ BigInteger.ONE,
+ BigInteger.ONE.shiftLeft(1073).multiply(BigInteger.valueOf(3L))
+ );
- Assertions.assertEquals(
+ assertDoubleValue(
Double.MIN_VALUE,
- BigFraction.of(
- BigInteger.ONE,
- BigInteger.ONE.shiftLeft(1074)
- ).doubleValue());
- Assertions.assertEquals(
+ BigInteger.ONE,
+ BigInteger.ONE.shiftLeft(1074)
+ );
+ assertDoubleValue(
Double.MIN_VALUE * 2,
- BigFraction.of(
- BigInteger.valueOf(2),
- BigInteger.ONE.shiftLeft(1074)
- ).doubleValue());
- Assertions.assertEquals(
+ BigInteger.valueOf(2),
+ BigInteger.ONE.shiftLeft(1074)
+ );
+ assertDoubleValue(
Double.MIN_VALUE * 3,
- BigFraction.of(
- BigInteger.valueOf(3),
- BigInteger.ONE.shiftLeft(1074)
- ).doubleValue());
+ BigInteger.valueOf(3),
+ BigInteger.ONE.shiftLeft(1074)
+ );
- Assertions.assertEquals(
+ assertDoubleValue(
Double.MIN_NORMAL - Double.MIN_VALUE,
- BigFraction.of(
- BigInteger.ONE.shiftLeft(52).subtract(BigInteger.ONE),
- BigInteger.ONE.shiftLeft(1074)
- ).doubleValue());
- Assertions.assertEquals(
+ BigInteger.ONE.shiftLeft(52).subtract(BigInteger.ONE),
+ BigInteger.ONE.shiftLeft(1074)
+ );
+ assertDoubleValue(
Double.MIN_NORMAL - 2 * Double.MIN_VALUE,
- BigFraction.of(
- BigInteger.ONE.shiftLeft(52).subtract(BigInteger.valueOf(2)),
- BigInteger.ONE.shiftLeft(1074)
- ).doubleValue());
+ BigInteger.ONE.shiftLeft(52).subtract(BigInteger.valueOf(2)),
+ BigInteger.ONE.shiftLeft(1074)
+ );
}
@Test
public void testDoubleValueForInfinities() {
- Assertions.assertEquals(
+ //the smallest integer that rounds up to Double.POSITIVE_INFINITY
+ BigInteger minInf = BigInteger.ONE
+ .shiftLeft(1024)
+ .subtract(BigInteger.ONE.shiftLeft(970));
+
+ assertDoubleValue(
Double.NEGATIVE_INFINITY,
- BigFraction.of(
- BigInteger.ONE.shiftLeft(1024)
- .subtract(BigInteger.ONE.shiftLeft(970))
- .negate()
- ).doubleValue());
- Assertions.assertEquals(
+ minInf.negate(),
+ BigInteger.ONE
+ );
+ assertDoubleValue(
Double.POSITIVE_INFINITY,
- BigFraction.of(
- BigInteger.ONE.shiftLeft(1024)
- .subtract(BigInteger.ONE.shiftLeft(970))
- ).doubleValue());
+ minInf,
+ BigInteger.ONE
+ );
}
// MATH-744
@@ -300,23 +296,23 @@ public class BigFractionTest {
}
// NUMBERS-120
- {
- BigFraction f = BigFraction.of(
- BigInteger.ONE.shiftLeft(1024)
- .subtract(BigInteger.ONE.shiftLeft(970))
- .add(BigInteger.ONE),
- BigInteger.valueOf(3));
- Assertions.assertEquals(5.992310449541053E307, f.doubleValue());
- }
+ assertDoubleValue(
+ 5.992310449541053E307,
+ BigInteger.ONE
+ .shiftLeft(1024)
+ .subtract(BigInteger.ONE.shiftLeft(970))
+ .add(BigInteger.ONE),
+ BigInteger.valueOf(3)
+ );
- {
- BigFraction f = BigFraction.of(
- BigInteger.ONE.shiftLeft(1025)
- .subtract(BigInteger.ONE.shiftLeft(972))
- .subtract(BigInteger.ONE),
- BigInteger.valueOf(2));
- Assertions.assertEquals(Double.MAX_VALUE, f.doubleValue());
- }
+ assertDoubleValue(
+ Double.MAX_VALUE,
+ BigInteger.ONE
+ .shiftLeft(1025)
+ .subtract(BigInteger.ONE.shiftLeft(972))
+ .subtract(BigInteger.ONE),
+ BigInteger.valueOf(2)
+ );
}
// NUMBERS-15
[commons-numbers] 10/18: NUMBERS-120: Remove redundant conditional
branch
Posted by er...@apache.org.
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 504f82b68c2bb597f11985a0599969139e117f2b
Author: Schamschi <he...@gmx.at>
AuthorDate: Fri Jun 28 01:29:49 2019 +0200
NUMBERS-120: Remove redundant conditional branch
---
.../commons/numbers/fraction/BigFraction.java | 27 ++++++++++------------
1 file changed, 12 insertions(+), 15 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 c5410b0..3487dda 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
@@ -835,22 +835,19 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
private static BigInteger roundAndRightShift(BigInteger value, int bits, boolean hasFractionalBits) {
if (bits <= 0) {
throw new IllegalArgumentException();
- } else if (bits > value.bitLength()) {
- return BigInteger.ZERO;
- } else {
- boolean roundUp = false;
- if (value.testBit(bits - 1)
- && (hasFractionalBits
- || (value.getLowestSetBit() < bits - 1)
- || value.testBit(bits))) {
- roundUp = true;
- }
- BigInteger result = value.shiftRight(bits);
- if (roundUp) {
- result = result.add(BigInteger.ONE);
- }
- return result;
}
+ boolean roundUp = false;
+ if (value.testBit(bits - 1)
+ && (hasFractionalBits
+ || (value.getLowestSetBit() < bits - 1)
+ || value.testBit(bits))) {
+ roundUp = true;
+ }
+ BigInteger result = value.shiftRight(bits);
+ if (roundUp) {
+ result = result.add(BigInteger.ONE);
+ }
+ return result;
}
/**
[commons-numbers] 16/18: NUMBERS-120: Report argument values in
IllegalArgumentException messages
Posted by er...@apache.org.
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 26c9e7f0c9962ffaed9743e8584f5e2809ecabed
Author: Schamschi <he...@gmx.at>
AuthorDate: Sat Jul 13 18:53:32 2019 +0200
NUMBERS-120: Report argument values in IllegalArgumentException messages
---
.../java/org/apache/commons/numbers/fraction/BigFraction.java | 11 +++++++----
1 file changed, 7 insertions(+), 4 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 a9a50ee..f2bac32 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
@@ -671,18 +671,20 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* sign.
* @param exponentLength the number of bits allowed for the exponent; must be
* between 1 and 32 (inclusive), and must not be greater
- * than 63 - significandLength
+ * than {@code 63 - significandLength}
* @param significandLength the number of bits allowed for the significand
* (excluding the implicit leading 1-bit in
* normalized numbers, e.g. 52 for a double-precision
* floating-point number); must be between 1 and
- * (63 - exponentLength) (inclusive)
+ * {@code 63 - exponentLength} (inclusive)
* @return the bits of an IEEE 754 binary floating-point representation of
* this fraction encoded in a {@code long}, as described above.
+ * @throws IllegalArgumentException if the arguments do not meet the
+ * criteria described above
*/
private long toFloatingPointBits(int exponentLength, int significandLength) {
if (exponentLength < 1 ||significandLength < 1 || exponentLength > Math.min(32, 63 - significandLength)) {
- throw new IllegalArgumentException();
+ throw new IllegalArgumentException("exponent length: " + exponentLength + "; significand length: " + significandLength);
}
if (numerator.signum() == 0) {
return 0L;
@@ -841,10 +843,11 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* @param hasFractionalBits whether the number should be treated as though
* it contained a non-zero fractional part
* @return a {@code BigInteger} as described above
+ * @throws IllegalArgumentException if {@code bits <= 0}
*/
private static BigInteger roundAndRightShift(BigInteger value, int bits, boolean hasFractionalBits) {
if (bits <= 0) {
- throw new IllegalArgumentException();
+ throw new IllegalArgumentException("bits: " + bits);
}
BigInteger result = value.shiftRight(bits);
if (value.testBit(bits - 1) &&
[commons-numbers] 06/18: NUMBERS-120: Repair
BigFraction.floatValue()
Posted by er...@apache.org.
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 fd1292e588bfbd0b0b63ae56cf316faf2df00537
Author: Schamschi <he...@gmx.at>
AuthorDate: Wed Jun 26 03:31:01 2019 +0200
NUMBERS-120: Repair BigFraction.floatValue()
---
.../org/apache/commons/numbers/fraction/BigFraction.java | 15 +--------------
1 file changed, 1 insertion(+), 14 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 6de8f37..3a1a63d 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
@@ -887,20 +887,7 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
*/
@Override
public float floatValue() {
- float floatNum = numerator.floatValue();
- float floatDen = denominator.floatValue();
- float result = floatNum / floatDen;
- if (Float.isInfinite(floatNum) ||
- Float.isInfinite(floatDen) ||
- Float.isNaN(result)) {
- // Numerator and/or denominator must be out of range:
- // Calculate how far to shift them to put them in range.
- int shift = Math.max(numerator.bitLength(),
- denominator.bitLength()) - Math.getExponent(Float.MAX_VALUE);
- result = numerator.shiftRight(shift).floatValue() /
- denominator.shiftRight(shift).floatValue();
- }
- return result;
+ return Float.intBitsToFloat((int) toFloatingPointBits(8, 23));
}
/**
[commons-numbers] 11/18: NUMBERS-120: Satisfy checkstyle
requirements
Posted by er...@apache.org.
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 1abb1d8c1d57ce497b30e7145eb3499143f0f79e
Author: Schamschi <he...@gmx.at>
AuthorDate: Mon Jul 1 16:55:21 2019 +0200
NUMBERS-120: Satisfy checkstyle requirements
---
.../java/org/apache/commons/numbers/fraction/BigFraction.java | 8 ++++----
1 file changed, 4 insertions(+), 4 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 3487dda..7737228 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
@@ -837,10 +837,10 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
throw new IllegalArgumentException();
}
boolean roundUp = false;
- if (value.testBit(bits - 1)
- && (hasFractionalBits
- || (value.getLowestSetBit() < bits - 1)
- || value.testBit(bits))) {
+ if (value.testBit(bits - 1) &&
+ (hasFractionalBits ||
+ (value.getLowestSetBit() < bits - 1) ||
+ value.testBit(bits))) {
roundUp = true;
}
BigInteger result = value.shiftRight(bits);
[commons-numbers] 14/18: NUMBERS-120: Add comment about previously
neglected corner case that was luckily already handled correctly
Posted by er...@apache.org.
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 e89aaadec3b431c4e2f979c778d22c929f180803
Author: Schamschi <he...@gmx.at>
AuthorDate: Thu Jul 4 01:44:01 2019 +0200
NUMBERS-120: Add comment about previously neglected corner case that was luckily already handled correctly
---
.../java/org/apache/commons/numbers/fraction/BigFraction.java | 10 ++++++++++
1 file changed, 10 insertions(+)
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 a73a643..a9a50ee 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
@@ -800,6 +800,16 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
!divisor.equals(BigInteger.ONE)
).longValue();
exponent = 0L;
+
+ /*
+ * Note: It is possible that an otherwise subnormal number will
+ * round up to the smallest normal number. However, this special
+ * case does not need to be treated separately, because the
+ * overflowing highest-order bit of the significand will then simply
+ * become the lowest-order bit of the exponent, increasing the
+ * exponent from 0 to 1 and thus establishing the implicity of the
+ * leading 1-bit.
+ */
}
return (sign << (significandLength + exponentLength)) | (exponent << significandLength) | significand;
}
[commons-numbers] 01/18: NUMBERS-132: Perform gcd algorithm on
negative numbers in ArithmeticUtils.gcd(int, int)
Posted by er...@apache.org.
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 89ce65de33085f345e72b1f34473e1386f96a923
Author: Schamschi <he...@gmx.at>
AuthorDate: Sat Jul 20 01:52:52 2019 +0200
NUMBERS-132: Perform gcd algorithm on negative numbers in ArithmeticUtils.gcd(int, int)
---
.../commons/numbers/core/ArithmeticUtils.java | 142 ++++++---------------
1 file changed, 37 insertions(+), 105 deletions(-)
diff --git a/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java b/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
index 8895328..b6bbc45 100644
--- a/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
+++ b/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java
@@ -26,8 +26,6 @@ import java.text.MessageFormat;
*/
public final class ArithmeticUtils {
- /** Overflow gcd exception message for 2^31. */
- private static final String OVERFLOW_GCD_MESSAGE_2_POWER_31 = "overflow: gcd({0}, {1}) is 2^31";
/** Overflow gcd exception message for 2^63. */
private static final String OVERFLOW_GCD_MESSAGE_2_POWER_63 = "overflow: gcd({0}, {1}) is 2^63";
@@ -69,114 +67,48 @@ public final class ArithmeticUtils {
* a non-negative {@code int} value.
*/
public static int gcd(int p, int q) {
- int a = p;
- int b = q;
- if (a == 0 ||
- b == 0) {
- if (a == Integer.MIN_VALUE ||
- b == Integer.MIN_VALUE) {
- throw new NumbersArithmeticException(OVERFLOW_GCD_MESSAGE_2_POWER_31,
- p, q);
- }
- return Math.abs(a + b);
- }
+ // Perform the gcd algorithm on negative numbers, so that -2^31 does not
+ // need to be handled separately
+ int a = p > 0 ? -p : p;
+ int b = q > 0 ? -q : q;
- long al = a;
- long bl = b;
- boolean useLong = false;
- if (a < 0) {
- if(Integer.MIN_VALUE == a) {
- useLong = true;
- } else {
- a = -a;
- }
- al = -al;
- }
- if (b < 0) {
- if (Integer.MIN_VALUE == b) {
- useLong = true;
- } else {
- b = -b;
- }
- bl = -bl;
- }
- if (useLong) {
- if(al == bl) {
- throw new NumbersArithmeticException(OVERFLOW_GCD_MESSAGE_2_POWER_31,
- p, q);
- }
- long blbu = bl;
- bl = al;
- al = blbu % al;
- if (al == 0) {
- if (bl > Integer.MAX_VALUE) {
- throw new NumbersArithmeticException(OVERFLOW_GCD_MESSAGE_2_POWER_31,
- p, q);
- }
- return (int) bl;
+ int negatedGcd;
+ if (a == 0) {
+ negatedGcd = b;
+ } else if (b == 0) {
+ negatedGcd = a;
+ } else {
+ // Make "a" and "b" odd, keeping track of common power of 2.
+ final int aTwos = Integer.numberOfTrailingZeros(a);
+ final int bTwos = Integer.numberOfTrailingZeros(b);
+ a >>= aTwos;
+ b >>= bTwos;
+ final int shift = Math.min(aTwos, bTwos);
+
+ // "a" and "b" are negative and odd.
+ // If a < b then "gdc(a, b)" is equal to "gcd(a - b, b)".
+ // If a > b then "gcd(a, b)" is equal to "gcd(b - a, a)".
+ // Hence, in the successive iterations:
+ // "a" becomes the negative absolute difference of the current values,
+ // "b" becomes that value of the two that is closer to zero.
+ while (a != b) {
+ final int delta = a - b;
+ b = Math.max(a, b);
+ a = delta > 0 ? -delta : delta;
+
+ // Remove any power of 2 in "a" ("b" is guaranteed to be odd).
+ a >>= Integer.numberOfTrailingZeros(a);
}
- blbu = bl;
-
- // Now "al" and "bl" fit in an "int".
- b = (int) al;
- a = (int) (blbu % al);
- }
-
- return gcdPositive(a, b);
- }
- /**
- * Computes the greatest common divisor of two <em>positive</em> numbers
- * (this precondition is <em>not</em> checked and the result is undefined
- * if not fulfilled) using the "binary gcd" method which avoids division
- * and modulo operations.
- * See Knuth 4.5.2 algorithm B.
- * The algorithm is due to Josef Stein (1961).
- * <br/>
- * Special cases:
- * <ul>
- * <li>The result of {@code gcd(x, x)}, {@code gcd(0, x)} and
- * {@code gcd(x, 0)} is the value of {@code x}.</li>
- * <li>The invocation {@code gcd(0, 0)} is the only one which returns
- * {@code 0}.</li>
- * </ul>
- *
- * @param a Positive number.
- * @param b Positive number.
- * @return the greatest common divisor.
- */
- private static int gcdPositive(int a, int b) {
- if (a == 0) {
- return b;
+ // Recover the common power of 2.
+ negatedGcd = a << shift;
}
- else if (b == 0) {
- return a;
- }
-
- // Make "a" and "b" odd, keeping track of common power of 2.
- final int aTwos = Integer.numberOfTrailingZeros(a);
- a >>= aTwos;
- final int bTwos = Integer.numberOfTrailingZeros(b);
- b >>= bTwos;
- final int shift = Math.min(aTwos, bTwos);
-
- // "a" and "b" are positive.
- // If a > b then "gdc(a, b)" is equal to "gcd(a - b, b)".
- // If a < b then "gcd(a, b)" is equal to "gcd(b - a, a)".
- // Hence, in the successive iterations:
- // "a" becomes the absolute difference of the current values,
- // "b" becomes the minimum of the current values.
- while (a != b) {
- final int delta = a - b;
- b = Math.min(a, b);
- a = Math.abs(delta);
-
- // Remove any power of 2 in "a" ("b" is guaranteed to be odd).
- a >>= Integer.numberOfTrailingZeros(a);
+ if (negatedGcd == Integer.MIN_VALUE) {
+ throw new NumbersArithmeticException("overflow: gcd({0}, {1}) is 2^31",
+ p, q);
+ } else {
+ return -negatedGcd;
}
-
- // Recover the common power of 2.
- return a << shift;
}
/**
[commons-numbers] 02/18: Merge branch 'NUMBERS-132__heinrich'
Posted by er...@apache.org.
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 f1f4ddca43eb67573a356e052fdd7cd70daedf7d
Merge: 08962e8 89ce65d
Author: Gilles Sadowski <gi...@harfang.homelinux.org>
AuthorDate: Thu Aug 8 18:29:43 2019 +0200
Merge branch 'NUMBERS-132__heinrich'
Closes #67.
.../commons/numbers/core/ArithmeticUtils.java | 142 ++++++---------------
1 file changed, 37 insertions(+), 105 deletions(-)
[commons-numbers] 05/18: NUMBERS-120: Extract functionality of
doubleValue() to helper method for reuse in floatValue()
Posted by er...@apache.org.
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 1712ee65ed09d1813aebde55b2d96c6aa05a2c9f
Author: Schamschi <he...@gmx.at>
AuthorDate: Wed Jun 26 02:35:38 2019 +0200
NUMBERS-120: Extract functionality of doubleValue() to helper method for reuse in floatValue()
---
.../commons/numbers/fraction/BigFraction.java | 141 +++++++++++++--------
1 file changed, 86 insertions(+), 55 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 d9efcaf..6de8f37 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
@@ -661,63 +661,75 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
}
/**
- * <p>
- * Gets the fraction as a {@code double}. This calculates the fraction as
- * the numerator divided by denominator.
- * </p>
- *
- * @return the fraction as a {@code double}
- * @see java.lang.Number#doubleValue()
+ * Calculates the sign bit, the biased exponent and the significand for a
+ * binary floating-point representation of this {@code BigFraction}
+ * according to the IEEE 754 standard, and encodes these values into a {@code long}
+ * variable. The representative bits are arranged adjacent to each other and
+ * placed at the low-order end of the returned {@code long} value, with the
+ * least significant bits used for the significand, the next more
+ * significant bits for the exponent, and next more significant bit for the
+ * sign.
+ * @param exponentLength the number of bits allowed for the exponent; must be
+ * between 1 and 32 (inclusive), and must not be greater
+ * than 63 - significandLength
+ * @param significandLength the number of bits allowed for the significand
+ * (excluding the implicit leading 1-bit in
+ * normalized numbers, e.g. 52 for a double-precision
+ * floating-point number); must be between 1 and
+ * (63 - exponentLength) (inclusive)
+ * @return the bits of an IEEE 754 binary floating-point representation of
+ * this fraction encoded in a {@code long}, as described above.
*/
- @Override
- public double doubleValue() {
+ private long toFloatingPointBits(int exponentLength, int significandLength) {
+ if (exponentLength < 1 ||significandLength < 1 || exponentLength > Math.min(32, 63 - significandLength)) {
+ throw new IllegalArgumentException();
+ }
if (numerator.signum() == 0) {
- return 0;
+ return 0L;
}
- /*
- * We will manually construct a long from which to create the double to
- * ensure maximum precision. First, we set the sign:
- */
long sign = numerator.signum() == -1 ? 1L : 0L;
BigInteger positiveNumerator = numerator.abs();
/*
- * The significand of a double value consists of 52 bits for the
- * fractional part, plus the implicit leading 1 bit for the
- * non-fractional part, which makes 53 bits in total. So we need to
- * calculate the most significant 54 bits of this fraction's quotient,
- * and then, based on the 54th most significant bit, find out whether
- * we need to round up or down.
+ * The most significant 1-bit of a non-zero number is not explicitly
+ * stored in the significand of an IEEE 754 normalized binary
+ * floating-point number, so we need to round the value of this fraction
+ * to (significandLength + 1) bits. In order to do this, we calculate
+ * the most significant (significandLength + 2) bits, and then, based on
+ * the least significant of those bits, find out whether we need to
+ * round up or down.
*
* First, we'll remove all powers of 2 from the denominator because they
- * are not relevant for the significand of the prospective double value.
+ * are not relevant for the significand of the prospective binary
+ * floating-point value.
*/
int denRightShift = denominator.getLowestSetBit();
BigInteger divisor = denominator.shiftRight(denRightShift);
/*
- * Now, we're going to calculate the 54 most significant bits of the
- * quotient using integer division. To guarantee that the quotient has
- * at least 54 bits, the bit length of the dividend must exceed that
- * of the divisor by at least 54. If the numerator has powers of 2
- * beyond this limit, they can be removed as well.
+ * Now, we're going to calculate the (significandLength + 2) most
+ * significant bits of the fraction's value using integer division. To
+ * guarantee that the quotient of the division has at least
+ * (significandLength + 2) bits, the bit length of the dividend must
+ * exceed that of the divisor by at least that amount. If the numerator
+ * has powers of 2 beyond this limit, they can be removed as well.
*/
- int numRightShift = positiveNumerator.bitLength() - divisor.bitLength() - 54;
+ int numRightShift = positiveNumerator.bitLength() - divisor.bitLength() - (significandLength + 2);
if (numRightShift > 0) {
numRightShift = Math.min(numRightShift, positiveNumerator.getLowestSetBit());
}
BigInteger dividend = positiveNumerator.shiftRight(numRightShift);
BigInteger quotient = dividend.divide(divisor);
- int quotRightShift = quotient.bitLength() - 53;
/*
* If the denominator was a power of two, then the divisor was reduced
- * 1, meaning the quotient was calculated exactly. Otherwise, the
+ * to 1, meaning the quotient was calculated exactly. Otherwise, the
* fractional part of the precise quotient's binary representation does
* not terminate.
*/
+ int quotRightShift = quotient.bitLength() - (significandLength + 1);
long significand = roundAndRightShift(
quotient,
quotRightShift,
@@ -725,60 +737,79 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
).longValue();
/*
- * If the significand had to be rounded up, this could have caused an
- * overflow into the 54th least significant bit.
+ * If the significand had to be rounded up, this could have caused the
+ * bit length of the significand to increase by one.
*/
- if ((significand & (1L << 53)) != 0) {
+ if ((significand & (1L << (significandLength + 1))) != 0) {
significand >>= 1;
quotRightShift++;
}
/*
- * Now comes the exponent. The absolute value of this fraction based
- * on the current local variables is:
+ * Now comes the exponent. The absolute value of this fraction based on
+ * the current local variables is:
*
* significand * 2^(numRightShift - denRightShift + quotRightShift)
*
- * To get the unbiased exponent for the double value, we need to add 52
- * to the above exponent, because the 52 least significant bits of
- * significant will be treated as a fractional part. To convert the
- * unbiased exponent to a biased exponent, we need to add 1023.
+ * To get the unbiased exponent for the floating-point value, we need to
+ * add (significandLength) to the above exponent, because all but the
+ * most significant bit of the significand will be treated as a
+ * fractional part. To convert the unbiased exponent to a biased
+ * exponent, we also need to add the exponent bias.
*/
- long exponent = numRightShift - denRightShift + quotRightShift + 52 + 1023;
+ int exponentBias = (1 << (exponentLength - 1)) - 1;
+ long exponent = numRightShift - denRightShift + quotRightShift + significandLength + exponentBias;
+ long maxExponent = (1L << exponentLength) - 1L; //special exponent for infinities and NaN
- if (exponent > 2046) { //infinity
- exponent = 2047;
- significand = 0;
+ if (exponent >= maxExponent) { //infinity
+ exponent = maxExponent;
+ significand = 0L;
} else if (exponent > 0) { //normalized number
- significand &= 0x000FFFFFFFFFFFFFL; //remove implicit leading 1-bit
+ significand &= -1L >>> (64 - significandLength); //remove implicit leading 1-bit
} else { //smaller than the smallest normalized number
/*
- * We need to round the quotient to fewer than 53 bits. This must
- * be done with the original quotient and not with the current
- * significand, because the loss of precision in the rounding to 53
- * bits might cause a rounding of the current significand's value
- * to produce a different result than a rounding of the
- * original quotient.
+ * We need to round the quotient to fewer than
+ * (significandLength + 1) bits. This must be done with the original
+ * quotient and not with the current significand, because the loss
+ * of precision in the previous rounding might cause a rounding of
+ * the current significand's value to produce a different result
+ * than a rounding of the original quotient.
*
* So we find out how many high-order bits from the quotient we can
- * squeeze into the significand. The absolute value of the fraction
+ * transfer into the significand. The absolute value of the fraction
* is:
*
* quotient * 2^(numRightShift - denRightShift)
*
* To get the significand, we need to right shift the quotient so
- * that the above exponent becomes (- 1022 - 52) = -1074 (-1022 is
- * the unbiased exponent of a subnormal double value, and 52 because
- * the significand will be treated as the fractional part)
+ * that the above exponent becomes (1 - exponentBias - significandLength)
+ * (the unbiased exponent of a subnormal floating-point number is
+ * defined as equivalent to the minimum unbiased exponent of a
+ * normalized floating-point number, and (- significandLength)
+ * because the significand will be treated as the fractional part).
*/
significand = roundAndRightShift(
quotient,
- - 1074 - (numRightShift - denRightShift),
+ (1 - exponentBias - significandLength) - (numRightShift - denRightShift),
!divisor.equals(BigInteger.ONE)
).longValue();
exponent = 0L;
}
- return Double.longBitsToDouble((sign << 63) | (exponent << 52) | significand);
+ return (sign << (significandLength + exponentLength)) | (exponent << significandLength) | significand;
+ }
+
+ /**
+ * <p>
+ * Gets the fraction as a {@code double}. This calculates the fraction as
+ * the numerator divided by denominator.
+ * </p>
+ *
+ * @return the fraction as a {@code double}
+ * @see java.lang.Number#doubleValue()
+ */
+ @Override
+ public double doubleValue() {
+ return Double.longBitsToDouble(toFloatingPointBits(11, 52));
}
/**
[commons-numbers] 15/18: NUMBERS-120: Add unit test for rounding up
from subnormal to normal number
Posted by er...@apache.org.
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 404ff82de649dfa503dcd9c1de87ee4f31431920
Author: Schamschi <he...@gmx.at>
AuthorDate: Thu Jul 4 13:31:53 2019 +0200
NUMBERS-120: Add unit test for rounding up from subnormal to normal number
---
.../java/org/apache/commons/numbers/fraction/BigFractionTest.java | 7 +++++++
1 file changed, 7 insertions(+)
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 1663964..c36aa15 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
@@ -238,6 +238,13 @@ public class BigFractionTest {
BigInteger.ONE.shiftLeft(52).subtract(BigInteger.valueOf(2)),
BigInteger.ONE.shiftLeft(1074)
);
+
+ //this number is smaller than Double.MIN_NORMAL, but should round up to it
+ assertDoubleValue(
+ Double.MIN_NORMAL,
+ BigInteger.ONE.shiftLeft(53).subtract(BigInteger.ONE),
+ BigInteger.ONE.shiftLeft(1075)
+ );
}
@Test
[commons-numbers] 08/18: NUMBERS-120: Don't calculate more bits
than necessary in toFloatingPointBits(int, int)
Posted by er...@apache.org.
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 167f004f167c5177c7944e4c1f5e9d72dcbd1843
Author: Schamschi <he...@gmx.at>
AuthorDate: Thu Jun 27 14:50:01 2019 +0200
NUMBERS-120: Don't calculate more bits than necessary in toFloatingPointBits(int, int)
---
.../commons/numbers/fraction/BigFraction.java | 24 ++++++++++++++--------
1 file changed, 15 insertions(+), 9 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 3a1a63d..c5410b0 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
@@ -712,23 +712,29 @@ public class BigFraction extends Number implements Comparable<BigFraction>, Seri
* significant bits of the fraction's value using integer division. To
* guarantee that the quotient of the division has at least
* (significandLength + 2) bits, the bit length of the dividend must
- * exceed that of the divisor by at least that amount. If the numerator
- * has powers of 2 beyond this limit, they can be removed as well.
+ * exceed that of the divisor by at least that amount.
+ *
+ * If the denominator has prime factors other than 2, i.e. if the
+ * divisor was not reduced to 1, an excess of exactly
+ * (significandLength + 2) bits is sufficient, because the knowledge
+ * that the fractional part of the precise quotient's binary
+ * representation does not terminate is enough information to resolve
+ * cases where the most significant (significandLength + 2) bits alone
+ * are not conclusive.
+ *
+ * Otherwise, the quotient must be calculated exactly and the bit length
+ * of the numerator can only be reduced as long as no precision is lost
+ * in the process (meaning it can have powers of 2 removed, like the
+ * denominator).
*/
int numRightShift = positiveNumerator.bitLength() - divisor.bitLength() - (significandLength + 2);
- if (numRightShift > 0) {
+ if (numRightShift > 0 && divisor.equals(BigInteger.ONE)) {
numRightShift = Math.min(numRightShift, positiveNumerator.getLowestSetBit());
}
BigInteger dividend = positiveNumerator.shiftRight(numRightShift);
BigInteger quotient = dividend.divide(divisor);
- /*
- * If the denominator was a power of two, then the divisor was reduced
- * to 1, meaning the quotient was calculated exactly. Otherwise, the
- * fractional part of the precise quotient's binary representation does
- * not terminate.
- */
int quotRightShift = quotient.bitLength() - (significandLength + 1);
long significand = roundAndRightShift(
quotient,
[commons-numbers] 18/18: Merge branch 'NUMBERS-120__heinrich'
Posted by er...@apache.org.
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 5a0d8f5905f4440f7ee0ec5219e8bfeaf7d11300
Merge: f1f4ddc 5d4485d
Author: Gilles Sadowski <gi...@harfang.homelinux.org>
AuthorDate: Thu Aug 8 19:17:34 2019 +0200
Merge branch 'NUMBERS-120__heinrich'
Closes #63.
.../commons/numbers/fraction/BigFraction.java | 219 ++++++++++++++++++---
.../commons/numbers/fraction/BigFractionTest.java | 133 +++++++++++--
2 files changed, 314 insertions(+), 38 deletions(-)
[commons-numbers] 07/18: NUMBERS-120: Make doubleValue() tests
independent of double constructor
Posted by er...@apache.org.
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 0c070c16f9271022ab09c8267b672987aa2c9d6e
Author: Schamschi <he...@gmx.at>
AuthorDate: Thu Jun 27 11:52:16 2019 +0200
NUMBERS-120: Make doubleValue() tests independent of double constructor
---
.../commons/numbers/fraction/BigFractionTest.java | 56 ++++++++++++----------
1 file changed, 31 insertions(+), 25 deletions(-)
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 e20113e..950e7cc 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
@@ -190,31 +190,37 @@ public class BigFractionTest {
@Test
public void testDoubleValueForSubnormalNumbers() {
- {
- double min = Double.MIN_VALUE;
- double min1Up = Math.nextUp(min);
- double min2Up = Math.nextUp(min1Up);
- Assertions.assertEquals(
- min,
- BigFraction.from(min).doubleValue());
- Assertions.assertEquals(
- min1Up,
- BigFraction.from(min1Up).doubleValue());
- Assertions.assertEquals(
- min2Up,
- BigFraction.from(min2Up).doubleValue());
- }
-
- {
- double minNormal1Down = Math.nextDown(Double.MIN_NORMAL);
- double minNormal2Down = Math.nextDown(minNormal1Down);
- Assertions.assertEquals(
- minNormal1Down,
- BigFraction.from(minNormal1Down).doubleValue());
- Assertions.assertEquals(
- minNormal2Down,
- BigFraction.from(minNormal2Down).doubleValue());
- }
+ Assertions.assertEquals(
+ Double.MIN_VALUE,
+ BigFraction.of(
+ BigInteger.ONE,
+ BigInteger.ONE.shiftLeft(1074)
+ ).doubleValue());
+ Assertions.assertEquals(
+ Double.MIN_VALUE * 2,
+ BigFraction.of(
+ BigInteger.valueOf(2),
+ BigInteger.ONE.shiftLeft(1074)
+ ).doubleValue());
+ Assertions.assertEquals(
+ Double.MIN_VALUE * 3,
+ BigFraction.of(
+ BigInteger.valueOf(3),
+ BigInteger.ONE.shiftLeft(1074)
+ ).doubleValue());
+
+ Assertions.assertEquals(
+ Double.MIN_NORMAL - Double.MIN_VALUE,
+ BigFraction.of(
+ BigInteger.ONE.shiftLeft(52).subtract(BigInteger.ONE),
+ BigInteger.ONE.shiftLeft(1074)
+ ).doubleValue());
+ Assertions.assertEquals(
+ Double.MIN_NORMAL - 2 * Double.MIN_VALUE,
+ BigFraction.of(
+ BigInteger.ONE.shiftLeft(52).subtract(BigInteger.valueOf(2)),
+ BigInteger.ONE.shiftLeft(1074)
+ ).doubleValue());
}
// MATH-744