001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.math.fraction;
018    
019    import java.io.Serializable;
020    import java.math.BigInteger;
021    
022    import org.apache.commons.math.FieldElement;
023    import org.apache.commons.math.MathRuntimeException;
024    import org.apache.commons.math.util.MathUtils;
025    
026    /**
027     * Representation of a rational number.
028     *
029     * implements Serializable since 2.0
030     * 
031     * @since 1.1
032     * @version $Revision: 795903 $ $Date: 2009-07-20 12:29:46 -0400 (Mon, 20 Jul 2009) $
033     */
034    public class Fraction
035        extends Number
036        implements FieldElement<Fraction>, Comparable<Fraction>, Serializable {
037    
038        /** A fraction representing "2 / 1". */
039        public static final Fraction TWO = new Fraction(2, 1);
040    
041        /** A fraction representing "1". */
042        public static final Fraction ONE = new Fraction(1, 1);
043    
044        /** A fraction representing "0". */
045        public static final Fraction ZERO = new Fraction(0, 1);
046    
047        /** A fraction representing "4/5". */
048        public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
049    
050        /** A fraction representing "1/5". */
051        public static final Fraction ONE_FIFTH = new Fraction(1, 5);
052    
053        /** A fraction representing "1/2". */
054        public static final Fraction ONE_HALF = new Fraction(1, 2);
055    
056        /** A fraction representing "1/4". */
057        public static final Fraction ONE_QUARTER = new Fraction(1, 4);
058    
059        /** A fraction representing "1/3". */
060        public static final Fraction ONE_THIRD = new Fraction(1, 3);
061    
062        /** A fraction representing "3/5". */
063        public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
064    
065        /** A fraction representing "3/4". */
066        public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
067    
068        /** A fraction representing "2/5". */
069        public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
070    
071        /** A fraction representing "2/4". */
072        public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
073    
074        /** A fraction representing "2/3". */
075        public static final Fraction TWO_THIRDS = new Fraction(2, 3);
076    
077        /** A fraction representing "-1 / 1". */
078        public static final Fraction MINUS_ONE = new Fraction(-1, 1);
079    
080        /** Serializable version identifier */
081        private static final long serialVersionUID = 3698073679419233275L;
082    
083        /** The denominator. */
084        private final int denominator;
085        
086        /** The numerator. */
087        private final int numerator;
088    
089        /**
090         * Create a fraction given the double value.
091         * @param value the double value to convert to a fraction.
092         * @throws FractionConversionException if the continued fraction failed to
093         *         converge.
094         */
095        public Fraction(double value) throws FractionConversionException {
096            this(value, 1.0e-5, 100);
097        }
098    
099        /**
100         * Create a fraction given the double value and maximum error allowed.
101         * <p>
102         * References:
103         * <ul>
104         * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
105         * Continued Fraction</a> equations (11) and (22)-(26)</li>
106         * </ul>
107         * </p>
108         * @param value the double value to convert to a fraction.
109         * @param epsilon maximum error allowed.  The resulting fraction is within
110         *        <code>epsilon</code> of <code>value</code>, in absolute terms.
111         * @param maxIterations maximum number of convergents
112         * @throws FractionConversionException if the continued fraction failed to
113         *         converge.
114         */
115        public Fraction(double value, double epsilon, int maxIterations)
116            throws FractionConversionException
117        {
118            this(value, epsilon, Integer.MAX_VALUE, maxIterations);
119        }
120    
121        /**
122         * Create a fraction given the double value and maximum denominator.
123         * <p>
124         * References:
125         * <ul>
126         * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
127         * Continued Fraction</a> equations (11) and (22)-(26)</li>
128         * </ul>
129         * </p>
130         * @param value the double value to convert to a fraction.
131         * @param maxDenominator The maximum allowed value for denominator
132         * @throws FractionConversionException if the continued fraction failed to
133         *         converge
134         */
135        public Fraction(double value, int maxDenominator)
136            throws FractionConversionException
137        {
138           this(value, 0, maxDenominator, 100);
139        }
140    
141        /**
142         * Create a fraction given the double value and either the maximum error
143         * allowed or the maximum number of denominator digits.
144         * <p>
145         *
146         * NOTE: This constructor is called with EITHER
147         *   - a valid epsilon value and the maxDenominator set to Integer.MAX_VALUE
148         *     (that way the maxDenominator has no effect).
149         * OR
150         *   - a valid maxDenominator value and the epsilon value set to zero
151         *     (that way epsilon only has effect if there is an exact match before
152         *     the maxDenominator value is reached).
153         * </p><p>
154         *
155         * It has been done this way so that the same code can be (re)used for both
156         * scenarios. However this could be confusing to users if it were part of
157         * the public API and this constructor should therefore remain PRIVATE.
158         * </p>
159         *
160         * See JIRA issue ticket MATH-181 for more details:
161         *
162         *     https://issues.apache.org/jira/browse/MATH-181
163         *
164         * @param value the double value to convert to a fraction.
165         * @param epsilon maximum error allowed.  The resulting fraction is within
166         *        <code>epsilon</code> of <code>value</code>, in absolute terms.
167         * @param maxDenominator maximum denominator value allowed.
168         * @param maxIterations maximum number of convergents
169         * @throws FractionConversionException if the continued fraction failed to
170         *         converge.
171         */
172        private Fraction(double value, double epsilon, int maxDenominator, int maxIterations)
173            throws FractionConversionException
174        {
175            long overflow = Integer.MAX_VALUE;
176            double r0 = value;
177            long a0 = (long)Math.floor(r0);
178            if (a0 > overflow) {
179                throw new FractionConversionException(value, a0, 1l);
180            }
181    
182            // check for (almost) integer arguments, which should not go
183            // to iterations.
184            if (Math.abs(a0 - value) < epsilon) {
185                this.numerator = (int) a0;
186                this.denominator = 1;
187                return;
188            }
189    
190            long p0 = 1;
191            long q0 = 0;
192            long p1 = a0;
193            long q1 = 1;
194    
195            long p2 = 0;
196            long q2 = 1;
197    
198            int n = 0;
199            boolean stop = false;
200            do {
201                ++n;
202                double r1 = 1.0 / (r0 - a0);
203                long a1 = (long)Math.floor(r1);
204                p2 = (a1 * p1) + p0;
205                q2 = (a1 * q1) + q0;
206                if ((p2 > overflow) || (q2 > overflow)) {
207                    throw new FractionConversionException(value, p2, q2);
208                }
209                
210                double convergent = (double)p2 / (double)q2;
211                if (n < maxIterations && Math.abs(convergent - value) > epsilon && q2 < maxDenominator) {
212                    p0 = p1;
213                    p1 = p2;
214                    q0 = q1;
215                    q1 = q2;
216                    a0 = a1;
217                    r0 = r1;
218                } else {
219                    stop = true;
220                }
221            } while (!stop);
222    
223            if (n >= maxIterations) {
224                throw new FractionConversionException(value, maxIterations);
225            }
226            
227            if (q2 < maxDenominator) {
228                this.numerator = (int) p2;
229                this.denominator = (int) q2;
230            } else {
231                this.numerator = (int) p1;
232                this.denominator = (int) q1;
233            }
234    
235        }
236        
237        /**
238         * Create a fraction from an int. 
239         * The fraction is num / 1.
240         * @param num the numerator.
241         */
242        public Fraction(int num) {
243            this(num, 1);
244        }
245        
246        /**
247         * Create a fraction given the numerator and denominator.  The fraction is
248         * reduced to lowest terms.
249         * @param num the numerator.
250         * @param den the denominator.
251         * @throws ArithmeticException if the denominator is <code>zero</code>
252         */
253        public Fraction(int num, int den) {
254            if (den == 0) {
255                throw MathRuntimeException.createArithmeticException("zero denominator in fraction {0}/{1}",
256                                                                     num, den);
257            }
258            if (den < 0) {
259                if (num == Integer.MIN_VALUE || den == Integer.MIN_VALUE) {
260                    throw MathRuntimeException.createArithmeticException("overflow in fraction {0}/{1}, cannot negate",
261                                                                         num, den);
262                }
263                num = -num;
264                den = -den;
265            }
266            // reduce numerator and denominator by greatest common denominator.
267            final int d = MathUtils.gcd(num, den);
268            if (d > 1) {
269                num /= d;
270                den /= d;
271            }
272            
273            // move sign to numerator.
274            if (den < 0) {
275                num = -num;
276                den = -den;
277            }
278            this.numerator   = num;
279            this.denominator = den;
280        }
281        
282        /**
283         * Returns the absolute value of this fraction.
284         * @return the absolute value.
285         */
286        public Fraction abs() {
287            Fraction ret;
288            if (numerator >= 0) {
289                ret = this;
290            } else {
291                ret = negate();
292            }
293            return ret;        
294        }
295        
296        /**
297         * Compares this object to another based on size.
298         * @param object the object to compare to
299         * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
300         *         than <tt>object</tt>, 0 if they are equal.
301         */
302        public int compareTo(Fraction object) {
303            long nOd = ((long) numerator) * object.denominator;
304            long dOn = ((long) denominator) * object.numerator;
305            return (nOd < dOn) ? -1 : ((nOd > dOn) ? +1 : 0);
306        }
307    
308        /**
309         * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
310         * the numerator divided by denominator.
311         * @return the fraction as a <tt>double</tt>
312         */
313        @Override
314        public double doubleValue() {
315            return (double)numerator / (double)denominator;
316        }
317        
318        /**
319         * Test for the equality of two fractions.  If the lowest term
320         * numerator and denominators are the same for both fractions, the two
321         * fractions are considered to be equal.
322         * @param other fraction to test for equality to this fraction
323         * @return true if two fractions are equal, false if object is
324         *         <tt>null</tt>, not an instance of {@link Fraction}, or not equal
325         *         to this fraction instance.
326         */
327        @Override
328        public boolean equals(Object other) {
329            boolean ret;
330            
331            if (this == other) { 
332                ret = true;
333            } else if (other == null) {
334                ret = false;
335            } else {
336                try {
337                    // since fractions are always in lowest terms, numerators and
338                    // denominators can be compared directly for equality.
339                    Fraction rhs = (Fraction)other;
340                    ret = (numerator == rhs.numerator) &&
341                        (denominator == rhs.denominator);
342                } catch (ClassCastException ex) {
343                    // ignore exception
344                    ret = false;
345                }
346            }
347            
348            return ret;
349        }
350        
351        /**
352         * Gets the fraction as a <tt>float</tt>. This calculates the fraction as
353         * the numerator divided by denominator.
354         * @return the fraction as a <tt>float</tt>
355         */
356        @Override
357        public float floatValue() {
358            return (float)doubleValue();
359        }
360        
361        /**
362         * Access the denominator.
363         * @return the denominator.
364         */
365        public int getDenominator() {
366            return denominator;
367        }
368        
369        /**
370         * Access the numerator.
371         * @return the numerator.
372         */
373        public int getNumerator() {
374            return numerator;
375        }
376        
377        /**
378         * Gets a hashCode for the fraction.
379         * @return a hash code value for this object
380         */
381        @Override
382        public int hashCode() {
383            return 37 * (37 * 17 + getNumerator()) + getDenominator();
384        }
385        
386        /**
387         * Gets the fraction as an <tt>int</tt>. This returns the whole number part
388         * of the fraction.
389         * @return the whole number fraction part
390         */
391        @Override
392        public int intValue() {
393            return (int)doubleValue();
394        }
395        
396        /**
397         * Gets the fraction as a <tt>long</tt>. This returns the whole number part
398         * of the fraction.
399         * @return the whole number fraction part
400         */
401        @Override
402        public long longValue() {
403            return (long)doubleValue();
404        }
405        
406        /**
407         * Return the additive inverse of this fraction.
408         * @return the negation of this fraction.
409         */
410        public Fraction negate() {
411            if (numerator==Integer.MIN_VALUE) {
412                throw MathRuntimeException.createArithmeticException("overflow in fraction {0}/{1}, cannot negate",
413                                                                     numerator, denominator);
414            }
415            return new Fraction(-numerator, denominator);
416        }
417    
418        /**
419         * Return the multiplicative inverse of this fraction.
420         * @return the reciprocal fraction
421         */
422        public Fraction reciprocal() {
423            return new Fraction(denominator, numerator);
424        }
425        
426        /**
427         * <p>Adds the value of this fraction to another, returning the result in reduced form.
428         * The algorithm follows Knuth, 4.5.1.</p>
429         *
430         * @param fraction  the fraction to add, must not be <code>null</code>
431         * @return a <code>Fraction</code> instance with the resulting values
432         * @throws IllegalArgumentException if the fraction is <code>null</code>
433         * @throws ArithmeticException if the resulting numerator or denominator exceeds
434         *  <code>Integer.MAX_VALUE</code>
435         */
436        public Fraction add(Fraction fraction) {
437            return addSub(fraction, true /* add */);
438        }
439    
440        /**
441         * Add an integer to the fraction.
442         * @param i the <tt>integer</tt> to add.
443         * @return this + i
444         */
445        public Fraction add(final int i) {
446            return new Fraction(numerator + i * denominator, denominator);
447        }
448    
449        /**
450         * <p>Subtracts the value of another fraction from the value of this one, 
451         * returning the result in reduced form.</p>
452         *
453         * @param fraction  the fraction to subtract, must not be <code>null</code>
454         * @return a <code>Fraction</code> instance with the resulting values
455         * @throws IllegalArgumentException if the fraction is <code>null</code>
456         * @throws ArithmeticException if the resulting numerator or denominator
457         *   cannot be represented in an <code>int</code>.
458         */
459        public Fraction subtract(Fraction fraction) {
460            return addSub(fraction, false /* subtract */);
461        }
462    
463        /**
464         * Subtract an integer from the fraction.
465         * @param i the <tt>integer</tt> to subtract.
466         * @return this - i
467         */
468        public Fraction subtract(final int i) {
469            return new Fraction(numerator - i * denominator, denominator);
470        }
471    
472        /** 
473         * Implement add and subtract using algorithm described in Knuth 4.5.1.
474         * 
475         * @param fraction the fraction to subtract, must not be <code>null</code>
476         * @param isAdd true to add, false to subtract
477         * @return a <code>Fraction</code> instance with the resulting values
478         * @throws IllegalArgumentException if the fraction is <code>null</code>
479         * @throws ArithmeticException if the resulting numerator or denominator
480         *   cannot be represented in an <code>int</code>.
481         */
482        private Fraction addSub(Fraction fraction, boolean isAdd) {
483            if (fraction == null) {
484                throw MathRuntimeException.createIllegalArgumentException("null fraction");
485            }
486            // zero is identity for addition.
487            if (numerator == 0) {
488                return isAdd ? fraction : fraction.negate();
489            }
490            if (fraction.numerator == 0) {
491                return this;
492            }     
493            // if denominators are randomly distributed, d1 will be 1 about 61%
494            // of the time.
495            int d1 = MathUtils.gcd(denominator, fraction.denominator);
496            if (d1==1) {
497                // result is ( (u*v' +/- u'v) / u'v')
498                int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
499                int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
500                return new Fraction
501                    (isAdd ? MathUtils.addAndCheck(uvp, upv) : 
502                     MathUtils.subAndCheck(uvp, upv),
503                     MathUtils.mulAndCheck(denominator, fraction.denominator));
504            }
505            // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
506            // exercise 7.  we're going to use a BigInteger.
507            // t = u(v'/d1) +/- v(u'/d1)
508            BigInteger uvp = BigInteger.valueOf(numerator)
509            .multiply(BigInteger.valueOf(fraction.denominator/d1));
510            BigInteger upv = BigInteger.valueOf(fraction.numerator)
511            .multiply(BigInteger.valueOf(denominator/d1));
512            BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
513            // but d2 doesn't need extra precision because
514            // d2 = gcd(t,d1) = gcd(t mod d1, d1)
515            int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
516            int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1);
517    
518            // result is (t/d2) / (u'/d1)(v'/d2)
519            BigInteger w = t.divide(BigInteger.valueOf(d2));
520            if (w.bitLength() > 31) {
521                throw MathRuntimeException.createArithmeticException("overflow, numerator too large after multiply: {0}",
522                                                                     w);
523            }
524            return new Fraction (w.intValue(), 
525                    MathUtils.mulAndCheck(denominator/d1, 
526                            fraction.denominator/d2));
527        }
528    
529        /**
530         * <p>Multiplies the value of this fraction by another, returning the 
531         * result in reduced form.</p>
532         *
533         * @param fraction  the fraction to multiply by, must not be <code>null</code>
534         * @return a <code>Fraction</code> instance with the resulting values
535         * @throws IllegalArgumentException if the fraction is <code>null</code>
536         * @throws ArithmeticException if the resulting numerator or denominator exceeds
537         *  <code>Integer.MAX_VALUE</code>
538         */
539        public Fraction multiply(Fraction fraction) {
540            if (fraction == null) {
541                throw MathRuntimeException.createIllegalArgumentException("null fraction");
542            }
543            if (numerator == 0 || fraction.numerator == 0) {
544                return ZERO;
545            }
546            // knuth 4.5.1
547            // make sure we don't overflow unless the result *must* overflow.
548            int d1 = MathUtils.gcd(numerator, fraction.denominator);
549            int d2 = MathUtils.gcd(fraction.numerator, denominator);
550            return getReducedFraction
551            (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
552                    MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
553        }
554    
555        /**
556         * Multiply the fraction by an integer.
557         * @param i the <tt>integer</tt> to multiply by.
558         * @return this * i
559         */
560        public Fraction multiply(final int i) {
561            return new Fraction(numerator * i, denominator);
562        }
563    
564        /**
565         * <p>Divide the value of this fraction by another.</p>
566         *
567         * @param fraction  the fraction to divide by, must not be <code>null</code>
568         * @return a <code>Fraction</code> instance with the resulting values
569         * @throws IllegalArgumentException if the fraction is <code>null</code>
570         * @throws ArithmeticException if the fraction to divide by is zero
571         * @throws ArithmeticException if the resulting numerator or denominator exceeds
572         *  <code>Integer.MAX_VALUE</code>
573         */
574        public Fraction divide(Fraction fraction) {
575            if (fraction == null) {
576                throw MathRuntimeException.createIllegalArgumentException("null fraction");
577            }
578            if (fraction.numerator == 0) {
579                throw MathRuntimeException.createArithmeticException(
580                        "the fraction to divide by must not be zero: {0}/{1}",
581                        fraction.numerator, fraction.denominator);
582            }
583            return multiply(fraction.reciprocal());
584        }
585    
586        /**
587         * Divide the fraction by an integer.
588         * @param i the <tt>integer</tt> to divide by.
589         * @return this * i
590         */
591        public Fraction divide(final int i) {
592            return new Fraction(numerator, denominator * i);
593        }
594    
595        /**
596         * <p>Creates a <code>Fraction</code> instance with the 2 parts
597         * of a fraction Y/Z.</p>
598         *
599         * <p>Any negative signs are resolved to be on the numerator.</p>
600         *
601         * @param numerator  the numerator, for example the three in 'three sevenths'
602         * @param denominator  the denominator, for example the seven in 'three sevenths'
603         * @return a new fraction instance, with the numerator and denominator reduced
604         * @throws ArithmeticException if the denominator is <code>zero</code>
605         */
606        public static Fraction getReducedFraction(int numerator, int denominator) {
607            if (denominator == 0) {
608                throw MathRuntimeException.createArithmeticException(
609                        "zero denominator in fraction {0}/{1}",
610                        numerator, denominator);
611            }
612            if (numerator==0) {
613                return ZERO; // normalize zero.
614            }
615            // allow 2^k/-2^31 as a valid fraction (where k>0)
616            if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
617                numerator/=2; denominator/=2;
618            }
619            if (denominator < 0) {
620                if (numerator==Integer.MIN_VALUE ||
621                        denominator==Integer.MIN_VALUE) {
622                    throw MathRuntimeException.createArithmeticException(
623                            "overflow in fraction {0}/{1}, cannot negate",
624                            numerator, denominator);
625                }
626                numerator = -numerator;
627                denominator = -denominator;
628            }
629            // simplify fraction.
630            int gcd = MathUtils.gcd(numerator, denominator);
631            numerator /= gcd;
632            denominator /= gcd;
633            return new Fraction(numerator, denominator);
634        }
635    
636        /**
637         * <p>
638         * Returns the <code>String</code> representing this fraction, ie
639         * "num / dem" or just "num" if the denominator is one.
640         * </p>
641         * 
642         * @return a string representation of the fraction.
643         * @see java.lang.Object#toString()
644         */
645        @Override
646        public String toString() {
647            String str = null;
648            if (denominator == 1) {
649                str = Integer.toString(numerator);
650            } else if (numerator == 0) {
651                str = "0";
652            } else {
653                str = numerator + " / " + denominator;
654            }
655            return str;
656        }
657    
658        /** {@inheritDoc} */
659        public FractionField getField() {
660            return FractionField.getInstance();
661        }
662    
663    }