Repository: commons-math Updated Branches: refs/heads/master 85d2568de -> 8c141a170
Added divideUnsigned and remainderUnsigned to ArithmeticUtils. JIRA: MATH-1271 Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/8c141a17 Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/8c141a17 Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/8c141a17 Branch: refs/heads/master Commit: 8c141a1705808491f16a27b53e1ff0db0a2807fd Parents: 85d2568 Author: Qualtagh <a@a.a> Authored: Fri Sep 11 18:16:35 2015 +0200 Committer: Luc Maisonobe <l...@apache.org> Committed: Fri Sep 11 18:16:35 2015 +0200 ---------------------------------------------------------------------- pom.xml | 3 + src/changes/changes.xml | 3 + .../commons/math4/util/ArithmeticUtils.java | 135 +++++++++++++ .../commons/math4/util/ArithmeticUtilsTest.java | 199 +++++++++++++++++++ 4 files changed, 340 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-math/blob/8c141a17/pom.xml ---------------------------------------------------------------------- diff --git a/pom.xml b/pom.xml index d00741b..81ec75f 100644 --- a/pom.xml +++ b/pom.xml @@ -293,6 +293,9 @@ <name>Todd C. Parnell</name> </contributor> <contributor> + <name>Qualtagh</name> + </contributor> + <contributor> <name>Andreas Rieger</name> </contributor> <contributor> http://git-wip-us.apache.org/repos/asf/commons-math/blob/8c141a17/src/changes/changes.xml ---------------------------------------------------------------------- diff --git a/src/changes/changes.xml b/src/changes/changes.xml index 47f34d0..a8a09fa 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -54,6 +54,9 @@ If the output is not quite correct, check for invisible trailing spaces! </release> <release version="4.0" date="XXXX-XX-XX" description=""> + <action dev="luc" type="add" issue="MATH-1271" due-to="Qualtagh"> + Added divideUnsigned and remainderUnsigned to ArithmeticUtils. + </action> <action dev="luc" type="fix" issue="MATH-1272" due-to="Qualtagh"> <!-- backported to 3.6 --> Fixed infinite loop in FastMath.pow(double, long) with Long.MIN_VALUE. </action> http://git-wip-us.apache.org/repos/asf/commons-math/blob/8c141a17/src/main/java/org/apache/commons/math4/util/ArithmeticUtils.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math4/util/ArithmeticUtils.java b/src/main/java/org/apache/commons/math4/util/ArithmeticUtils.java index ab799ed..0f154dc 100644 --- a/src/main/java/org/apache/commons/math4/util/ArithmeticUtils.java +++ b/src/main/java/org/apache/commons/math4/util/ArithmeticUtils.java @@ -665,4 +665,139 @@ public final class ArithmeticUtils { public static boolean isPowerOfTwo(long n) { return (n > 0) && ((n & (n - 1)) == 0); } + + /** + * Returns the unsigned remainder from dividing the first argument + * by the second where each argument and the result is interpreted + * as an unsigned value. + * <p>This method doesn't use long datatype unlike it's used in + * {@link java.lang.Integer#remainderUnsigned}. + * + * @param dividend the value to be divided + * @param divisor the value doing the dividing + * @return the unsigned remainder of the first argument divided by + * the second argument + * @see java.lang.Integer#remainderUnsigned + * @since 4.0 + */ + public static int remainderUnsigned(int dividend, int divisor) { + if (divisor >= 0) { + if (dividend >= 0) { + return dividend % divisor; + } + // The implementation is a Java port of algorithm described in the book + // "Hacker's Delight" (section "Unsigned short division from signed division"). + int q = ((dividend >>> 1) / divisor) << 1; + dividend -= q * divisor; + if (dividend < 0 || dividend >= divisor) { + dividend -= divisor; + } + return dividend; + } + return dividend >= 0 || dividend < divisor ? dividend : dividend - divisor; + } + + /** + * Returns the unsigned remainder from dividing the first argument + * by the second where each argument and the result is interpreted + * as an unsigned value. + * <p>This method doesn't use BigInteger datatype unlike it's used in + * {@link java.lang.Long#remainderUnsigned}. + * + * @param dividend the value to be divided + * @param divisor the value doing the dividing + * @return the unsigned remainder of the first argument divided by + * the second argument + * @see java.lang.Long#remainderUnsigned + * @since 4.0 + */ + public static long remainderUnsigned(long dividend, long divisor) { + if (divisor >= 0L) { + if (dividend >= 0L) { + return dividend % divisor; + } + // The implementation is a Java port of algorithm described in the book + // "Hacker's Delight" (section "Unsigned short division from signed division"). + long q = ((dividend >>> 1) / divisor) << 1; + dividend -= q * divisor; + if (dividend < 0L || dividend >= divisor) { + dividend -= divisor; + } + return dividend; + } + return dividend >= 0L || dividend < divisor ? dividend : dividend - divisor; + } + + /** + * Returns the unsigned quotient of dividing the first argument by + * the second where each argument and the result is interpreted as + * an unsigned value. + * <p>Note that in two's complement arithmetic, the three other + * basic arithmetic operations of add, subtract, and multiply are + * bit-wise identical if the two operands are regarded as both + * being signed or both being unsigned. Therefore separate {@code + * addUnsigned}, etc. methods are not provided. + * <p>This method doesn't use long datatype unlike it's used in + * {@link java.lang.Integer#divideUnsigned}. + * + * @param dividend the value to be divided + * @param divisor the value doing the dividing + * @return the unsigned quotient of the first argument divided by + * the second argument + * @see java.lang.Integer#divideUnsigned + * @since 4.0 + */ + public static int divideUnsigned(int dividend, int divisor) { + if (divisor >= 0) { + if (dividend >= 0) { + return dividend / divisor; + } + // The implementation is a Java port of algorithm described in the book + // "Hacker's Delight" (section "Unsigned short division from signed division"). + int q = ((dividend >>> 1) / divisor) << 1; + dividend -= q * divisor; + if (dividend < 0L || dividend >= divisor) { + q++; + } + return q; + } + return dividend >= 0 || dividend < divisor ? 0 : 1; + } + + /** + * Returns the unsigned quotient of dividing the first argument by + * the second where each argument and the result is interpreted as + * an unsigned value. + * <p>Note that in two's complement arithmetic, the three other + * basic arithmetic operations of add, subtract, and multiply are + * bit-wise identical if the two operands are regarded as both + * being signed or both being unsigned. Therefore separate {@code + * addUnsigned}, etc. methods are not provided. + * <p>This method doesn't use BigInteger datatype unlike it's used in + * {@link java.lang.Long#divideUnsigned}. + * + * @param dividend the value to be divided + * @param divisor the value doing the dividing + * @return the unsigned quotient of the first argument divided by + * the second argument + * @see java.lang.Long#divideUnsigned + * @since 4.0 + */ + public static long divideUnsigned(long dividend, long divisor) { + if (divisor >= 0L) { + if (dividend >= 0L) { + return dividend / divisor; + } + // The implementation is a Java port of algorithm described in the book + // "Hacker's Delight" (section "Unsigned short division from signed division"). + long q = ((dividend >>> 1) / divisor) << 1; + dividend -= q * divisor; + if (dividend < 0L || dividend >= divisor) { + q++; + } + return q; + } + return dividend >= 0L || dividend < divisor ? 0L : 1L; + } + } http://git-wip-us.apache.org/repos/asf/commons-math/blob/8c141a17/src/test/java/org/apache/commons/math4/util/ArithmeticUtilsTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/math4/util/ArithmeticUtilsTest.java b/src/test/java/org/apache/commons/math4/util/ArithmeticUtilsTest.java index 525dbff..336126a 100644 --- a/src/test/java/org/apache/commons/math4/util/ArithmeticUtilsTest.java +++ b/src/test/java/org/apache/commons/math4/util/ArithmeticUtilsTest.java @@ -587,4 +587,203 @@ public class ArithmeticUtilsTest { // success } } + + /** + * Testing helper method. + * @return an array of int numbers containing corner cases:<ul> + * <li>values near the beginning of int range,</li> + * <li>values near the end of int range,</li> + * <li>values near zero</li> + * <li>and some randomly distributed values.</li> + * </ul> + */ + private static int[] getIntSpecialCases() { + int ints[] = new int[100]; + int i = 0; + ints[i++] = Integer.MAX_VALUE; + ints[i++] = Integer.MAX_VALUE - 1; + ints[i++] = 100; + ints[i++] = 101; + ints[i++] = 102; + ints[i++] = 300; + ints[i++] = 567; + for (int j = 0; j < 20; j++) { + ints[i++] = j; + } + for (int j = i - 1; j >= 0; j--) { + ints[i++] = ints[j] > 0 ? -ints[j] : Integer.MIN_VALUE; + } + java.util.Random r = new java.util.Random(System.nanoTime()); + for (; i < ints.length;) { + ints[i++] = r.nextInt(); + } + return ints; + } + + /** + * Testing helper method. + * @return an array of long numbers containing corner cases:<ul> + * <li>values near the beginning of long range,</li> + * <li>values near the end of long range,</li> + * <li>values near the beginning of int range,</li> + * <li>values near the end of int range,</li> + * <li>values near zero</li> + * <li>and some randomly distributed values.</li> + * </ul> + */ + private static long[] getLongSpecialCases() { + long longs[] = new long[100]; + int i = 0; + longs[i++] = Long.MAX_VALUE; + longs[i++] = Long.MAX_VALUE - 1L; + longs[i++] = (long) Integer.MAX_VALUE + 1L; + longs[i++] = Integer.MAX_VALUE; + longs[i++] = Integer.MAX_VALUE - 1; + longs[i++] = 100L; + longs[i++] = 101L; + longs[i++] = 102L; + longs[i++] = 300L; + longs[i++] = 567L; + for (int j = 0; j < 20; j++) { + longs[i++] = j; + } + for (int j = i - 1; j >= 0; j--) { + longs[i++] = longs[j] > 0L ? -longs[j] : Long.MIN_VALUE; + } + java.util.Random r = new java.util.Random(System.nanoTime()); + for (; i < longs.length;) { + longs[i++] = r.nextLong(); + } + return longs; + } + + private static long toUnsignedLong(int number) { + return number < 0 ? 0x100000000L + (long)number : (long)number; + } + + private static int remainderUnsignedExpected(int dividend, int divisor) { + return (int)remainderUnsignedExpected(toUnsignedLong(dividend), toUnsignedLong(divisor)); + } + + private static int divideUnsignedExpected(int dividend, int divisor) { + return (int)divideUnsignedExpected(toUnsignedLong(dividend), toUnsignedLong(divisor)); + } + + private static BigInteger toUnsignedBigInteger(long number) { + return number < 0L ? BigInteger.ONE.shiftLeft(64).add(BigInteger.valueOf(number)) : BigInteger.valueOf(number); + } + + private static long remainderUnsignedExpected(long dividend, long divisor) { + return toUnsignedBigInteger(dividend).remainder(toUnsignedBigInteger(divisor)).longValue(); + } + + private static long divideUnsignedExpected(long dividend, long divisor) { + return toUnsignedBigInteger(dividend).divide(toUnsignedBigInteger(divisor)).longValue(); + } + + @Test(timeout=5000L) + public void testRemainderUnsignedInt() { + Assert.assertEquals(36, ArithmeticUtils.remainderUnsigned(-2147479015, 63)); + Assert.assertEquals(6, ArithmeticUtils.remainderUnsigned(-2147479015, 25)); + } + + @Test(timeout=5000L) + public void testRemainderUnsignedIntSpecialCases() { + int ints[] = getIntSpecialCases(); + for (int dividend : ints) { + for (int divisor : ints) { + if (divisor == 0) { + try { + ArithmeticUtils.remainderUnsigned(dividend, divisor); + Assert.fail("Should have failed with ArithmeticException: division by zero"); + } catch (ArithmeticException e) { + // Success. + } + } else { + Assert.assertEquals(remainderUnsignedExpected(dividend, divisor), ArithmeticUtils.remainderUnsigned(dividend, divisor)); + } + } + } + } + + @Test(timeout=5000L) + public void testRemainderUnsignedLong() { + Assert.assertEquals(48L, ArithmeticUtils.remainderUnsigned(-2147479015L, 63L)); + } + + @Test//(timeout=5000L) + public void testRemainderUnsignedLongSpecialCases() { + long longs[] = getLongSpecialCases(); + for (long dividend : longs) { + for (long divisor : longs) { + if (divisor == 0L) { + try { + ArithmeticUtils.remainderUnsigned(dividend, divisor); + Assert.fail("Should have failed with ArithmeticException: division by zero"); + } catch (ArithmeticException e) { + // Success. + } + } else { + Assert.assertEquals(remainderUnsignedExpected(dividend, divisor), ArithmeticUtils.remainderUnsigned(dividend, divisor)); + } + } + } + } + + @Test(timeout=5000L) + public void testDivideUnsignedInt() { + Assert.assertEquals(34087115, ArithmeticUtils.divideUnsigned(-2147479015, 63)); + Assert.assertEquals(85899531, ArithmeticUtils.divideUnsigned(-2147479015, 25)); + Assert.assertEquals(2147483646, ArithmeticUtils.divideUnsigned(-3, 2)); + Assert.assertEquals(330382098, ArithmeticUtils.divideUnsigned(-16, 13)); + Assert.assertEquals(306783377, ArithmeticUtils.divideUnsigned(-16, 14)); + Assert.assertEquals(2, ArithmeticUtils.divideUnsigned(-1, 2147483647)); + Assert.assertEquals(2, ArithmeticUtils.divideUnsigned(-2, 2147483647)); + Assert.assertEquals(1, ArithmeticUtils.divideUnsigned(-3, 2147483647)); + Assert.assertEquals(1, ArithmeticUtils.divideUnsigned(-16, 2147483647)); + Assert.assertEquals(1, ArithmeticUtils.divideUnsigned(-16, 2147483646)); + } + + @Test(timeout=5000L) + public void testDivideUnsignedIntSpecialCases() { + int ints[] = getIntSpecialCases(); + for (int dividend : ints) { + for (int divisor : ints) { + if (divisor == 0) { + try { + ArithmeticUtils.divideUnsigned(dividend, divisor); + Assert.fail("Should have failed with ArithmeticException: division by zero"); + } catch (ArithmeticException e) { + // Success. + } + } else { + Assert.assertEquals(divideUnsignedExpected(dividend, divisor), ArithmeticUtils.divideUnsigned(dividend, divisor)); + } + } + } + } + + @Test(timeout=5000L) + public void testDivideUnsignedLong() { + Assert.assertEquals(292805461453366231L, ArithmeticUtils.divideUnsigned(-2147479015L, 63L)); + } + + @Test(timeout=5000L) + public void testDivideUnsignedLongSpecialCases() { + long longs[] = getLongSpecialCases(); + for (long dividend : longs) { + for (long divisor : longs) { + if (divisor == 0L) { + try { + ArithmeticUtils.divideUnsigned(dividend, divisor); + Assert.fail("Should have failed with ArithmeticException: division by zero"); + } catch (ArithmeticException e) { + // Success. + } + } else { + Assert.assertEquals(divideUnsignedExpected(dividend, divisor), ArithmeticUtils.divideUnsigned(dividend, divisor)); + } + } + } + } }
