You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ps...@apache.org on 2009/12/31 00:03:24 UTC
svn commit: r894730 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math/MessagesResources_fr.java
main/java/org/apache/commons/math/util/MathUtils.java
test/java/org/apache/commons/math/util/MathUtilsTest.java
Author: psteitz
Date: Wed Dec 30 23:03:23 2009
New Revision: 894730
URL: http://svn.apache.org/viewvc?rev=894730&view=rev
Log:
Added gcd(long, long), lcm(long, long) methods. JIRA: MATH-239.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math/MessagesResources_fr.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/MessagesResources_fr.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/MessagesResources_fr.java?rev=894730&r1=894729&r2=894730&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/MessagesResources_fr.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/MessagesResources_fr.java Wed Dec 30 23:03:23 2009
@@ -40,6 +40,12 @@
"n doit \u00eatre positif pour le calcul de n!, or n = {0}" },
{ "overflow: gcd({0}, {1}) is 2^31",
"d\u00e9passement de capacit\u00e9 : le PGCD de {0} et {1} vaut 2^31" },
+ { "overflow: gcd({0}, {1}) is 2^63",
+ "d\u00e9passement de capacit\u00e9 : le PGCD de {0} et {1} vaut 2^63" },
+ { "overflow: lcm({0}, {1}) is 2^31",
+ "d\u00e9passement de capacit\u00e9 : le MCM de {0} et {1} vaut 2^31" },
+ { "overflow: lcm({0}, {1}) is 2^63",
+ "d\u00e9passement de capacit\u00e9 : le MCM de {0} et {1} vaut 2^63" },
{ "cannot raise an integral value to a negative power ({0}^{1})",
"impossible d''\u00e9lever une valeur enti\u00e8re " +
"\u00e0 une puissance n\u00e9gative ({0}^{1})" },
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java?rev=894730&r1=894729&r2=894730&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/util/MathUtils.java Wed Dec 30 23:03:23 2009
@@ -606,9 +606,8 @@
* @param p any number
* @param q any number
* @return the greatest common divisor, never negative
- * @throws ArithmeticException
- * if the result cannot be represented as a nonnegative int
- * value
+ * @throws ArithmeticException if the result cannot be represented as a
+ * nonnegative int value
* @since 1.1
*/
public static int gcd(final int p, final int q) {
@@ -672,6 +671,95 @@
}
/**
+ * <p>
+ * Gets the greatest common divisor of the absolute value of two numbers,
+ * using the "binary gcd" method which avoids division and modulo
+ * 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(Long.MIN_VALUE, Long.MIN_VALUE)</code>,
+ * <code>gcd(Long.MIN_VALUE, 0L)</code> and
+ * <code>gcd(0L, Long.MIN_VALUE)</code> throw an
+ * <code>ArithmeticException</code>, because the result would be 2^63, which
+ * is too large for a long value.</li>
+ * <li>The result of <code>gcd(x, x)</code>, <code>gcd(0L, x)</code> and
+ * <code>gcd(x, 0L)</code> is the absolute value of <code>x</code>, except
+ * for the special cases above.
+ * <li>The invocation <code>gcd(0L, 0L)</code> is the only one which returns
+ * <code>0L</code>.</li>
+ * </ul>
+ *
+ * @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 long
+ * value
+ * @since 2.1
+ */
+ public static long gcd(final long p, final long q) {
+ long u = p;
+ long v = q;
+ if ((u == 0) || (v == 0)) {
+ if ((u == Long.MIN_VALUE) || (v == Long.MIN_VALUE)){
+ throw MathRuntimeException.createArithmeticException(
+ "overflow: gcd({0}, {1}) is 2^63",
+ p, q);
+ }
+ return (Math.abs(u) + Math.abs(v));
+ }
+ // keep u and v negative, as negative integers range down to
+ // -2^63, while positive numbers can only be as large as 2^63-1
+ // (i.e. we can't necessarily negate a negative number without
+ // overflow)
+ /* assert u!=0 && v!=0; */
+ if (u > 0) {
+ u = -u;
+ } // make u negative
+ if (v > 0) {
+ v = -v;
+ } // make v negative
+ // B1. [Find power of 2]
+ int k = 0;
+ while ((u & 1) == 0 && (v & 1) == 0 && k < 63) { // while u and v are
+ // both even...
+ u /= 2;
+ v /= 2;
+ k++; // cast out twos.
+ }
+ if (k == 63) {
+ throw MathRuntimeException.createArithmeticException(
+ "overflow: gcd({0}, {1}) is 2^63",
+ p, q);
+ }
+ // B2. Initialize: u and v have been divided by 2^k and at least
+ // one is odd.
+ long t = ((u & 1) == 1) ? v : -(u / 2)/* B3 */;
+ // t negative: u was odd, v may be even (t replaces v)
+ // t positive: u was even, v is odd (t replaces u)
+ do {
+ /* assert u<0 && v<0; */
+ // B4/B3: cast out twos from t.
+ while ((t & 1) == 0) { // while t is even..
+ t /= 2; // cast out twos
+ }
+ // B5 [reset max(u,v)]
+ if (t > 0) {
+ u = -t;
+ } else {
+ v = t;
+ }
+ // B6/B3. at this point both u and v should be odd.
+ t = (v - u) / 2;
+ // |u| larger: t positive (replace u)
+ // |v| larger: t negative (replace v)
+ } while (t != 0);
+ return -u * (1L << k); // gcd is u*2^k
+ }
+
+ /**
* Returns an integer hash code representing the given double value.
*
* @param value the value to be hashed
@@ -791,8 +879,45 @@
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");
+ if (lcm == Integer.MIN_VALUE) {
+ throw MathRuntimeException.createArithmeticException(
+ "overflow: lcm({0}, {1}) is 2^31",
+ a, b);
+ }
+ return lcm;
+ }
+
+ /**
+ * <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(Long.MIN_VALUE, n)</code> and
+ * <code>lcm(n, Long.MIN_VALUE)</code>, where <code>abs(n)</code> is a
+ * power of 2, throw an <code>ArithmeticException</code>, because the result
+ * would be 2^63, which is too large for an int value.</li>
+ * <li>The result of <code>lcm(0L, x)</code> and <code>lcm(x, 0L)</code> is
+ * <code>0L</code> for any <code>x</code>.
+ * </ul>
+ *
+ * @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 long
+ * value
+ * @since 2.1
+ */
+ public static long lcm(long a, long b) {
+ if (a==0 || b==0){
+ return 0;
+ }
+ long lcm = Math.abs(mulAndCheck(a / gcd(a, b), b));
+ if (lcm == Long.MIN_VALUE){
+ throw MathRuntimeException.createArithmeticException(
+ "overflow: lcm({0}, {1}) is 2^63",
+ a, b);
}
return lcm;
}
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java?rev=894730&r1=894729&r2=894730&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/util/MathUtilsTest.java Wed Dec 30 23:03:23 2009
@@ -490,6 +490,81 @@
}
}
+ public void testGcdLong(){
+ long a = 30;
+ long b = 50;
+ long c = 77;
+
+ assertEquals(0, MathUtils.gcd(0L, 0));
+
+ assertEquals(b, MathUtils.gcd(0, b));
+ assertEquals(a, MathUtils.gcd(a, 0));
+ assertEquals(b, MathUtils.gcd(0, -b));
+ assertEquals(a, MathUtils.gcd(-a, 0));
+
+ assertEquals(10, MathUtils.gcd(a, b));
+ assertEquals(10, MathUtils.gcd(-a, b));
+ assertEquals(10, MathUtils.gcd(a, -b));
+ assertEquals(10, MathUtils.gcd(-a, -b));
+
+ assertEquals(1, MathUtils.gcd(a, c));
+ assertEquals(1, MathUtils.gcd(-a, c));
+ assertEquals(1, MathUtils.gcd(a, -c));
+ assertEquals(1, MathUtils.gcd(-a, -c));
+
+ assertEquals(3L * (1L<<45), MathUtils.gcd(3L * (1L<<50), 9L * (1L<<45)));
+
+ assertEquals(1L<<45, MathUtils.gcd(1L<<45, Long.MIN_VALUE));
+
+ assertEquals(Long.MAX_VALUE, MathUtils.gcd(Long.MAX_VALUE, 0L));
+ assertEquals(Long.MAX_VALUE, MathUtils.gcd(-Long.MAX_VALUE, 0L));
+ assertEquals(1, MathUtils.gcd(60247241209L, 153092023L));
+ try {
+ // gcd(Long.MIN_VALUE, 0) > Long.MAX_VALUE
+ MathUtils.gcd(Long.MIN_VALUE, 0);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException expected) {
+ // expected
+ }
+ try {
+ // gcd(0, Long.MIN_VALUE) > Long.MAX_VALUE
+ MathUtils.gcd(0, Long.MIN_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException expected) {
+ // expected
+ }
+ try {
+ // gcd(Long.MIN_VALUE, Long.MIN_VALUE) > Long.MAX_VALUE
+ MathUtils.gcd(Long.MIN_VALUE, Long.MIN_VALUE);
+ fail("expecting ArithmeticException");
+ } catch (ArithmeticException expected) {
+ // expected
+ }
+ }
+
+ public void testGcdConsistency() {
+ int[] primeList = {19, 23, 53, 67, 73, 79, 101, 103, 111, 131};
+ ArrayList<Integer> primes = new ArrayList<Integer>();
+ for (int i = 0; i < primeList.length; i++) {
+ primes.add(Integer.valueOf(primeList[i]));
+ }
+ RandomDataImpl randomData = new RandomDataImpl();
+ for (int i = 0; i < 20; i++) {
+ Object[] sample = randomData.nextSample(primes, 4);
+ int p1 = ((Integer) sample[0]).intValue();
+ int p2 = ((Integer) sample[1]).intValue();
+ int p3 = ((Integer) sample[2]).intValue();
+ int p4 = ((Integer) sample[3]).intValue();
+ int i1 = p1 * p2 * p3;
+ int i2 = p1 * p2 * p4;
+ int gcd = p1 * p2;
+ assertEquals(gcd, MathUtils.gcd(i1, i2));
+ long l1 = i1;
+ long l2 = i2;
+ assertEquals(gcd, MathUtils.gcd(l1, l2));
+ }
+ }
+
public void testHash() {
double[] testArray = {
Double.NaN,
@@ -624,7 +699,7 @@
// lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
MathUtils.lcm(Integer.MIN_VALUE, 1);
fail("Expecting ArithmeticException");
- } catch (ArithmeticException ex) {
+ } catch (ArithmeticException expected) {
// expected
}
@@ -632,14 +707,64 @@
// lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
MathUtils.lcm(Integer.MIN_VALUE, 1<<20);
fail("Expecting ArithmeticException");
- } catch (ArithmeticException ex) {
+ } catch (ArithmeticException expected) {
// expected
}
try {
MathUtils.lcm(Integer.MAX_VALUE, Integer.MAX_VALUE - 1);
fail("Expecting ArithmeticException");
- } catch (ArithmeticException ex) {
+ } catch (ArithmeticException expected) {
+ // expected
+ }
+ }
+
+ public void testLcmLong() {
+ long a = 30;
+ long b = 50;
+ long c = 77;
+
+ assertEquals(0, MathUtils.lcm(0, b));
+ assertEquals(0, MathUtils.lcm(a, 0));
+ assertEquals(b, MathUtils.lcm(1, b));
+ assertEquals(a, MathUtils.lcm(a, 1));
+ 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));
+
+ assertEquals(Long.MAX_VALUE, MathUtils.lcm(60247241209L, 153092023L));
+
+ // Assert that no intermediate value overflows:
+ // The naive implementation of lcm(a,b) would be (a*b)/gcd(a,b)
+ assertEquals((1L<<50)*15, MathUtils.lcm((1L<<45)*3, (1L<<50)*5));
+
+ // Special case
+ assertEquals(0L, MathUtils.lcm(0L, 0L));
+
+ try {
+ // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
+ MathUtils.lcm(Long.MIN_VALUE, 1);
+ fail("Expecting ArithmeticException");
+ } catch (ArithmeticException expected) {
+ // expected
+ }
+
+ try {
+ // lcm == abs(MIN_VALUE) cannot be represented as a nonnegative int
+ MathUtils.lcm(Long.MIN_VALUE, 1<<20);
+ fail("Expecting ArithmeticException");
+ } catch (ArithmeticException expected) {
+ // expected
+ }
+
+ assertEquals((long) Integer.MAX_VALUE * (Integer.MAX_VALUE - 1),
+ MathUtils.lcm((long)Integer.MAX_VALUE, Integer.MAX_VALUE - 1));
+ try {
+ MathUtils.lcm(Long.MAX_VALUE, Long.MAX_VALUE - 1);
+ fail("Expecting ArithmeticException");
+ } catch (ArithmeticException expected) {
// expected
}
}