This is an automated email from the ASF dual-hosted git repository. aherbert pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
commit 286932d1306606e927c417409c14bb49751c61f8 Author: aherbert <[email protected]> AuthorDate: Wed Feb 16 11:29:38 2022 +0000 NUMBERS-184: Reduce operations in Precision.equals using a maxUlps --- .../org/apache/commons/numbers/core/Precision.java | 78 +++++++--------------- .../apache/commons/numbers/core/PrecisionTest.java | 59 +++++++++++++--- src/changes/changes.xml | 3 + 3 files changed, 74 insertions(+), 66 deletions(-) diff --git a/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/Precision.java b/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/Precision.java index e918fb7..323c338 100644 --- a/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/Precision.java +++ b/commons-numbers-core/src/main/java/org/apache/commons/numbers/core/Precision.java @@ -49,20 +49,8 @@ public final class Precision { /** Exponent offset in IEEE754 representation. */ private static final long EXPONENT_OFFSET = 1023L; - /** Offset to order signed double numbers lexicographically. */ - private static final long SGN_MASK = 0x8000000000000000L; - /** Offset to order signed double numbers lexicographically. */ - private static final int SGN_MASK_FLOAT = 0x80000000; /** Positive zero. */ private static final double POSITIVE_ZERO = 0d; - /** Positive zero bits. */ - private static final long POSITIVE_ZERO_DOUBLE_BITS = Double.doubleToRawLongBits(+0.0); - /** Negative zero bits. */ - private static final long NEGATIVE_ZERO_DOUBLE_BITS = Double.doubleToRawLongBits(-0.0); - /** Positive zero bits. */ - private static final int POSITIVE_ZERO_FLOAT_BITS = Float.floatToRawIntBits(+0.0f); - /** Negative zero bits. */ - private static final int NEGATIVE_ZERO_FLOAT_BITS = Float.floatToRawIntBits(-0.0f); static { /* @@ -238,32 +226,21 @@ public final class Precision { * point values between {@code x} and {@code y}. */ public static boolean equals(final float x, final float y, final int maxUlps) { - final int xInt = Float.floatToRawIntBits(x); final int yInt = Float.floatToRawIntBits(y); final boolean isEqual; - if (((xInt ^ yInt) & SGN_MASK_FLOAT) == 0) { - // number have same sign, there is no risk of overflow - isEqual = Math.abs(xInt - yInt) <= maxUlps; + if ((xInt ^ yInt) < 0) { + // Numbers have opposite signs, take care of overflow. + // Remove the sign bit to obtain the absolute ULP above zero. + final int deltaPlus = xInt & Integer.MAX_VALUE; + final int deltaMinus = yInt & Integer.MAX_VALUE; + + // Avoid possible overflow from adding the deltas by using a long. + isEqual = (long) deltaPlus + deltaMinus <= maxUlps; } else { - // number have opposite signs, take care of overflow - final int deltaPlus; - final int deltaMinus; - if (xInt < yInt) { - deltaPlus = yInt - POSITIVE_ZERO_FLOAT_BITS; - deltaMinus = xInt - NEGATIVE_ZERO_FLOAT_BITS; - } else { - deltaPlus = xInt - POSITIVE_ZERO_FLOAT_BITS; - deltaMinus = yInt - NEGATIVE_ZERO_FLOAT_BITS; - } - - if (deltaPlus > maxUlps) { - isEqual = false; - } else { - isEqual = deltaMinus <= (maxUlps - deltaPlus); - } - + // Numbers have same sign, there is no risk of overflow. + isEqual = Math.abs(xInt - yInt) <= maxUlps; } return isEqual && !Float.isNaN(x) && !Float.isNaN(y); @@ -393,35 +370,26 @@ public final class Precision { * point values between {@code x} and {@code y}. */ public static boolean equals(final double x, final double y, final int maxUlps) { - final long xInt = Double.doubleToRawLongBits(x); final long yInt = Double.doubleToRawLongBits(y); - final boolean isEqual; - if (((xInt ^ yInt) & SGN_MASK) == 0L) { - // number have same sign, there is no risk of overflow - isEqual = Math.abs(xInt - yInt) <= maxUlps; - } else { - // number have opposite signs, take care of overflow - final long deltaPlus; - final long deltaMinus; - if (xInt < yInt) { - deltaPlus = yInt - POSITIVE_ZERO_DOUBLE_BITS; - deltaMinus = xInt - NEGATIVE_ZERO_DOUBLE_BITS; - } else { - deltaPlus = xInt - POSITIVE_ZERO_DOUBLE_BITS; - deltaMinus = yInt - NEGATIVE_ZERO_DOUBLE_BITS; - } + if ((xInt ^ yInt) < 0) { + // Numbers have opposite signs, take care of overflow. + // Remove the sign bit to obtain the absolute ULP above zero. + final long deltaPlus = xInt & Long.MAX_VALUE; + final long deltaMinus = yInt & Long.MAX_VALUE; - if (deltaPlus > maxUlps) { - isEqual = false; - } else { - isEqual = deltaMinus <= (maxUlps - deltaPlus); - } + // Note: + // If either value is NaN, the exponent bits are set to (2047L << 52) and the + // distance above 0.0 is always above an integer ULP error. So omit the test + // for NaN and return directly. + // Avoid possible overflow from adding the deltas by splitting the comparison + return deltaPlus <= maxUlps && deltaMinus <= (maxUlps - deltaPlus); } - return isEqual && !Double.isNaN(x) && !Double.isNaN(y); + // Numbers have same sign, there is no risk of overflow. + return Math.abs(xInt - yInt) <= maxUlps && !Double.isNaN(x) && !Double.isNaN(y); } /** diff --git a/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/PrecisionTest.java b/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/PrecisionTest.java index 338557e..08a8820 100644 --- a/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/PrecisionTest.java +++ b/commons-numbers-core/src/test/java/org/apache/commons/numbers/core/PrecisionTest.java @@ -29,7 +29,7 @@ import org.junit.jupiter.api.Test; */ class PrecisionTest { - // Interfaces to allow testing equals variants with the same conditions + // Interfaces to allow testing equals variants with the same conditions. @FunctionalInterface private interface EqualsWithDelta { @@ -123,23 +123,25 @@ class PrecisionTest { @Test void testEqualsWithAllowedUlps() { - assertEqualsIncludingNaNWithAllowedUlps(Precision::equals, false, false); + assertEqualsWithAllowedUlps(Precision::equals, false, false); } @Test void testEqualsWithImplicitAllowedUlpsOf1() { // Use the version without the ulp argument - assertEqualsIncludingNaNWithAllowedUlps((a, b, ulp) -> Precision.equals(a, b), false, true); + assertEqualsWithAllowedUlps((a, b, ulp) -> Precision.equals(a, b), false, true); } @Test void testEqualsIncludingNaNWithAllowedUlps() { - assertEqualsIncludingNaNWithAllowedUlps(Precision::equalsIncludingNaN, true, false); + assertEqualsWithAllowedUlps(Precision::equalsIncludingNaN, true, false); } - private static void assertEqualsIncludingNaNWithAllowedUlps(EqualsWithUlps fun, + private static void assertEqualsWithAllowedUlps(EqualsWithUlps fun, boolean nanAreEqual, boolean fixed1Ulp) { Assertions.assertTrue(fun.equals(0.0, -0.0, 1)); + Assertions.assertTrue(fun.equals(Double.MIN_VALUE, -0.0, 1)); + Assertions.assertFalse(fun.equals(Double.MIN_VALUE, -Double.MIN_VALUE, 1)); Assertions.assertTrue(fun.equals(1.0, 1 + Math.ulp(1d), 1)); Assertions.assertFalse(fun.equals(1.0, 1 + 2 * Math.ulp(1d), 1)); @@ -152,6 +154,7 @@ class PrecisionTest { Assertions.assertFalse(fun.equals(value, Math.nextDown(Math.nextDown(value)), 1)); // This test is conditional if (!fixed1Ulp) { + Assertions.assertFalse(fun.equals(value, value, -1), "Negative ULP should be supported"); Assertions.assertFalse(fun.equals(value, Math.nextUp(value), 0)); Assertions.assertTrue(fun.equals(value, Math.nextUp(Math.nextUp(value)), 2)); Assertions.assertTrue(fun.equals(value, Math.nextDown(Math.nextDown(value)), 2)); @@ -171,7 +174,21 @@ class PrecisionTest { Assertions.assertFalse(fun.equals(Double.NaN, Double.POSITIVE_INFINITY, 0)); Assertions.assertFalse(fun.equals(Double.NaN, Double.NEGATIVE_INFINITY, 0)); - Assertions.assertFalse(fun.equals(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, 100000)); + if (!fixed1Ulp) { + Assertions.assertFalse(fun.equals(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, Integer.MAX_VALUE)); + Assertions.assertFalse(fun.equals(0, Double.MAX_VALUE, Integer.MAX_VALUE)); + // Here: f == 5.304989477E-315; + // it is used to test the maximum ULP distance between two opposite sign numbers. + final double f = Double.longBitsToDouble(1L << 30); + Assertions.assertFalse(fun.equals(-f, f, Integer.MAX_VALUE)); + Assertions.assertTrue(fun.equals(-f, Math.nextDown(f), Integer.MAX_VALUE)); + Assertions.assertTrue(fun.equals(Math.nextUp(-f), f, Integer.MAX_VALUE)); + // Maximum distance between same sign numbers. + final double f2 = Double.longBitsToDouble((1L << 30) + Integer.MAX_VALUE); + Assertions.assertTrue(fun.equals(f, f2, Integer.MAX_VALUE)); + Assertions.assertFalse(fun.equals(f, Math.nextUp(f2), Integer.MAX_VALUE)); + Assertions.assertFalse(fun.equals(Math.nextDown(f), f2, Integer.MAX_VALUE)); + } } // Tests for floating point equality match the above tests with arguments @@ -222,23 +239,25 @@ class PrecisionTest { @Test void testFloatEqualsWithAllowedUlps() { - assertFloatEqualsIncludingNaNWithAllowedUlps(Precision::equals, false, false); + assertFloatEqualsWithAllowedUlps(Precision::equals, false, false); } @Test void testFloatEqualsWithImplicitAllowedUlpsOf1() { // Use the version without the ulp argument - assertFloatEqualsIncludingNaNWithAllowedUlps((a, b, ulp) -> Precision.equals(a, b), false, true); + assertFloatEqualsWithAllowedUlps((a, b, ulp) -> Precision.equals(a, b), false, true); } @Test void testFloatEqualsIncludingNaNWithAllowedUlps() { - assertFloatEqualsIncludingNaNWithAllowedUlps(Precision::equalsIncludingNaN, true, false); + assertFloatEqualsWithAllowedUlps(Precision::equalsIncludingNaN, true, false); } - private static void assertFloatEqualsIncludingNaNWithAllowedUlps(FloatEqualsWithUlps fun, + private static void assertFloatEqualsWithAllowedUlps(FloatEqualsWithUlps fun, boolean nanAreEqual, boolean fixed1Ulp) { Assertions.assertTrue(fun.equals(0.0f, -0.0f, 1)); + Assertions.assertTrue(fun.equals(Float.MIN_VALUE, -0.0f, 1)); + Assertions.assertFalse(fun.equals(Float.MIN_VALUE, -Float.MIN_VALUE, 1)); Assertions.assertTrue(fun.equals(1.0f, 1f + Math.ulp(1f), 1)); Assertions.assertFalse(fun.equals(1.0f, 1f + 2 * Math.ulp(1f), 1)); @@ -251,6 +270,7 @@ class PrecisionTest { Assertions.assertFalse(fun.equals(value, Math.nextDown(Math.nextDown(value)), 1)); // This test is conditional if (!fixed1Ulp) { + Assertions.assertFalse(fun.equals(value, value, -1), "Negative ULP should be supported"); Assertions.assertFalse(fun.equals(value, Math.nextUp(value), 0)); Assertions.assertTrue(fun.equals(value, Math.nextUp(Math.nextUp(value)), 2)); Assertions.assertTrue(fun.equals(value, Math.nextDown(Math.nextDown(value)), 2)); @@ -270,7 +290,24 @@ class PrecisionTest { Assertions.assertFalse(fun.equals(Float.NaN, Float.POSITIVE_INFINITY, 0)); Assertions.assertFalse(fun.equals(Float.NaN, Float.NEGATIVE_INFINITY, 0)); - Assertions.assertFalse(fun.equals(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY, 100000)); + if (!fixed1Ulp) { + Assertions.assertFalse(fun.equals(Float.NEGATIVE_INFINITY, Float.POSITIVE_INFINITY, Integer.MAX_VALUE)); + // The 31-bit integer specification of the max positive ULP allows an extremely + // large range of a 23-bit mantissa and 8-bit exponent + Assertions.assertTrue(fun.equals(0, Float.MAX_VALUE, Integer.MAX_VALUE)); + // Here: f == 2; + // it is used to test the maximum ULP distance between two opposite sign numbers. + final float f = Float.intBitsToFloat(1 << 30); + Assertions.assertFalse(fun.equals(-f, f, Integer.MAX_VALUE)); + Assertions.assertTrue(fun.equals(-f, Math.nextDown(f), Integer.MAX_VALUE)); + Assertions.assertTrue(fun.equals(Math.nextUp(-f), f, Integer.MAX_VALUE)); + // Maximum distance between same sign finite numbers is not possible as the upper + // limit is NaN. Check that it is not equal to anything. + final float f2 = Float.intBitsToFloat(Integer.MAX_VALUE); + Assertions.assertEquals(Double.NaN, f2); + Assertions.assertFalse(fun.equals(f2, Float.MAX_VALUE, Integer.MAX_VALUE)); + Assertions.assertFalse(fun.equals(f2, 0, Integer.MAX_VALUE)); + } } @Test diff --git a/src/changes/changes.xml b/src/changes/changes.xml index 3a684d7..5b1b50e 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -72,6 +72,9 @@ N.B. the Performance testing module requires Java 9+. (The unit tests require Java 8+) "> + <action dev="aherbert" type="update" issue="NUMBERS-184"> + "Precision": Reduce number of operations in Precision.equals using a maxUlps. + </action> <action dev="aherbert" type="add" issue="NUMBERS-181"> Updated support for the beta functions. "RegularizedBeta": Added the complement and derivative of the regularized beta function.
