You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by lu...@apache.org on 2009/02/21 14:54:25 UTC
svn commit: r746511 - in /commons/proper/math/trunk: pom.xml
src/java/org/apache/commons/math/MessagesResources_fr.java
src/java/org/apache/commons/math/util/MathUtils.java
src/site/xdoc/changes.xml
src/test/org/apache/commons/math/util/MathUtilsTest.java
Author: luc
Date: Sat Feb 21 13:54:25 2009
New Revision: 746511
URL: http://svn.apache.org/viewvc?rev=746511&view=rev
Log:
Fixed an error in computing gcd and lcm for some extreme values at integer range boundaries.
JIRA: MATH-243
Modified:
commons/proper/math/trunk/pom.xml
commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java
commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java
commons/proper/math/trunk/src/site/xdoc/changes.xml
commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java
Modified: commons/proper/math/trunk/pom.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/pom.xml?rev=746511&r1=746510&r2=746511&view=diff
==============================================================================
--- commons/proper/math/trunk/pom.xml (original)
+++ commons/proper/math/trunk/pom.xml Sat Feb 21 13:54:25 2009
@@ -166,6 +166,9 @@
<name>Christopher Schuck</name>
</contributor>
<contributor>
+ <name>Christian Semrau</name>
+ </contributor>
+ <contributor>
<name>Mauro Talevi</name>
</contributor>
<contributor>
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java?rev=746511&r1=746510&r2=746511&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/MessagesResources_fr.java Sat Feb 21 13:54:25 2009
@@ -44,6 +44,10 @@
/** Non-translated/translated messages arrays. */
static final Object[][] contents = {
+ // org.apache.commons.math.util.MathUtils
+ { "overflow: gcd({0}, {1}) is 2^31",
+ "d\u00e9passement de capacit\u00e9 : le PGCD de {0} et {1} vaut 2^31" },
+
// org.apache.commons.math.FunctionEvaluationException
{ "Evaluation failed for argument = {0}",
"Erreur d''\u00e9valuation pour l''argument {0}" },
Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java?rev=746511&r1=746510&r2=746511&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java Sat Feb 21 13:54:25 2009
@@ -20,6 +20,9 @@
import java.math.BigDecimal;
import java.util.Arrays;
+import org.apache.commons.math.MathException;
+import org.apache.commons.math.MathRuntimeException;
+
/**
* Some useful additions to the built-in functions in {@link Math}.
* @version $Revision$ $Date$
@@ -510,14 +513,38 @@
* operations. See Knuth 4.5.2 algorithm B. This algorithm is due to Josef
* Stein (1961).
* </p>
+ * Special cases:
+ * <ul>
+ * <li>The invocations
+ * <code>gcd(Integer.MIN_VALUE, Integer.MIN_VALUE)</code>,
+ * <code>gcd(Integer.MIN_VALUE, 0)</code> and
+ * <code>gcd(0, Integer.MIN_VALUE)</code> throw an
+ * <code>ArithmeticException</code>, because the result would be 2^31, which
+ * is too large for an int value.</li>
+ * <li>The result of <code>gcd(x, x)</code>, <code>gcd(0, x)</code> and
+ * <code>gcd(x, 0)</code> is the absolute value of <code>x</code>, except
+ * for the special cases above.
+ * <li>The invocation <code>gcd(0, 0)</code> is the only one which returns
+ * <code>0</code>.</li>
+ * </ul>
*
- * @param u a non-zero number
- * @param v a non-zero number
- * @return the greatest common divisor, never zero
+ * @param u any number
+ * @param v any number
+ * @return the greatest common divisor, never negative
+ * @throws ArithmeticException
+ * if the result cannot be represented as a nonnegative int
+ * value
* @since 1.1
*/
- public static int gcd(int u, int v) {
+ public static int gcd(final int p, final int q) {
+ int u = p;
+ int v = q;
if ((u == 0) || (v == 0)) {
+ if ((u == Integer.MIN_VALUE) || (v == Integer.MIN_VALUE)) {
+ throw MathRuntimeException.createArithmeticException(
+ "overflow: gcd({0}, {1}) is 2^31",
+ new Object[] { p, q });
+ }
return (Math.abs(u) + Math.abs(v));
}
// keep u and v negative, as negative integers range down to
@@ -540,7 +567,9 @@
k++; // cast out twos.
}
if (k == 31) {
- throw new ArithmeticException("overflow: gcd is 2^31");
+ throw MathRuntimeException.createArithmeticException(
+ "overflow: gcd({0}, {1}) is 2^31",
+ new Object[] { p, q });
}
// B2. Initialize: u and v have been divided by 2^k and at least
// one is odd.
@@ -660,16 +689,37 @@
}
/**
- * Returns the least common multiple between two integer values.
+ * <p>
+ * Returns the least common multiple of the absolute value of two numbers,
+ * using the formula <code>lcm(a,b) = (a / gcd(a,b)) * b</code>.
+ * </p>
+ * Special cases:
+ * <ul>
+ * <li>The invocations <code>lcm(Integer.MIN_VALUE, n)</code> and
+ * <code>lcm(n, Integer.MIN_VALUE)</code>, where <code>abs(n)</code> is a
+ * power of 2, throw an <code>ArithmeticException</code>, because the result
+ * would be 2^31, which is too large for an int value.</li>
+ * <li>The result of <code>lcm(0, x)</code> and <code>lcm(x, 0)</code> is
+ * <code>0</code> for any <code>x</code>.
+ * </ul>
*
- * @param a the first integer value.
- * @param b the second integer value.
- * @return the least common multiple between a and b.
- * @throws ArithmeticException if the lcm is too large to store as an int
+ * @param a any number
+ * @param b any number
+ * @return the least common multiple, never negative
+ * @throws ArithmeticException
+ * if the result cannot be represented as a nonnegative int
+ * value
* @since 1.1
*/
public static int lcm(int a, int b) {
- return Math.abs(mulAndCheck(a / gcd(a, b), b));
+ if (a==0 || b==0){
+ return 0;
+ }
+ int lcm = Math.abs(mulAndCheck(a / gcd(a, b), b));
+ if (lcm == Integer.MIN_VALUE){
+ throw new ArithmeticException("overflow: lcm is 2^31");
+ }
+ return lcm;
}
/**
Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=746511&r1=746510&r2=746511&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Sat Feb 21 13:54:25 2009
@@ -39,6 +39,10 @@
</properties>
<body>
<release version="2.0" date="TBD" description="TBD">
+ <action dev="luc" type="fix" issue="MATH-243" due-to="Christian Semrau">
+ Fixed an error in computing gcd and lcm for some extreme values at integer
+ range boundaries.
+ </action>
<action dev="luc" type="add" issue="MATH-247" due-to="Benjamin McCann">
Added a MathUtils method to check equality given some error bounds.
</action>
Modified: commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java?rev=746511&r1=746510&r2=746511&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java (original)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java Sat Feb 21 13:54:25 2009
@@ -429,12 +429,28 @@
assertEquals(3 * (1<<15), MathUtils.gcd(3 * (1<<20), 9 * (1<<15)));
assertEquals(Integer.MAX_VALUE, MathUtils.gcd(Integer.MAX_VALUE, 0));
- // abs(Integer.MIN_VALUE) == Integer.MIN_VALUE
- assertEquals(Integer.MIN_VALUE, MathUtils.gcd(Integer.MIN_VALUE, 0));
+ assertEquals(Integer.MAX_VALUE, MathUtils.gcd(-Integer.MAX_VALUE, 0));
+ assertEquals(1<<30, MathUtils.gcd(1<<30, -Integer.MIN_VALUE));
try {
+ // gcd(Integer.MIN_VALUE, 0) > Integer.MAX_VALUE
+ MathUtils.gcd(Integer.MIN_VALUE, 0);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException expected) {
+ // expected
+ }
+ try {
+ // gcd(0, Integer.MIN_VALUE) > Integer.MAX_VALUE
+ MathUtils.gcd(0, Integer.MIN_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException expected) {
+ // expected
+ }
+ try {
+ // gcd(Integer.MIN_VALUE, Integer.MIN_VALUE) > Integer.MAX_VALUE
MathUtils.gcd(Integer.MIN_VALUE, Integer.MIN_VALUE);
+ fail("expecting ArithmeticException");
} catch (ArithmeticException expected) {
- //
+ // expected
}
}
@@ -558,8 +574,32 @@
assertEquals(150, MathUtils.lcm(a, b));
assertEquals(150, MathUtils.lcm(-a, b));
assertEquals(150, MathUtils.lcm(a, -b));
+ assertEquals(150, MathUtils.lcm(-a, -b));
assertEquals(2310, MathUtils.lcm(a, c));
+ // Assert that no intermediate value overflows:
+ // The naive implementation of lcm(a,b) would be (a*b)/gcd(a,b)
+ assertEquals((1<<20)*15, MathUtils.lcm((1<<20)*3, (1<<20)*5));
+
+ // Special case
+ assertEquals(0, MathUtils.lcm(0, 0));
+
+ try {
+ // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
+ MathUtils.lcm(Integer.MIN_VALUE, 1);
+ fail("Expecting ArithmeticException");
+ } catch (ArithmeticException ex) {
+ // expected
+ }
+
+ try {
+ // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
+ MathUtils.lcm(Integer.MIN_VALUE, 1<<20);
+ fail("Expecting ArithmeticException");
+ } catch (ArithmeticException ex) {
+ // expected
+ }
+
try {
MathUtils.lcm(Integer.MAX_VALUE, Integer.MAX_VALUE - 1);
fail("Expecting ArithmeticException");