commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pste...@apache.org
Subject svn commit: r168072 - in /jakarta/commons/proper/math/trunk: src/java/org/apache/commons/math/fraction/Fraction.java src/java/org/apache/commons/math/util/MathUtils.java src/test/org/apache/commons/math/fraction/FractionTest.java src/test/org/apache/commons/math/util/MathUtilsTest.java xdocs/changes.xml
Date Wed, 04 May 2005 05:15:00 GMT
Author: psteitz
Date: Tue May  3 22:14:59 2005
New Revision: 168072

URL: http://svn.apache.org/viewcvs?rev=168072&view=rev
Log:
Ported numerics improvements in commons lang Fraction implementation.
Added utility methods for overflow-checked integer arithmetic and
improved gcd method in MathUtils.

Modified:
    jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/fraction/Fraction.java
    jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java
    jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/fraction/FractionTest.java
    jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java
    jakarta/commons/proper/math/trunk/xdocs/changes.xml

Modified: jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/fraction/Fraction.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/fraction/Fraction.java?rev=168072&r1=168071&r2=168072&view=diff
==============================================================================
--- jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/fraction/Fraction.java
(original)
+++ jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/fraction/Fraction.java
Tue May  3 22:14:59 2005
@@ -15,6 +15,7 @@
  */
 package org.apache.commons.math.fraction;
 
+import java.math.BigInteger;
 import org.apache.commons.math.ConvergenceException;
 import org.apache.commons.math.util.MathUtils;
 
@@ -118,9 +119,21 @@
      * reduced to lowest terms.
      * @param num the numerator.
      * @param den the denominator.
+     * @throws ArithmeticException if the denomiator is <code>zero</code>
      */
     public Fraction(int num, int den) {
         super();
+        if (den == 0) {
+            throw new ArithmeticException("The denominator must not be zero");
+        }
+        if (den < 0) {
+            if (num == Integer.MIN_VALUE ||
+                    den == Integer.MIN_VALUE) {
+                throw new ArithmeticException("overflow: can't negate");
+            }
+            num = -num;
+            den = -den;
+        }
         this.numerator = num;
         this.denominator = den;
         reduce();
@@ -141,20 +154,6 @@
     }
     
     /**
-     * Return the sum of this fraction and the given fraction.  The returned
-     * fraction is reduced to lowest terms.
-     *
-     * @param rhs the other fraction.
-     * @return the fraction sum in lowest terms.
-     */
-    public Fraction add(Fraction rhs) {
-        int den = MathUtils.lcm(denominator, rhs.denominator);
-        int num = (numerator * (den / denominator)) +
-            (rhs.numerator * (den / rhs.denominator));
-        return new Fraction(num, den);
-    }
-    
-    /**
      * Compares this object to another based on size.
      * @param object the object to compare to
      * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
@@ -177,16 +176,6 @@
         
         return ret;
     }
-
-    /**
-     * Return the quotient of this fraction and the given fraction.  The
-     * returned fraction is reduced to lowest terms.
-     * @param rhs the other fraction.
-     * @return the fraction quotient in lowest terms.
-     */
-    public Fraction divide(Fraction rhs) {
-        return multiply(rhs.reciprocal());
-    }
     
     /**
      * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
@@ -281,21 +270,13 @@
     }
     
     /**
-     * Return the product of this fraction and the given fraction.  The returned
-     * fraction is reduced to lowest terms.
-     * @param rhs the other fraction.
-     * @return the fraction product in lowest terms.
-     */
-    public Fraction multiply(Fraction rhs) {
-        return new Fraction(numerator * rhs.numerator, 
-                denominator * rhs.denominator);
-    }
-    
-    /**
      * Return the additive inverse of this fraction.
      * @return the negation of this fraction.
      */
     public Fraction negate() {
+        if (numerator==Integer.MIN_VALUE) {
+            throw new ArithmeticException("overflow: too large to negate");
+        }
         return new Fraction(-numerator, denominator);
     }
 
