commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pste...@apache.org
Subject cvs commit: jakarta-commons/lang/src/test/org/apache/commons/lang/math FractionTest.java
Date Sun, 11 Jul 2004 23:20:17 GMT
psteitz     2004/07/11 16:20:17

  Modified:    lang/src/java/org/apache/commons/lang/math Fraction.java
               lang/src/test/org/apache/commons/lang/math FractionTest.java
  Log:
  Fixed numeric problems reported in PR #29294
  Submitted by: C. Scott Ananian
  Reviewed by: Phil Steitz
  
  Revision  Changes    Path
  1.14      +274 -109  jakarta-commons/lang/src/java/org/apache/commons/lang/math/Fraction.java
  
  Index: Fraction.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/lang/src/java/org/apache/commons/lang/math/Fraction.java,v
  retrieving revision 1.13
  retrieving revision 1.14
  diff -u -r1.13 -r1.14
  --- Fraction.java	18 Feb 2004 22:56:13 -0000	1.13
  +++ Fraction.java	11 Jul 2004 23:20:17 -0000	1.14
  @@ -16,6 +16,7 @@
   package org.apache.commons.lang.math;
   
   import java.io.Serializable;
  +import java.math.BigInteger;
   
   /**
    * <p><code>Fraction</code> is a <code>Number</code> implementation that
  @@ -28,6 +29,7 @@
    * @author Stephen Colebourne
    * @author Tim O'Brien
    * @author Pete Gieser
  + * @author C. Scott Ananian
    * @since 2.0
    * @version $Id$
    */
  @@ -137,6 +139,10 @@
               throw new ArithmeticException("The denominator must not be zero");
           }
           if (denominator < 0) {
  +            if (numerator==Integer.MIN_VALUE ||
  +                    denominator==Integer.MIN_VALUE) {
  +                throw new ArithmeticException("overflow: can't negate");
  +            }
               numerator = -numerator;
               denominator = -denominator;
           }
  @@ -154,7 +160,7 @@
        * @param denominator  the denominator, for example the seven in 'one and three sevenths'
        * @return a new fraction instance
        * @throws ArithmeticException if the denomiator is <code>zero</code>
  -     * @throws ArithmeticException if the denomiator is negative
  +     * @throws ArithmeticException if the denominator is negative
        * @throws ArithmeticException if the numerator is negative
        * @throws ArithmeticException if the resulting numerator exceeds 
        *  <code>Integer.MAX_VALUE</code>
  @@ -169,13 +175,14 @@
           if (numerator < 0) {
               throw new ArithmeticException("The numerator must not be negative");
           }
  -        double numeratorValue = 0;
  +        long numeratorValue;
           if (whole < 0) {
  -            numeratorValue = (double) whole * denominator - numerator;
  +            numeratorValue = whole * (long)denominator - numerator;
           } else {
  -            numeratorValue = (double) whole * denominator + numerator;
  +            numeratorValue = whole * (long)denominator + numerator;
           }
  -        if (Math.abs(numeratorValue) > Integer.MAX_VALUE) {
  +        if (numeratorValue < Integer.MIN_VALUE ||
  +                numeratorValue > Integer.MAX_VALUE)  {
               throw new ArithmeticException("Numerator too large to represent as an Integer.");
           }
           return new Fraction((int) numeratorValue, denominator);
  @@ -190,18 +197,32 @@
        * @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 denomiator is <code>zero</code>
  +     * @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;
           }
  -        int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
  -        return new Fraction(numerator / gcd, denominator / gcd);
  +        // simplify fraction.
  +        int gcd = greatestCommonDivisor(numerator, denominator);
  +        numerator /= gcd;
  +        denominator /= gcd;
  +        return new Fraction(numerator, denominator);
       }
   
       /**
  @@ -215,7 +236,7 @@
        * @return a new fraction instance that is close to the value
        * @throws ArithmeticException if <code>|value| > Integer.MAX_VALUE</code> 
        *  or <code>value = NaN</code>
  -     * @throws ArithmeticException if the calculated denomiator is <code>zero</code>
  +     * @throws ArithmeticException if the calculated denominator is <code>zero</code>
        * @throws ArithmeticException if the the algorithm does not converge
        */
       public static Fraction getFraction(double value) {
  @@ -275,11 +296,11 @@
        *
        * <p>The formats accepted are:</p>
        *
  -     * <p>
        * <ol>
        *  <li><code>double</code> String containing a dot</li>
        *  <li>'X Y/Z'</li>
        *  <li>'Y/Z'</li>
  +     *  <li>'X' (a simple whole number)</li>
        * </ol>
        * and a .</p>
        *
  @@ -307,11 +328,9 @@
               if (pos < 0) {
                   throw new NumberFormatException("The fraction could not be parsed as the format X Y/Z");
               } else {
  +                int numer = Integer.parseInt(str.substring(0, pos));
                   int denom = Integer.parseInt(str.substring(pos + 1));
  -                return getFraction(
  -                    Integer.parseInt(str.substring(0, pos)) + whole * denom,
  -                    denom
  -                );
  +                return getFraction(whole, numer, denom);
               }
           }
   
  @@ -321,10 +340,9 @@
               // simple whole number
               return getFraction(Integer.parseInt(str), 1);
           } else {
  -            return getFraction(
  -                Integer.parseInt(str.substring(0, pos)),
  -                Integer.parseInt(str.substring(pos + 1))
  -            );
  +            int numer = Integer.parseInt(str.substring(0, pos));
  +            int denom = Integer.parseInt(str.substring(pos + 1));
  +            return getFraction(numer, denom);
           }
       }
   
  @@ -440,18 +458,26 @@
       }
   
       /**
  -     * <p>Gets a fraction that is the invert (1/fraction) of this one.</p>
  -     *
  +     * <p>Gets a fraction that is the inverse (1/fraction) of this one.</p>
  +     * 
        * <p>The returned fraction is not reduced.</p>
        *
  -     * @return a new fraction instance with the numerator and denominator inverted
  -     * @throws ArithmeticException if the numerator is <code>zero</code>
  +     * @return a new fraction instance with the numerator and denominator
  +     *         inverted.
  +     * @throws ArithmeticException if the fraction represents zero.
        */
       public Fraction invert() {
           if (numerator == 0) {
  -            throw new ArithmeticException("Unable to invert a fraction with a zero numerator");
  +            throw new ArithmeticException("Unable to invert zero.");
  +        }
  +        if (numerator==Integer.MIN_VALUE) {
  +            throw new ArithmeticException("overflow: can't negate numerator");
  +        }
  +        if (numerator<0) {
  +            return new Fraction(-denominator, -numerator);
  +        } else {
  +            return new Fraction(denominator, numerator);
           }
  -        return getFraction(denominator, numerator);
       }
   
       /**
  @@ -462,12 +488,16 @@
        * @return a new fraction instance with the opposite signed numerator
        */
       public Fraction negate() {
  -        return getFraction(-numerator, denominator);
  +        // the positive range is one smaller than the negative range of an int.
  +        if (numerator==Integer.MIN_VALUE) {
  +            throw new ArithmeticException("overflow: too large to negate");
  +        }
  +        return new Fraction(-numerator, denominator);
       }
   
       /**
        * <p>Gets a fraction that is the positive equivalent of this one.</p>
  -     * <p>More precisely: <pre>(fraction >= 0 ? this : -fraction)</pre></p>
  +     * <p>More precisely: <code>(fraction >= 0 ? this : -fraction)</code></p>
        *
        * <p>The returned fraction is not reduced.</p>
        *
  @@ -478,13 +508,13 @@
           if (numerator >= 0) {
               return this;
           }
  -        return getFraction(-numerator, denominator);
  +        return negate();
       }
   
       /**
        * <p>Gets a fraction that is raised to the passed in power.</p>
        *
  -     * <p>The returned fraction is not reduced.</p>
  +     * <p>The returned fraction is in reduced form.</p>
        *
        * @param power  the power to raise the fraction to
        * @return <code>this</code> if the power is one, <code>ONE</code> if the power
  @@ -498,44 +528,150 @@
               return this;
           } else if (power == 0) {
               return ONE;
  -        } else {
  -            double denominatorValue = Math.pow(denominator, power);
  -            double numeratorValue = Math.pow(numerator, power);
  -            if (numeratorValue > Integer.MAX_VALUE || denominatorValue > Integer.MAX_VALUE) {
  -                throw new ArithmeticException("Integer overflow");
  +        } else if (power < 0) {
  +            if (power==Integer.MIN_VALUE) { // MIN_VALUE can't be negated.
  +                return this.invert().pow(2).pow(-(power/2));
               }
  -            if (power < 0) {
  -                return getFraction((int) Math.pow(denominator, -power), 
  -                    (int) Math.pow(numerator, -power));
  +            return this.invert().pow(-power);
  +        } else {
  +            Fraction f = this.multiplyBy(this);
  +            if ((power % 2) == 0) { // if even...
  +                return f.pow(power/2);
  +            } else { // if odd...
  +                return f.pow(power/2).multiplyBy(this);
               }
  -            return getFraction((int) Math.pow(numerator, power), 
  -                (int) Math.pow(denominator, power));
           }
       }
   
       /**
  -     * <p>Gets the greatest common divisor of two numbers.</p>
  +     * <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 number1  a positive number
  -     * @param number2  a positive number
  +     * @param u  a non-zero number
  +     * @param v  a non-zero number
        * @return the greatest common divisor, never zero
        */
  -    private static int greatestCommonDivisor(int number1, int number2) {
  -        int remainder = number1 % number2;
  -        while (remainder != 0) {
  -            number1 = number2;
  -            number2 = remainder;
  -            remainder = number1 % number2;
  -        }
  -        return number2;
  +    private static int greatestCommonDivisor(int u, int 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
  +            }
  +            // 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
       }
   
       // Arithmetic
       //-------------------------------------------------------------------
   
  +    /** 
  +     * 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
  +     */
  +    private 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;
  +    }
  +    
  +    /**
  +     *  Multiply two non-negative integers, checking for overflow.
  +     * 
  +     * @param x a non-negative factor
  +     * @param y a non-negative factor
  +     * @return the product <code>x*y</code>
  +     * @throws ArithmeticException if the result can not be represented as
  +     * an int
  +     */
  +    private static int mulPosAndCheck(int x, int y) {
  +        /* assert x>=0 && y>=0; */
  +        long m = ((long)x)*((long)y);
  +        if (m > Integer.MAX_VALUE) {
  +            throw new ArithmeticException("overflow: mulPos");
  +        }
  +        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
  +     */
  +    private 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
  +     */
  +    private 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 (int)s;
  +    }
  +    
       /**
  -     * <p>Adds the value of this fraction to another, returning the result in 
  -     * reduced form.</p>
  +     * <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
  @@ -544,48 +680,82 @@
        *  <code>Integer.MAX_VALUE</code>
        */
       public Fraction add(Fraction fraction) {
  -        if (fraction == null) {
  -            throw new IllegalArgumentException("The fraction must not be null");
  -        }
  -        if (numerator == 0) {
  -            return fraction;
  -        }
  -        if (fraction.numerator == 0) {
  -            return this;
  -        }     
  -        // Compute lcd explicitly to limit overflow
  -        int gcd = greatestCommonDivisor(Math.abs(fraction.denominator), Math.abs(denominator));
  -        int thisResidue = denominator/gcd;
  -        int thatResidue = fraction.denominator/gcd;
  -        double denominatorValue = Math.abs((double) gcd * thisResidue * thatResidue);
  -        double numeratorValue = (double) numerator * thatResidue + fraction.numerator * thisResidue;
  -        if (Math.abs(numeratorValue) > Integer.MAX_VALUE || 
  -            Math.abs(denominatorValue) > Integer.MAX_VALUE) {
  -                throw new ArithmeticException("Integer overflow");
  -        }
  -        return Fraction.getReducedFraction((int) numeratorValue, (int) denominatorValue);
  +        return addSub(fraction, true /* add */);
       }
   
       /**
  -     * <p>Subtracts the value of another fraction from the value of this one,
  +     * <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 exceeds
  -     *  <code>Integer.MAX_VALUE</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");
           }
  -        return add(fraction.negate());
  +        // 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 = greatestCommonDivisor(denominator, fraction.denominator);
  +        if (d1==1) {
  +            // result is ( (u*v' +/- u'v) / u'v')
  +            int uvp = mulAndCheck(numerator, fraction.denominator);
  +            int upv = mulAndCheck(fraction.numerator, denominator);
  +            return new Fraction
  +                (isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv),
  +                 mulPosAndCheck(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:greatestCommonDivisor(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(),
  +             mulPosAndCheck(denominator/d1, fraction.denominator/d2));
       }
   
       /**
  -     * <p>Multiplies the value of this fraction by another, returning the result 
  -     * in reduced form.</p>
  +     * <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
  @@ -600,18 +770,17 @@
           if (numerator == 0 || fraction.numerator == 0) {
               return ZERO;
           }
  -        double numeratorValue = (double) numerator * fraction.numerator;
  -        double denominatorValue = (double) denominator * fraction.denominator;
  -        if (Math.abs(numeratorValue) > Integer.MAX_VALUE || 
  -            Math.abs(denominatorValue) > Integer.MAX_VALUE) {
  -                throw new ArithmeticException("Integer overflow");
  -        }
  -        return getReducedFraction((int) numeratorValue, (int) denominatorValue);
  +        // knuth 4.5.1
  +        // make sure we don't overflow unless the result *must* overflow.
  +        int d1 = greatestCommonDivisor(numerator, fraction.denominator);
  +        int d2 = greatestCommonDivisor(fraction.numerator, denominator);
  +        return getReducedFraction
  +            (mulAndCheck(numerator/d1, fraction.numerator/d2),
  +             mulPosAndCheck(denominator/d2, fraction.denominator/d1));
       }
   
       /**
  -     * <p>Divide the value of this fraction by another, returning the result 
  -     * in reduced form.</p>
  +     * <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
  @@ -627,16 +796,7 @@
           if (fraction.numerator == 0) {
               throw new ArithmeticException("The fraction to divide by must not be zero");
           }
  -        if (numerator == 0) {
  -            return ZERO;
  -        }  
  -        double numeratorValue = (double) numerator * fraction.denominator;
  -        double denominatorValue = (double) denominator * fraction.numerator;
  -        if (Math.abs(numeratorValue) > Integer.MAX_VALUE || 
  -            Math.abs(denominatorValue) > Integer.MAX_VALUE) {
  -                throw new ArithmeticException("Integer overflow");
  -        }
  -        return getReducedFraction((int) numeratorValue, (int) denominatorValue);
  +        return multiplyBy(fraction.invert());
       }
   
       // Basics
  @@ -658,8 +818,8 @@
               return false;
           }
           Fraction other = (Fraction) obj;
  -        return (numerator == other.numerator &&
  -                denominator == other.denominator);
  +        return (getNumerator() == other.getNumerator() &&
  +                getDenominator() == other.getDenominator());
       }
   
       /**
  @@ -669,9 +829,8 @@
        */
       public int hashCode() {
           if (hashCode == 0) {
  -            hashCode = 17;
  -            hashCode = 37 * hashCode + numerator;
  -            hashCode = 37 * hashCode + denominator;
  +            // hashcode update should be atomic.
  +            hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator();
           }
           return hashCode;
       }
  @@ -686,6 +845,9 @@
        */
       public int compareTo(Object object) {
           Fraction other = (Fraction) object;
  +        if (this==other) {
  +            return 0;
  +        }
           if (numerator == other.numerator && denominator == other.denominator) {
               return 0;
           }
  @@ -712,9 +874,9 @@
       public String toString() {
           if (toString == null) {
               toString = new StringBuffer(32)
  -                .append(numerator)
  +                .append(getNumerator())
                   .append('/')
  -                .append(denominator).toString();
  +                .append(getDenominator()).toString();
           }
           return toString;
       }
  @@ -734,7 +896,11 @@
                   toProperString = "0";
               } else if (numerator == denominator) {
                   toProperString = "1";
  -            } else if (Math.abs(numerator) > denominator) {
  +            } else if ((numerator>0?-numerator:numerator) < -denominator) {
  +                // note that we do the magnitude comparison test above with
  +                // NEGATIVE (not positive) numbers, since negative numbers
  +                // have a larger range.  otherwise numerator==Integer.MIN_VALUE
  +                // is handled incorrectly.
                   int properNumerator = getProperNumerator();
                   if (properNumerator == 0) {
                       toProperString = Integer.toString(getProperWhole());
  @@ -742,15 +908,14 @@
                       toProperString = new StringBuffer(32)
                           .append(getProperWhole()).append(' ')
                           .append(properNumerator).append('/')
  -                        .append(denominator).toString();
  +                        .append(getDenominator()).toString();
                   }
               } else {
                   toProperString = new StringBuffer(32)
  -                    .append(numerator).append('/')
  -                    .append(denominator).toString();
  +                    .append(getNumerator()).append('/')
  +                    .append(getDenominator()).toString();
               }
           }
           return toProperString;
       }
  -
   }
  
  
  
  1.7       +335 -17   jakarta-commons/lang/src/test/org/apache/commons/lang/math/FractionTest.java
  
  Index: FractionTest.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons/lang/src/test/org/apache/commons/lang/math/FractionTest.java,v
  retrieving revision 1.6
  retrieving revision 1.7
  diff -u -r1.6 -r1.7
  --- FractionTest.java	18 Feb 2004 23:02:38 -0000	1.6
  +++ FractionTest.java	11 Jul 2004 23:20:17 -0000	1.7
  @@ -18,15 +18,21 @@
   import junit.framework.Test;
   import junit.framework.TestCase;
   import junit.framework.TestSuite;
  +
  +import java.io.ByteArrayInputStream;
  +import java.io.ByteArrayOutputStream;
  +import java.io.ObjectInputStream;
  +import java.io.ObjectOutputStream;
   /**
  - * Test cases for the {@link Fraction} classes.
  + * Test cases for the {@link Fraction} class
    *
    * @author Stephen Colebourne
  + * @author C. Scott Ananian
    * @version $Id$
    */
   public class FractionTest extends TestCase {
       
  -    private static final int SKIP = 53;
  +    private static final int SKIP = 500;  //53
   
       public FractionTest(String name) {
           super(name);
  @@ -80,7 +86,7 @@
           assertEquals(4, Fraction.FOUR_FIFTHS.getNumerator());
           assertEquals(5, Fraction.FOUR_FIFTHS.getDenominator());
       }
  -    
  +
       public void testFactory_int_int() {
           Fraction f = null;
           
  @@ -139,6 +145,16 @@
               f = Fraction.getFraction(-3, 0);
               fail("expecting ArithmeticException");
           } catch (ArithmeticException ex) {}
  +
  +        // very large: can't represent as unsimplified fraction, although
  +        try {
  +            f = Fraction.getFraction(4, Integer.MIN_VALUE);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +        try {
  +            f = Fraction.getFraction(1, Integer.MIN_VALUE);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
       }
   
       public void testFactory_int_int_int() {
  @@ -223,8 +239,26 @@
               f = Fraction.getFraction(-Integer.MAX_VALUE, 1, 2);
               fail("expecting ArithmeticException");
           } catch (ArithmeticException ex) {}
  -    }
   
  +        // very large
  +        f = Fraction.getFraction(-1, 0, Integer.MAX_VALUE);
  +        assertEquals(-Integer.MAX_VALUE, f.getNumerator());
  +        assertEquals(Integer.MAX_VALUE, f.getDenominator());
  +
  +        try {
  +            // negative denominators not allowed in this constructor.
  +            f = Fraction.getFraction(0, 4, Integer.MIN_VALUE);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +        try {
  +            f = Fraction.getFraction(1, 1, Integer.MAX_VALUE);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +        try {
  +            f = Fraction.getFraction(-1, 2, Integer.MAX_VALUE);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +    }
       public void testReducedFactory_int_int() {
           Fraction f = null;
           
  @@ -296,6 +330,18 @@
           f = Fraction.getReducedFraction(121, 22);
           assertEquals(11, f.getNumerator());
           assertEquals(2, f.getDenominator());
  +        
  +        // Extreme values 
  +        // OK, can reduce before negating
  +        f = Fraction.getReducedFraction(-2, Integer.MIN_VALUE);
  +        assertEquals(1, f.getNumerator());
  +        assertEquals(-(Integer.MIN_VALUE / 2), f.getDenominator());
  +        
  +        // Can't reduce, negation will throw
  +        try { 
  +            f = Fraction.getReducedFraction(-7, Integer.MIN_VALUE);  
  +            fail("Expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}      
       }
   
       public void testFactory_double() {
  @@ -391,7 +437,7 @@
       public void testFactory_String() {
           try {
               Fraction.getFraction(null);
  -            fail("expecting ArithmeticException");
  +            fail("expecting IllegalArgumentException");
           } catch (IllegalArgumentException ex) {}
       }
       
  @@ -417,6 +463,7 @@
           
           try {
               f = Fraction.getFraction("2.3R");
  +            fail("Expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
           
           try {
  @@ -426,6 +473,7 @@
           
           try {
               f = Fraction.getFraction(".");
  +            fail("Expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
       }
   
  @@ -448,34 +496,42 @@
           assertEquals(6, f.getNumerator());
           assertEquals(4, f.getDenominator());
           
  +        f = Fraction.getFraction("-7 1/2");
  +        assertEquals(-15, f.getNumerator());
  +        assertEquals(2, f.getDenominator());
  +        
  +        f = Fraction.getFraction("-1 2/4");
  +        assertEquals(-6, f.getNumerator());
  +        assertEquals(4, f.getDenominator());
  +        
           try {
               f = Fraction.getFraction("2 3");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
           
           try {
               f = Fraction.getFraction("a 3");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
           
           try {
               f = Fraction.getFraction("2 b/4");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
           
           try {
               f = Fraction.getFraction("2 ");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
   
           try {
               f = Fraction.getFraction(" 3");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
           
           try {
               f = Fraction.getFraction(" ");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
       }
   
  @@ -508,22 +564,22 @@
           
           try {
               f = Fraction.getFraction("2/d");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
           
           try {
               f = Fraction.getFraction("2e/3");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
           
           try {
               f = Fraction.getFraction("2/");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
           
           try {
               f = Fraction.getFraction("/");
  -            fail("expecting NumberFomatException");
  +            fail("expecting NumberFormatException");
           } catch (NumberFormatException ex) {}
       }
   
  @@ -541,6 +597,12 @@
           assertEquals(-3, f.getProperWhole());
           assertEquals(5, f.getProperNumerator());
           assertEquals(6, f.getDenominator());
  +
  +        f = Fraction.getFraction(Integer.MIN_VALUE, 0, 1);
  +        assertEquals(Integer.MIN_VALUE, f.getNumerator());
  +        assertEquals(Integer.MIN_VALUE, f.getProperWhole());
  +        assertEquals(0, f.getProperNumerator());
  +        assertEquals(1, f.getDenominator());
       }
               
       public void testConversions() {
  @@ -560,6 +622,11 @@
           f = f.reduce();
           assertEquals(2, f.getNumerator());
           assertEquals(3, f.getDenominator());
  +
  +        f = Fraction.getFraction(2, 3);
  +        f = f.reduce();
  +        assertEquals(2, f.getNumerator());
  +        assertEquals(3, f.getDenominator());
       }
       
       public void testInvert() {
  @@ -575,10 +642,28 @@
           assertEquals(3, f.getNumerator());
           assertEquals(4, f.getDenominator());
           
  +        f = Fraction.getFraction(-15, 47);
  +        f = f.invert();
  +        assertEquals(-47, f.getNumerator());
  +        assertEquals(15, f.getDenominator());
  +        
           f = Fraction.getFraction(0, 3);
           try {
               f = f.invert();
  +            fail("expecting ArithmeticException");
           } catch (ArithmeticException ex) {}
  +
  +        // large values
  +        f = Fraction.getFraction(Integer.MIN_VALUE, 1);
  +        try {
  +            f = f.invert();
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +
  +        f = Fraction.getFraction(Integer.MAX_VALUE, 1);
  +        f = f.invert();
  +        assertEquals(1, f.getNumerator());
  +        assertEquals(Integer.MAX_VALUE, f.getDenominator());
       }
       
       public void testNegate() {
  @@ -593,6 +678,18 @@
           f = f.negate();
           assertEquals(50, f.getNumerator());
           assertEquals(75, f.getDenominator());
  +
  +        // large values
  +        f = Fraction.getFraction(Integer.MAX_VALUE-1, Integer.MAX_VALUE);
  +        f = f.negate();
  +        assertEquals(Integer.MIN_VALUE+2, f.getNumerator());
  +        assertEquals(Integer.MAX_VALUE, f.getDenominator());
  +
  +        f = Fraction.getFraction(Integer.MIN_VALUE, 1);
  +        try {
  +            f = f.negate();
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
       }
       
       public void testAbs() {
  @@ -607,6 +704,22 @@
           f = f.abs();
           assertEquals(50, f.getNumerator());
           assertEquals(75, f.getDenominator());
  +
  +        f = Fraction.getFraction(Integer.MAX_VALUE, 1);
  +        f = f.abs();
  +        assertEquals(Integer.MAX_VALUE, f.getNumerator());
  +        assertEquals(1, f.getDenominator());
  +
  +        f = Fraction.getFraction(Integer.MAX_VALUE, -1);
  +        f = f.abs();
  +        assertEquals(Integer.MAX_VALUE, f.getNumerator());
  +        assertEquals(1, f.getDenominator());
  +
  +        f = Fraction.getFraction(Integer.MIN_VALUE, 1);
  +        try {
  +            f = f.abs();
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
       }
       
       public void testPow() {
  @@ -617,6 +730,7 @@
           
           f = Fraction.getFraction(3, 5);
           assertSame(f, f.pow(1));
  +        assertEquals(f, f.pow(1));
   
           f = Fraction.getFraction(3, 5);
           f = f.pow(2);
  @@ -638,7 +752,82 @@
           assertEquals(25, f.getNumerator());
           assertEquals(9, f.getDenominator());
           
  -        f = Fraction.getFraction(Integer.MAX_VALUE);
  +        // check unreduced fractions stay that way.
  +        f = Fraction.getFraction(6, 10);
  +        assertEquals(Fraction.ONE, f.pow(0));
  +        
  +        f = Fraction.getFraction(6, 10);
  +        assertEquals(f, f.pow(1));
  +        assertFalse(f.pow(1).equals(Fraction.getFraction(3,5)));
  +
  +        f = Fraction.getFraction(6, 10);
  +        f = f.pow(2);
  +        assertEquals(9, f.getNumerator());
  +        assertEquals(25, f.getDenominator());
  +        
  +        f = Fraction.getFraction(6, 10);
  +        f = f.pow(3);
  +        assertEquals(27, f.getNumerator());
  +        assertEquals(125, f.getDenominator());
  +        
  +        f = Fraction.getFraction(6, 10);
  +        f = f.pow(-1);
  +        assertEquals(10, f.getNumerator());
  +        assertEquals(6, f.getDenominator());
  +        
  +        f = Fraction.getFraction(6, 10);
  +        f = f.pow(-2);
  +        assertEquals(25, f.getNumerator());
  +        assertEquals(9, f.getDenominator());
  +        
  +        // zero to any positive power is still zero.
  +        f = Fraction.getFraction(0, 1231);
  +        f = f.pow(1);
  +        assertTrue(0==f.compareTo(Fraction.ZERO));
  +        assertEquals(0, f.getNumerator());
  +        assertEquals(1231, f.getDenominator());
  +        f = f.pow(2);
  +        assertTrue(0==f.compareTo(Fraction.ZERO));
  +        assertEquals(0, f.getNumerator());
  +        assertEquals(1, f.getDenominator());
  +
  +        // zero to negative powers should throw an exception
  +        try {
  +            f = f.pow(-1);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +        try {
  +            f = f.pow(Integer.MIN_VALUE);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +
  +        // one to any power is still one.
  +        f = Fraction.getFraction(1, 1);
  +        f = f.pow(0);
  +        assertEquals(f, Fraction.ONE);
  +        f = f.pow(1);
  +        assertEquals(f, Fraction.ONE);
  +        f = f.pow(-1);
  +        assertEquals(f, Fraction.ONE);
  +        f = f.pow(Integer.MAX_VALUE);
  +        assertEquals(f, Fraction.ONE);
  +        f = f.pow(Integer.MIN_VALUE);
  +        assertEquals(f, Fraction.ONE);
  +
  +        f = Fraction.getFraction(Integer.MAX_VALUE, 1);
  +        try {
  +            f = f.pow(2);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +
  +        // Numerator growing too negative during the pow operation.
  +        f = Fraction.getFraction(Integer.MIN_VALUE, 1);
  +        try {
  +            f = f.pow(3);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +
  +        f = Fraction.getFraction(65536, 1);
           try {
               f = f.pow(2);
               fail("expecting ArithmeticException");
  @@ -699,11 +888,31 @@
           f = f2.add(f1);
           assertSame(f2, f);
           
  +        f1 = Fraction.getFraction(-1, 13*13*2*2);
  +        f2 = Fraction.getFraction(-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 = Fraction.getFraction(1,32768*3);
  +        f2 = Fraction.getFraction(1,59049);
  +        f = f1.add(f2);
  +        assertEquals(52451, f.getNumerator());
  +        assertEquals(1934917632, f.getDenominator());
  +
  +        f1 = Fraction.getFraction(Integer.MIN_VALUE, 3);
  +        f2 = Fraction.ONE_THIRD;
  +        f = f1.add(f2);
  +        assertEquals(Integer.MIN_VALUE+1, f.getNumerator());
  +        assertEquals(3, f.getDenominator());
  +        
           f1 = Fraction.getFraction(Integer.MAX_VALUE - 1, 1);
           f2 = Fraction.ONE;
           f = f1.add(f2);
  @@ -715,12 +924,32 @@
               fail("expecting ArithmeticException but got: " + f.toString());
           } catch (ArithmeticException ex) {}
           
  +        // denominator should not be a multiple of 2 or 3 to trigger overflow
  +        f1 = Fraction.getFraction(Integer.MIN_VALUE, 5);
  +        f2 = Fraction.getFraction(-1,5);
  +        try {
  +            f = f1.add(f2); // should overflow
  +            fail("expecting ArithmeticException but got: " + f.toString());
  +        } catch (ArithmeticException ex) {}
  +        
           try {
               f= Fraction.getFraction(-Integer.MAX_VALUE, 1);
               f = f.add(f);
               fail("expecting ArithmeticException");
           } catch (ArithmeticException ex) {}
               
  +        try {
  +            f= Fraction.getFraction(-Integer.MAX_VALUE, 1);
  +            f = f.add(f);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +            
  +        f1 = Fraction.getFraction(3,327680);
  +        f2 = Fraction.getFraction(2,59049);
  +        try {
  +            f = f1.add(f2); // should overflow
  +            fail("expecting ArithmeticException but got: " + f.toString());
  +        } catch (ArithmeticException ex) {}
       }
               
       public void testSubtract() {
  @@ -780,6 +1009,26 @@
               fail("expecting IllegalArgumentException");
           } catch (IllegalArgumentException ex) {}
           
  +        // if this fraction is subtracted naively, it will overflow.
  +        // check that it doesn't.
  +        f1 = Fraction.getFraction(1,32768*3);
  +        f2 = Fraction.getFraction(1,59049);
  +        f = f1.subtract(f2);
  +        assertEquals(-13085, f.getNumerator());
  +        assertEquals(1934917632, f.getDenominator());
  +
  +        f1 = Fraction.getFraction(Integer.MIN_VALUE, 3);
  +        f2 = Fraction.ONE_THIRD.negate();
  +        f = f1.subtract(f2);
  +        assertEquals(Integer.MIN_VALUE+1, f.getNumerator());
  +        assertEquals(3, f.getDenominator());
  +        
  +        f1 = Fraction.getFraction(Integer.MAX_VALUE, 1);
  +        f2 = Fraction.ONE;
  +        f = f1.subtract(f2);
  +        assertEquals(Integer.MAX_VALUE-1, f.getNumerator());
  +        assertEquals(1, f.getDenominator());
  +
           try {
               f1 = Fraction.getFraction(1, Integer.MAX_VALUE);
               f2 = Fraction.getFraction(1, Integer.MAX_VALUE - 1);
  @@ -787,6 +1036,32 @@
               fail("expecting ArithmeticException");  //should overflow
           } catch (ArithmeticException ex) {}
               
  +        // denominator should not be a multiple of 2 or 3 to trigger overflow
  +        f1 = Fraction.getFraction(Integer.MIN_VALUE, 5);
  +        f2 = Fraction.getFraction(1,5);
  +        try {
  +            f = f1.subtract(f2); // should overflow
  +            fail("expecting ArithmeticException but got: " + f.toString());
  +        } catch (ArithmeticException ex) {}
  +        
  +        try {
  +            f= Fraction.getFraction(Integer.MIN_VALUE, 1);
  +            f = f.subtract(Fraction.ONE);
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +            
  +        try {
  +            f= Fraction.getFraction(Integer.MAX_VALUE, 1);
  +            f = f.subtract(Fraction.ONE.negate());
  +            fail("expecting ArithmeticException");
  +        } catch (ArithmeticException ex) {}
  +            
  +        f1 = Fraction.getFraction(3,327680);
  +        f2 = Fraction.getFraction(2,59049);
  +        try {
  +            f = f1.subtract(f2); // should overflow
  +            fail("expecting ArithmeticException but got: " + f.toString());
  +        } catch (ArithmeticException ex) {}
       }
               
       public void testMultiply() {
  @@ -800,6 +1075,15 @@
           assertEquals(6, f.getNumerator());
           assertEquals(25, f.getDenominator());
           
  +        f1 = Fraction.getFraction(6, 10);
  +        f2 = Fraction.getFraction(6, 10);
  +        f = f1.multiplyBy(f2);
  +        assertEquals(9, f.getNumerator());
  +        assertEquals(25, f.getDenominator());
  +        f = f.multiplyBy(f2);
  +        assertEquals(27, f.getNumerator());
  +        assertEquals(125, f.getDenominator());
  +        
           f1 = Fraction.getFraction(3, 5);
           f2 = Fraction.getFraction(-2, 5);
           f = f1.multiplyBy(f2);
  @@ -812,6 +1096,7 @@
           assertEquals(6, f.getNumerator());
           assertEquals(25, f.getDenominator());
           
  +        
           f1 = Fraction.getFraction(0, 5);
           f2 = Fraction.getFraction(2, 7);
           f = f1.multiplyBy(f2);
  @@ -823,6 +1108,12 @@
           assertEquals(2, f.getNumerator());
           assertEquals(7, f.getDenominator());
           
  +        f1 = Fraction.getFraction(Integer.MAX_VALUE, 1);
  +        f2 = Fraction.getFraction(Integer.MIN_VALUE, Integer.MAX_VALUE);
  +        f = f1.multiplyBy(f2);
  +        assertEquals(Integer.MIN_VALUE, f.getNumerator());
  +        assertEquals(1, f.getDenominator());
  +
           try {
               f.multiplyBy(null);
               fail("expecting IllegalArgumentException");
  @@ -875,6 +1166,12 @@
           assertEquals(1, f.getNumerator());
           assertEquals(1, f.getDenominator());
           
  +        f1 = Fraction.getFraction(Integer.MIN_VALUE, Integer.MAX_VALUE);
  +        f2 = Fraction.getFraction(1, Integer.MAX_VALUE);
  +        f = f1.divideBy(f2);
  +        assertEquals(Integer.MIN_VALUE, f.getNumerator());
  +        assertEquals(1, f.getDenominator());
  +
           try {
               f.divideBy(null);
               fail("IllegalArgumentException");
  @@ -932,6 +1229,7 @@
           Fraction f2 = null;
           
           f1 = Fraction.getFraction(3, 5);
  +        assertTrue(f1.compareTo(f1) == 0);
           
           try {
               f1.compareTo(null);
  @@ -945,15 +1243,24 @@
           
           f2 = Fraction.getFraction(2, 5);
           assertTrue(f1.compareTo(f2) > 0);
  +        assertTrue(f2.compareTo(f2) == 0);
           
           f2 = Fraction.getFraction(4, 5);
           assertTrue(f1.compareTo(f2) < 0);
  +        assertTrue(f2.compareTo(f2) == 0);
           
           f2 = Fraction.getFraction(3, 5);
           assertTrue(f1.compareTo(f2) == 0);
  +        assertTrue(f2.compareTo(f2) == 0);
           
           f2 = Fraction.getFraction(6, 10);
           assertTrue(f1.compareTo(f2) == 0);
  +        assertTrue(f2.compareTo(f2) == 0);
  +
  +        f2 = Fraction.getFraction(-1, 1, Integer.MAX_VALUE);
  +        assertTrue(f1.compareTo(f2) > 0);
  +        assertTrue(f2.compareTo(f2) == 0);
  +
       }
       
       public void testToString() {
  @@ -975,6 +1282,12 @@
           
           f = Fraction.getFraction(2, 2);
           assertEquals("2/2", f.toString());        
  +
  +        f = Fraction.getFraction(Integer.MIN_VALUE, 0, 1);
  +        assertEquals("-2147483648/1", f.toString());        
  +
  +        f = Fraction.getFraction(-1, 1, Integer.MAX_VALUE);
  +        assertEquals("-2147483648/2147483647", f.toString());
       }
       
       public void testToProperString() {
  @@ -1002,6 +1315,11 @@
           
           f = Fraction.getFraction(-7, 5);
           assertEquals("-1 2/5", f.toProperString());        
  +
  +        f = Fraction.getFraction(Integer.MIN_VALUE, 0, 1);
  +        assertEquals("-2147483648", f.toProperString());        
  +
  +        f = Fraction.getFraction(-1, 1, Integer.MAX_VALUE);
  +        assertEquals("-1 1/2147483647", f.toProperString());
       }
  -    
   }
  
  
  

---------------------------------------------------------------------
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