fixed overflow error in gdc computation

Luc Maisonobe · Luc Maisonobe · commit dabf3a5beb9a · 2009-01-16T23:06:32.000Z
JIRA: MATH-238 git-svn-id: https://svn.apache.org/repos/asf/commons/proper/math/trunk@735178 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/src/java/org/apache/commons/math/util/MathUtils.java b/src/java/org/apache/commons/math/util/MathUtils.java
@@ -409,7 +409,7 @@ public static double factorialLog(final int n) {
      * @since 1.1
      */
     public static int gcd(int u, int v) {
-        if (u * v == 0) {
+        if ((u == 0) || (v == 0)) {
             return (Math.abs(u) + Math.abs(v));
         }
         // keep u and v negative, as negative integers range down to
diff --git a/src/site/xdoc/changes.xml b/src/site/xdoc/changes.xml
@@ -39,6 +39,9 @@ The <action> type attribute can be add,update,fix,remove.
   </properties>
   <body>
     <release version="2.0" date="TBD" description="TBD">
+      <action dev="luc" type="fix" issue="MATH-238" due-to="Chritian Semrau">
+        Fixed an error in gcd computation for large values.
+      </action>
       <action dev="luc" type="add" >
         Added method to walk matrix entries with or without changing them in the
         visitor design pattern sense. Three different orders can be used, row by row,
diff --git a/src/test/org/apache/commons/math/util/MathUtilsTest.java b/src/test/org/apache/commons/math/util/MathUtilsTest.java
@@ -291,6 +291,9 @@ public void testGcd() {
         assertEquals(1, MathUtils.gcd(-a, c));
         assertEquals(1, MathUtils.gcd(a, -c));
         assertEquals(1, MathUtils.gcd(-a, -c));
+
+        assertEquals(3 * (1<<15), MathUtils.gcd(3 * (1<<20), 9 * (1<<15)));
+
     }
 
     public void testHash() {

Original file line number	Diff line number	Diff line change
`@@ -409,7 +409,7 @@ public static double factorialLog(final int n) {`
`409`	`409`	`* @since 1.1`
`410`	`410`	`*/`
`411`	`411`	`public static int gcd(int u, int v) {`
`412`		`- if (u * v == 0) {`
	`412`	`+ if ((u == 0) \|\| (v == 0)) {`
`413`	`413`	`return (Math.abs(u) + Math.abs(v));`
`414`	`414`	`}`
`415`	`415`	`// keep u and v negative, as negative integers range down to`
Original file line number	Diff line number	Diff line change
`@@ -291,6 +291,9 @@ public void testGcd() {`
`291`	`291`	`assertEquals(1, MathUtils.gcd(-a, c));`
`292`	`292`	`assertEquals(1, MathUtils.gcd(a, -c));`
`293`	`293`	`assertEquals(1, MathUtils.gcd(-a, -c));`
	`294`	`+`
	`295`	`+ assertEquals(3 * (1<<15), MathUtils.gcd(3 * (1<<20), 9 * (1<<15)));`
	`296`	`+`
`294`	`297`	`}`
`295`	`298`
`296`	`299`	`public void testHash() {`