@@ -308,13 +289,171 @@
     }
     
     /**
-     * Return the difference between this fraction and the given fraction.  The
-     * returned fraction is reduced to lowest terms.
-     * @param rhs the other fraction.
-     * @return the fraction difference in lowest terms.
+     * <p>Adds the value of this fraction to another, returning the result in reduced
form.
+     * The algorithm follows Knuth, 4.5.1.</p>
+     *
+     * @param fraction  the fraction to add, must not be <code>null</code>
+     * @return a <code>Fraction</code> instance with the resulting values
+     * @throws IllegalArgumentException if the fraction is <code>null</code>
+     * @throws ArithmeticException if the resulting numerator or denominator exceeds
+     *  <code>Integer.MAX_VALUE</code>
      */
-    public Fraction subtract(Fraction rhs) {
-        return add(rhs.negate());
+    public Fraction add(Fraction fraction) {
+        return addSub(fraction, true /* add */);
+    }
+
+    /**
+     * <p>Subtracts the value of another fraction from the value of this one, 
+     * returning the result in reduced form.</p>
+     *
+     * @param fraction  the fraction to subtract, must not be <code>null</code>
+     * @return a <code>Fraction</code> instance with the resulting values
+     * @throws IllegalArgumentException if the fraction is <code>null</code>
+     * @throws ArithmeticException if the resulting numerator or denominator
+     *   cannot be represented in an <code>int</code>.
+     */
+    public Fraction subtract(Fraction fraction) {
+        return addSub(fraction, false /* subtract */);
+    }
+
+    /** 
+     * Implement add and subtract using algorithm described in Knuth 4.5.1.
+     * 
+     * @param fraction the fraction to subtract, must not be <code>null</code>
+     * @param isAdd true to add, false to subtract
+     * @return a <code>Fraction</code> instance with the resulting values
+     * @throws IllegalArgumentException if the fraction is <code>null</code>
+     * @throws ArithmeticException if the resulting numerator or denominator
+     *   cannot be represented in an <code>int</code>.
+     */
+    private Fraction addSub(Fraction fraction, boolean isAdd) {
+        if (fraction == null) {
+            throw new IllegalArgumentException("The fraction must not be null");
+        }
+        // zero is identity for addition.
+        if (numerator == 0) {
+            return isAdd ? fraction : fraction.negate();
+        }
+        if (fraction.numerator == 0) {
+            return this;
+        }     
+        // if denominators are randomly distributed, d1 will be 1 about 61%
+        // of the time.
+        int d1 = MathUtils.gcd(denominator, fraction.denominator);
+        if (d1==1) {
+            // result is ( (u*v' +/- u'v) / u'v')
+            int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
+            int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
+            return new Fraction
+                (isAdd ? MathUtils.addAndCheck(uvp, upv) : 
+                 MathUtils.subAndCheck(uvp, upv),
+                 MathUtils.mulAndCheck(denominator, fraction.denominator));
+        }
+        // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
+        // exercise 7.  we're going to use a BigInteger.
+        // t = u(v'/d1) +/- v(u'/d1)
+        BigInteger uvp = BigInteger.valueOf(numerator)
+        .multiply(BigInteger.valueOf(fraction.denominator/d1));
+        BigInteger upv = BigInteger.valueOf(fraction.numerator)
+        .multiply(BigInteger.valueOf(denominator/d1));
+        BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
+        // but d2 doesn't need extra precision because
+        // d2 = gcd(t,d1) = gcd(t mod d1, d1)
+        int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
+        int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1);
+
+        // result is (t/d2) / (u'/d1)(v'/d2)
+        BigInteger w = t.divide(BigInteger.valueOf(d2));
+        if (w.bitLength() > 31) {
+            throw new ArithmeticException
+            ("overflow: numerator too large after multiply");
+        }
+        return new Fraction (w.intValue(), 
+                MathUtils.mulAndCheck(denominator/d1, 
+                        fraction.denominator/d2));
+    }
+
+    /**
+     * <p>Multiplies the value of this fraction by another, returning the 
+     * result in reduced form.</p>
+     *
+     * @param fraction  the fraction to multiply by, must not be <code>null</code>
+     * @return a <code>Fraction</code> instance with the resulting values
+     * @throws IllegalArgumentException if the fraction is <code>null</code>
+     * @throws ArithmeticException if the resulting numerator or denominator exceeds
+     *  <code>Integer.MAX_VALUE</code>
+     */
+    public Fraction multiply(Fraction fraction) {
+        if (fraction == null) {
+            throw new IllegalArgumentException("The fraction must not be null");
+        }
+        if (numerator == 0 || fraction.numerator == 0) {
+            return ZERO;
+        }
+        // knuth 4.5.1
+        // make sure we don't overflow unless the result *must* overflow.
+        int d1 = MathUtils.gcd(numerator, fraction.denominator);
+        int d2 = MathUtils.gcd(fraction.numerator, denominator);
+        return getReducedFraction
+        (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
+                MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
+    }
+
+    /**
+     * <p>Divide the value of this fraction by another.</p>
+     *
+     * @param fraction  the fraction to divide by, must not be <code>null</code>
+     * @return a <code>Fraction</code> instance with the resulting values
+     * @throws IllegalArgumentException if the fraction is <code>null</code>
+     * @throws ArithmeticException if the fraction to divide by is zero
+     * @throws ArithmeticException if the resulting numerator or denominator exceeds
+     *  <code>Integer.MAX_VALUE</code>
+     */
+    public Fraction divide(Fraction fraction) {
+        if (fraction == null) {
+            throw new IllegalArgumentException("The fraction must not be null");
+        }
+        if (fraction.numerator == 0) {
+            throw new ArithmeticException("The fraction to divide by must not be zero");
+        }
+        return multiply(fraction.reciprocal());
+    }
+    
+    /**
+     * <p>Creates a <code>Fraction</code> instance with the 2 parts
+     * of a fraction Y/Z.</p>
+     *
+     * <p>Any negative signs are resolved to be on the numerator.</p>
+     *
+     * @param numerator  the numerator, for example the three in 'three sevenths'
+     * @param denominator  the denominator, for example the seven in 'three sevenths'
+     * @return a new fraction instance, with the numerator and denominator reduced
+     * @throws ArithmeticException if the denominator is <code>zero</code>
+     */
+    public static Fraction getReducedFraction(int numerator, int denominator) {
+        if (denominator == 0) {
+            throw new ArithmeticException("The denominator must not be zero");
+        }
+        if (numerator==0) {
+            return ZERO; // normalize zero.
+        }
+        // allow 2^k/-2^31 as a valid fraction (where k>0)
+        if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
+            numerator/=2; denominator/=2;
+        }
+        if (denominator < 0) {
+            if (numerator==Integer.MIN_VALUE ||
+                    denominator==Integer.MIN_VALUE) {
+                throw new ArithmeticException("overflow: can't negate");
+            }
+            numerator = -numerator;
+            denominator = -denominator;
+        }
+        // simplify fraction.
+        int gcd = MathUtils.gcd(numerator, denominator);
+        numerator /= gcd;
+        denominator /= gcd;
+        return new Fraction(numerator, denominator);
     }
     
     /**

Modified: jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java?rev=168072&r1=168071&r2=168072&view=diff
==============================================================================
--- jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java
(original)
+++ jakarta/commons/proper/math/trunk/src/java/org/apache/commons/math/util/MathUtils.java
Tue May  3 22:14:59 2005
@@ -535,31 +535,110 @@
     }
 
     /**
-     * Returns the greatest common divisor between two integer values.
-     * @param a the first integer value.
-     * @param b the second integer value.
-     * @return the greatest common divisor between a and b.
+     * <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>
+     *
+     * @param u  a non-zero number
+     * @param v  a non-zero number
+     * @return the greatest common divisor, never zero
      */
