commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pste...@apache.org
Subject 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
Date Wed, 30 Dec 2009 23:03:24 GMT
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
         }
     }



Mime
View raw message