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