-    public static int gcd(int a, int b) {
-        int ret;
-        
-        if (a == 0) {
-            ret = Math.abs(b);
-        } else if (b == 0) {
-            ret = Math.abs(a);
-        } else if (a < 0) {
-            ret = gcd(-a, b);
-        } else if (b < 0) {
-            ret = gcd(a, -b);
-        } else {
-            int r = 0;
-            while(b > 0){
-                r = a % b;
-                a = b;
-                b = r;
+    public static int gcd(int u, int v) {
+        if (u * v == 0) {
+            return (Math.abs(u) + Math.abs(v));
+        }
+        // keep u and v negative, as negative integers range down to
+        // -2^31, while positive numbers can only be as large as 2^31-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<31) { // while u and
v are both even...
+            u/=2; v/=2; k++; // cast out twos.
+        }
+        if (k==31) {
+            throw new ArithmeticException("overflow: gcd is 2^31");
+        }
+        // B2. Initialize: u and v have been divided by 2^k and at least
+        //     one is odd.
+        int 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
             }
-            ret = a;
+            // 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*(1<<k); // gcd is u*2^k
+    }
+
+    /** 
+     * Multiply two integers, checking for overflow.
+     * 
+     * @param x a factor
+     * @param y a factor
+     * @return the product <code>x*y</code>
+     * @throws ArithmeticException if the result can not be represented as
+     *                             an int
+     */
+    public static int mulAndCheck(int x, int y) {
+        long m = ((long)x)*((long)y);
+        if (m < Integer.MIN_VALUE ||
+                m > Integer.MAX_VALUE) {
+            throw new ArithmeticException("overflow: mul");
+        }
+        return (int)m;
+    }
+    
+    /** 
+     * Add two integers, checking for overflow.
+     * 
+     * @param x an addend
+     * @param y an addend
+     * @return the sum <code>x+y</code>
+     * @throws ArithmeticException if the result can not be represented as
+     * an int
+     */
+    public static int addAndCheck(int x, int y) {
+        long s = (long)x+(long)y;
+        if (s < Integer.MIN_VALUE ||
+                s > Integer.MAX_VALUE) {
+            throw new ArithmeticException("overflow: add");
+        }
+        return (int)s;
+    }
+    
+    /** 
+     * Subtract two integers, checking for overflow.
+     * 
+     * @param x the minuend
+     * @param y the subtrahend
+     * @return the difference <code>x-y</code>
+     * @throws ArithmeticException if the result can not be represented as
+     * an int
+     */
+    public static int subAndCheck(int x, int y) {
+        long s = (long)x-(long)y;
+        if (s < Integer.MIN_VALUE ||
+                s > Integer.MAX_VALUE) {
+            throw new ArithmeticException("overflow: add");
         }
-        return ret;
+        return (int)s;
     }
 }

Modified: jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/fraction/FractionTest.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/fraction/FractionTest.java?rev=168072&r1=168071&r2=168072&view=diff
==============================================================================
--- jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/fraction/FractionTest.java
(original)
+++ jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/fraction/FractionTest.java
Tue May  3 22:14:59 2005
@@ -66,6 +66,63 @@
         assertFraction(10, 21, c.abs());
     }
     
+    public void testReciprocal() {
+        Fraction f = null;
+        
+        f = new Fraction(50, 75);
+        f = f.reciprocal();
+        assertEquals(3, f.getNumerator());
+        assertEquals(2, f.getDenominator());
+        
+        f = new Fraction(4, 3);
+        f = f.reciprocal();
+        assertEquals(3, f.getNumerator());
+        assertEquals(4, f.getDenominator());
+        
+        f = new Fraction(-15, 47);
+        f = f.reciprocal();
+        assertEquals(-47, f.getNumerator());
+        assertEquals(15, f.getDenominator());
+        
+        f = new Fraction(0, 3);
+        try {
+            f = f.reciprocal();
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
+
+        // large values
+        f = new Fraction(Integer.MAX_VALUE, 1);
+        f = f.reciprocal();
+        assertEquals(1, f.getNumerator());
+        assertEquals(Integer.MAX_VALUE, f.getDenominator());
+    }
+    
+    public void testNegate() {
+        Fraction f = null;
+        
+        f = new Fraction(50, 75);
+        f = f.negate();
+        assertEquals(-2, f.getNumerator());
+        assertEquals(3, f.getDenominator());
+        
+        f = new Fraction(-50, 75);
+        f = f.negate();
+        assertEquals(2, f.getNumerator());
+        assertEquals(3, f.getDenominator());
+
+        // large values
+        f = new Fraction(Integer.MAX_VALUE-1, Integer.MAX_VALUE);
+        f = f.negate();
+        assertEquals(Integer.MIN_VALUE+2, f.getNumerator());
+        assertEquals(Integer.MAX_VALUE, f.getDenominator());
+
+        f = new Fraction(Integer.MIN_VALUE, 1);
+        try {
+            f = f.negate();
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
+    }
+    
     public void testAdd() {
         Fraction a = new Fraction(1, 2);
         Fraction b = new Fraction(2, 3);
@@ -74,6 +131,75 @@
         assertFraction(7, 6, a.add(b));
         assertFraction(7, 6, b.add(a));
         assertFraction(4, 3, b.add(b));
+        
+        Fraction f1 = new Fraction(Integer.MAX_VALUE - 1, 1);
+        Fraction f2 = Fraction.ONE;
+        Fraction f = f1.add(f2);
+        assertEquals(Integer.MAX_VALUE, f.getNumerator());
+        assertEquals(1, f.getDenominator());
+        
+        f1 = new Fraction(-1, 13*13*2*2);
+        f2 = new Fraction(-2, 13*17*2);
+        f = f1.add(f2);
+        assertEquals(13*13*17*2*2, f.getDenominator());
+        assertEquals(-17 - 2*13*2, f.getNumerator());
+        
+        try {
+            f.add(null);
+            fail("expecting IllegalArgumentException");
+        } catch (IllegalArgumentException ex) {}
+        
+        // if this fraction is added naively, it will overflow.
+        // check that it doesn't.
+        f1 = new Fraction(1,32768*3);
+        f2 = new Fraction(1,59049);
+        f = f1.add(f2);
+        assertEquals(52451, f.getNumerator());
+        assertEquals(1934917632, f.getDenominator());
+
+        f1 = new Fraction(Integer.MIN_VALUE, 3);
+        f2 = new Fraction(1,3);
+        f = f1.add(f2);
+        assertEquals(Integer.MIN_VALUE+1, f.getNumerator());
+        assertEquals(3, f.getDenominator());
+        
+        f1 = new Fraction(Integer.MAX_VALUE - 1, 1);
+        f2 = Fraction.ONE;
+        f = f1.add(f2);
+        assertEquals(Integer.MAX_VALUE, f.getNumerator());
+        assertEquals(1, f.getDenominator());
+        
+        try {
+            f = f.add(Fraction.ONE); // should overflow
+            fail("expecting ArithmeticException but got: " + f.toString());
+        } catch (ArithmeticException ex) {}
+        
+        // denominator should not be a multiple of 2 or 3 to trigger overflow
+        f1 = new Fraction(Integer.MIN_VALUE, 5);
+        f2 = new Fraction(-1,5);
+        try {
+            f = f1.add(f2); // should overflow
+            fail("expecting ArithmeticException but got: " + f.toString());
+        } catch (ArithmeticException ex) {}
+        
+        try {
+            f= new Fraction(-Integer.MAX_VALUE, 1);
+            f = f.add(f);
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
+        
+        try {
+            f= new Fraction(-Integer.MAX_VALUE, 1);
+            f = f.add(f);
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
+        
+        f1 = new Fraction(3,327680);
+        f2 = new Fraction(2,59049);
+        try {
+            f = f1.add(f2); // should overflow
+            fail("expecting ArithmeticException but got: " + f.toString());
+        } catch (ArithmeticException ex) {}
     }
     
     public void testDivide() {
@@ -84,6 +210,51 @@
         assertFraction(3, 4, a.divide(b));
         assertFraction(4, 3, b.divide(a));
         assertFraction(1, 1, b.divide(b));
+        
+        Fraction f1 = new Fraction(3, 5);
+        Fraction f2 = Fraction.ZERO;
+        try {
+            Fraction f = f1.divide(f2);
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
+        
+        f1 = new Fraction(0, 5);
+        f2 = new Fraction(2, 7);
+        Fraction f = f1.divide(f2);
+        assertSame(Fraction.ZERO, f);
+        
+        f1 = new Fraction(2, 7);
+        f2 = Fraction.ONE;
+        f = f1.divide(f2);
+        assertEquals(2, f.getNumerator());
+        assertEquals(7, f.getDenominator());
+        
+        f1 = new Fraction(1, Integer.MAX_VALUE);
+        f = f1.divide(f1);  
+        assertEquals(1, f.getNumerator());
+        assertEquals(1, f.getDenominator());
+        
+        f1 = new Fraction(Integer.MIN_VALUE, Integer.MAX_VALUE);
+        f2 = new Fraction(1, Integer.MAX_VALUE);
+        f = f1.divide(f2);
+        assertEquals(Integer.MIN_VALUE, f.getNumerator());
+        assertEquals(1, f.getDenominator());
+
+        try {
+            f.divide(null);
+            fail("IllegalArgumentException");
+        } catch (IllegalArgumentException ex) {}
+        
+        try {
+            f1 = new Fraction(1, Integer.MAX_VALUE);
+            f = f1.divide(f1.reciprocal());  // should overflow
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
+        try {
+            f1 = new Fraction(1, -Integer.MAX_VALUE);
+            f = f1.divide(f1.reciprocal());  // should overflow
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
     }
     
     public void testMultiply() {
@@ -94,6 +265,17 @@
         assertFraction(1, 3, a.multiply(b));
         assertFraction(1, 3, b.multiply(a));
         assertFraction(4, 9, b.multiply(b));
+        
+        Fraction f1 = new Fraction(Integer.MAX_VALUE, 1);
+        Fraction f2 = new Fraction(Integer.MIN_VALUE, Integer.MAX_VALUE);
+        Fraction f = f1.multiply(f2);
+        assertEquals(Integer.MIN_VALUE, f.getNumerator());
+        assertEquals(1, f.getDenominator());
+
+        try {
+            f.multiply(null);
+            fail("expecting IllegalArgumentException");
+        } catch (IllegalArgumentException ex) {}
     }
     
     public void testSubtract() {
@@ -104,5 +286,65 @@
         assertFraction(-1, 6, a.subtract(b));
         assertFraction(1, 6, b.subtract(a));
         assertFraction(0, 1, b.subtract(b));
+        
+        Fraction f = new Fraction(1,1);
+        try {
+            f.subtract(null);
+            fail("expecting IllegalArgumentException");
+        } catch (IllegalArgumentException ex) {}
+        
+        // if this fraction is subtracted naively, it will overflow.
+        // check that it doesn't.
+        Fraction f1 = new Fraction(1,32768*3);
+        Fraction f2 = new Fraction(1,59049);
+        f = f1.subtract(f2);
+        assertEquals(-13085, f.getNumerator());
+        assertEquals(1934917632, f.getDenominator());
+
+        f1 = new Fraction(Integer.MIN_VALUE, 3);
+        f2 = new Fraction(1,3).negate();
+        f = f1.subtract(f2);
+        assertEquals(Integer.MIN_VALUE+1, f.getNumerator());
+        assertEquals(3, f.getDenominator());
+        
+        f1 = new Fraction(Integer.MAX_VALUE, 1);
+        f2 = Fraction.ONE;
+        f = f1.subtract(f2);
+        assertEquals(Integer.MAX_VALUE-1, f.getNumerator());
+        assertEquals(1, f.getDenominator());
+
+        try {
+            f1 = new Fraction(1, Integer.MAX_VALUE);
+            f2 = new Fraction(1, Integer.MAX_VALUE - 1);
+            f = f1.subtract(f2);
+            fail("expecting ArithmeticException");  //should overflow
+        } catch (ArithmeticException ex) {}
+        
+        // denominator should not be a multiple of 2 or 3 to trigger overflow
+        f1 = new Fraction(Integer.MIN_VALUE, 5);
+        f2 = new Fraction(1,5);
+        try {
+            f = f1.subtract(f2); // should overflow
+            fail("expecting ArithmeticException but got: " + f.toString());
+        } catch (ArithmeticException ex) {}
+        
+        try {
+            f= new Fraction(Integer.MIN_VALUE, 1);
+            f = f.subtract(Fraction.ONE);
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
+        
+        try {
+            f= new Fraction(Integer.MAX_VALUE, 1);
+            f = f.subtract(Fraction.ONE.negate());
+            fail("expecting ArithmeticException");
+        } catch (ArithmeticException ex) {}
+        
+        f1 = new Fraction(3,327680);
+        f2 = new Fraction(2,59049);
+        try {
+            f = f1.subtract(f2); // should overflow
+            fail("expecting ArithmeticException but got: " + f.toString());
+        } catch (ArithmeticException ex) {}
     }
 }

Modified: jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java?rev=168072&r1=168071&r2=168072&view=diff
==============================================================================
--- jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java
(original)
+++ jakarta/commons/proper/math/trunk/src/test/org/apache/commons/math/util/MathUtilsTest.java
Tue May  3 22:14:59 2005
@@ -41,6 +41,42 @@
         return suite;
     }
     
+    public void testAddAndCheck() {
+        int big = Integer.MAX_VALUE;
+        int bigNeg = Integer.MIN_VALUE;
+        assertEquals(big, MathUtils.addAndCheck(big, 0));
+        try {
+            int res = MathUtils.addAndCheck(big, 1);
+        } catch (ArithmeticException ex) {}
+        try {
+            int res = MathUtils.addAndCheck(bigNeg, -1);
+        } catch (ArithmeticException ex) {}
+    }
+    
+    public void testMulAndCheck() {
+        int big = Integer.MAX_VALUE;
+        int bigNeg = Integer.MIN_VALUE;
+        assertEquals(big, MathUtils.mulAndCheck(big, 1));
+        try {
+            int res = MathUtils.mulAndCheck(big, 2);
+        } catch (ArithmeticException ex) {}
+        try {
+            int res = MathUtils.mulAndCheck(bigNeg, 2);
+        } catch (ArithmeticException ex) {}
+    }
+    
+    public void testSubAndCheck() {
+        int big = Integer.MAX_VALUE;
+        int bigNeg = Integer.MIN_VALUE;
+        assertEquals(big, MathUtils.subAndCheck(big, 0));
+        try {
+            int res = MathUtils.subAndCheck(big, -1);
+        } catch (ArithmeticException ex) {}
+        try {
+            int res = MathUtils.subAndCheck(bigNeg, 1);
+        } catch (ArithmeticException ex) {}
+    }
+    
     public void testBinomialCoefficient() {
         long[] bcoef5 = {1,5,10,10,5,1};
         long[] bcoef6 = {1,6,15,20,15,6,1};

Modified: jakarta/commons/proper/math/trunk/xdocs/changes.xml
URL: http://svn.apache.org/viewcvs/jakarta/commons/proper/math/trunk/xdocs/changes.xml?rev=168072&r1=168071&r2=168072&view=diff
==============================================================================
--- jakarta/commons/proper/math/trunk/xdocs/changes.xml (original)
+++ jakarta/commons/proper/math/trunk/xdocs/changes.xml Tue May  3 22:14:59 2005
@@ -44,7 +44,12 @@
         incorrectly using heteroscedastic t statistic.  Also improved sensitivity
         of test cases.
       </action>
-       <action dev="psteitz" type="fix" issue="34448"  due-to="Gilles Gaillard">
+      <action dev="psteitz" type="update">
+        Ported numerics improvements in commons lang Fraction implementation.
+        Added utility methods for overflow-checked integer arithmetic and
+        improved gcd method in MathUtils.
+      </action>
+      <action dev="psteitz" type="fix" issue="34448"  due-to="Gilles Gaillard">
         Fixed javadoc errors. One-sided t-test significance adjustment was
         reversed in javadoc for boolean-valued test methods.
       </action>



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message