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 */
017package org.apache.commons.math3.fraction;
018
019import java.io.Serializable;
020import java.math.BigInteger;
021
022import org.apache.commons.math3.FieldElement;
023import org.apache.commons.math3.exception.util.LocalizedFormats;
024import org.apache.commons.math3.exception.MathArithmeticException;
025import org.apache.commons.math3.exception.NullArgumentException;
026import org.apache.commons.math3.util.ArithmeticUtils;
027import org.apache.commons.math3.util.FastMath;
028
029/**
030 * Representation of a rational number.
031 *
032 * implements Serializable since 2.0
033 *
034 * @since 1.1
035 * @version $Id: Fraction.java 1519204 2013-08-31 19:43:02Z tn $
036 */
037public class Fraction
038    extends Number
039    implements FieldElement<Fraction>, Comparable<Fraction>, Serializable {
040
041    /** A fraction representing "2 / 1". */
042    public static final Fraction TWO = new Fraction(2, 1);
043
044    /** A fraction representing "1". */
045    public static final Fraction ONE = new Fraction(1, 1);
046
047    /** A fraction representing "0". */
048    public static final Fraction ZERO = new Fraction(0, 1);
049
050    /** A fraction representing "4/5". */
051    public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
052
053    /** A fraction representing "1/5". */
054    public static final Fraction ONE_FIFTH = new Fraction(1, 5);
055
056    /** A fraction representing "1/2". */
057    public static final Fraction ONE_HALF = new Fraction(1, 2);
058
059    /** A fraction representing "1/4". */
060    public static final Fraction ONE_QUARTER = new Fraction(1, 4);
061
062    /** A fraction representing "1/3". */
063    public static final Fraction ONE_THIRD = new Fraction(1, 3);
064
065    /** A fraction representing "3/5". */
066    public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
067
068    /** A fraction representing "3/4". */
069    public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
070
071    /** A fraction representing "2/5". */
072    public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
073
074    /** A fraction representing "2/4". */
075    public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
076
077    /** A fraction representing "2/3". */
078    public static final Fraction TWO_THIRDS = new Fraction(2, 3);
079
080    /** A fraction representing "-1 / 1". */
081    public static final Fraction MINUS_ONE = new Fraction(-1, 1);
082
083    /** Serializable version identifier */
084    private static final long serialVersionUID = 3698073679419233275L;
085
086    /** The default epsilon used for convergence. */
087    private static final double DEFAULT_EPSILON = 1e-5;
088
089    /** The denominator. */
090    private final int denominator;
091
092    /** The numerator. */
093    private final int numerator;
094
095    /**
096     * Create a fraction given the double value.
097     * @param value the double value to convert to a fraction.
098     * @throws FractionConversionException if the continued fraction failed to
099     *         converge.
100     */
101    public Fraction(double value) throws FractionConversionException {
102        this(value, DEFAULT_EPSILON, 100);
103    }
104
105    /**
106     * Create a fraction given the double value and maximum error allowed.
107     * <p>
108     * References:
109     * <ul>
110     * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
111     * Continued Fraction</a> equations (11) and (22)-(26)</li>
112     * </ul>
113     * </p>
114     * @param value the double value to convert to a fraction.
115     * @param epsilon maximum error allowed.  The resulting fraction is within
116     *        {@code epsilon} of {@code value}, in absolute terms.
117     * @param maxIterations maximum number of convergents
118     * @throws FractionConversionException if the continued fraction failed to
119     *         converge.
120     */
121    public Fraction(double value, double epsilon, int maxIterations)
122        throws FractionConversionException
123    {
124        this(value, epsilon, Integer.MAX_VALUE, maxIterations);
125    }
126
127    /**
128     * Create a fraction given the double value and maximum denominator.
129     * <p>
130     * References:
131     * <ul>
132     * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
133     * Continued Fraction</a> equations (11) and (22)-(26)</li>
134     * </ul>
135     * </p>
136     * @param value the double value to convert to a fraction.
137     * @param maxDenominator The maximum allowed value for denominator
138     * @throws FractionConversionException if the continued fraction failed to
139     *         converge
140     */
141    public Fraction(double value, int maxDenominator)
142        throws FractionConversionException
143    {
144       this(value, 0, maxDenominator, 100);
145    }
146
147    /**
148     * Create a fraction given the double value and either the maximum error
149     * allowed or the maximum number of denominator digits.
150     * <p>
151     *
152     * NOTE: This constructor is called with EITHER
153     *   - a valid epsilon value and the maxDenominator set to Integer.MAX_VALUE
154     *     (that way the maxDenominator has no effect).
155     * OR
156     *   - a valid maxDenominator value and the epsilon value set to zero
157     *     (that way epsilon only has effect if there is an exact match before
158     *     the maxDenominator value is reached).
159     * </p><p>
160     *
161     * It has been done this way so that the same code can be (re)used for both
162     * scenarios. However this could be confusing to users if it were part of
163     * the public API and this constructor should therefore remain PRIVATE.
164     * </p>
165     *
166     * See JIRA issue ticket MATH-181 for more details:
167     *
168     *     https://issues.apache.org/jira/browse/MATH-181
169     *
170     * @param value the double value to convert to a fraction.
171     * @param epsilon maximum error allowed.  The resulting fraction is within
172     *        {@code epsilon} of {@code value}, in absolute terms.
173     * @param maxDenominator maximum denominator value allowed.
174     * @param maxIterations maximum number of convergents
175     * @throws FractionConversionException if the continued fraction failed to
176     *         converge.
177     */
178    private Fraction(double value, double epsilon, int maxDenominator, int maxIterations)
179        throws FractionConversionException
180    {
181        long overflow = Integer.MAX_VALUE;
182        double r0 = value;
183        long a0 = (long)FastMath.floor(r0);
184        if (FastMath.abs(a0) > overflow) {
185            throw new FractionConversionException(value, a0, 1l);
186        }
187
188        // check for (almost) integer arguments, which should not go to iterations.
189        if (FastMath.abs(a0 - value) < epsilon) {
190            this.numerator = (int) a0;
191            this.denominator = 1;
192            return;
193        }
194
195        long p0 = 1;
196        long q0 = 0;
197        long p1 = a0;
198        long q1 = 1;
199
200        long p2 = 0;
201        long q2 = 1;
202
203        int n = 0;
204        boolean stop = false;
205        do {
206            ++n;
207            double r1 = 1.0 / (r0 - a0);
208            long a1 = (long)FastMath.floor(r1);
209            p2 = (a1 * p1) + p0;
210            q2 = (a1 * q1) + q0;
211
212            if ((FastMath.abs(p2) > overflow) || (FastMath.abs(q2) > overflow)) {
213                // in maxDenominator mode, if the last fraction was very close to the actual value
214                // q2 may overflow in the next iteration; in this case return the last one.
215                if (epsilon == 0.0 && FastMath.abs(q1) < maxDenominator) {
216                    break;
217                }
218                throw new FractionConversionException(value, p2, q2);
219            }
220
221            double convergent = (double)p2 / (double)q2;
222            if (n < maxIterations && FastMath.abs(convergent - value) > epsilon && q2 < maxDenominator) {
223                p0 = p1;
224                p1 = p2;
225                q0 = q1;
226                q1 = q2;
227                a0 = a1;
228                r0 = r1;
229            } else {
230                stop = true;
231            }
232        } while (!stop);
233
234        if (n >= maxIterations) {
235            throw new FractionConversionException(value, maxIterations);
236        }
237
238        if (q2 < maxDenominator) {
239            this.numerator = (int) p2;
240            this.denominator = (int) q2;
241        } else {
242            this.numerator = (int) p1;
243            this.denominator = (int) q1;
244        }
245
246    }
247
248    /**
249     * Create a fraction from an int.
250     * The fraction is num / 1.
251     * @param num the numerator.
252     */
253    public Fraction(int num) {
254        this(num, 1);
255    }
256
257    /**
258     * Create a fraction given the numerator and denominator.  The fraction is
259     * reduced to lowest terms.
260     * @param num the numerator.
261     * @param den the denominator.
262     * @throws MathArithmeticException if the denominator is {@code zero}
263     */
264    public Fraction(int num, int den) {
265        if (den == 0) {
266            throw new MathArithmeticException(LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION,
267                                              num, den);
268        }
269        if (den < 0) {
270            if (num == Integer.MIN_VALUE ||
271                den == Integer.MIN_VALUE) {
272                throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_FRACTION,
273                                                  num, den);
274            }
275            num = -num;
276            den = -den;
277        }
278        // reduce numerator and denominator by greatest common denominator.
279        final int d = ArithmeticUtils.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 new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_FRACTION, numerator, denominator);
416        }
417        return new Fraction(-numerator, denominator);
418    }
419
420    /**
421     * Return the multiplicative inverse of this fraction.
422     * @return the reciprocal fraction
423     */
424    public Fraction reciprocal() {
425        return new Fraction(denominator, numerator);
426    }
427
428    /**
429     * <p>Adds the value of this fraction to another, returning the result in reduced form.
430     * The algorithm follows Knuth, 4.5.1.</p>
431     *
432     * @param fraction  the fraction to add, must not be {@code null}
433     * @return a {@code Fraction} instance with the resulting values
434     * @throws NullArgumentException if the fraction is {@code null}
435     * @throws MathArithmeticException if the resulting numerator or denominator exceeds
436     *  {@code Integer.MAX_VALUE}
437     */
438    public Fraction add(Fraction fraction) {
439        return addSub(fraction, true /* add */);
440    }
441
442    /**
443     * Add an integer to the fraction.
444     * @param i the <tt>integer</tt> to add.
445     * @return this + i
446     */
447    public Fraction add(final int i) {
448        return new Fraction(numerator + i * denominator, denominator);
449    }
450
451    /**
452     * <p>Subtracts the value of another fraction from the value of this one,
453     * returning the result in reduced form.</p>
454     *
455     * @param fraction  the fraction to subtract, must not be {@code null}
456     * @return a {@code Fraction} instance with the resulting values
457     * @throws NullArgumentException if the fraction is {@code null}
458     * @throws MathArithmeticException if the resulting numerator or denominator
459     *   cannot be represented in an {@code int}.
460     */
461    public Fraction subtract(Fraction fraction) {
462        return addSub(fraction, false /* subtract */);
463    }
464
465    /**
466     * Subtract an integer from the fraction.
467     * @param i the <tt>integer</tt> to subtract.
468     * @return this - i
469     */
470    public Fraction subtract(final int i) {
471        return new Fraction(numerator - i * denominator, denominator);
472    }
473
474    /**
475     * Implement add and subtract using algorithm described in Knuth 4.5.1.
476     *
477     * @param fraction the fraction to subtract, must not be {@code null}
478     * @param isAdd true to add, false to subtract
479     * @return a {@code Fraction} instance with the resulting values
480     * @throws NullArgumentException if the fraction is {@code null}
481     * @throws MathArithmeticException if the resulting numerator or denominator
482     *   cannot be represented in an {@code int}.
483     */
484    private Fraction addSub(Fraction fraction, boolean isAdd) {
485        if (fraction == null) {
486            throw new NullArgumentException(LocalizedFormats.FRACTION);
487        }
488        // zero is identity for addition.
489        if (numerator == 0) {
490            return isAdd ? fraction : fraction.negate();
491        }
492        if (fraction.numerator == 0) {
493            return this;
494        }
495        // if denominators are randomly distributed, d1 will be 1 about 61%
496        // of the time.
497        int d1 = ArithmeticUtils.gcd(denominator, fraction.denominator);
498        if (d1==1) {
499            // result is ( (u*v' +/- u'v) / u'v')
500            int uvp = ArithmeticUtils.mulAndCheck(numerator, fraction.denominator);
501            int upv = ArithmeticUtils.mulAndCheck(fraction.numerator, denominator);
502            return new Fraction
503                (isAdd ? ArithmeticUtils.addAndCheck(uvp, upv) :
504                 ArithmeticUtils.subAndCheck(uvp, upv),
505                 ArithmeticUtils.mulAndCheck(denominator, fraction.denominator));
506        }
507        // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
508        // exercise 7.  we're going to use a BigInteger.
509        // t = u(v'/d1) +/- v(u'/d1)
510        BigInteger uvp = BigInteger.valueOf(numerator)
511        .multiply(BigInteger.valueOf(fraction.denominator/d1));
512        BigInteger upv = BigInteger.valueOf(fraction.numerator)
513        .multiply(BigInteger.valueOf(denominator/d1));
514        BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
515        // but d2 doesn't need extra precision because
516        // d2 = gcd(t,d1) = gcd(t mod d1, d1)
517        int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
518        int d2 = (tmodd1==0)?d1:ArithmeticUtils.gcd(tmodd1, d1);
519
520        // result is (t/d2) / (u'/d1)(v'/d2)
521        BigInteger w = t.divide(BigInteger.valueOf(d2));
522        if (w.bitLength() > 31) {
523            throw new MathArithmeticException(LocalizedFormats.NUMERATOR_OVERFLOW_AFTER_MULTIPLY,
524                                              w);
525        }
526        return new Fraction (w.intValue(),
527                ArithmeticUtils.mulAndCheck(denominator/d1,
528                        fraction.denominator/d2));
529    }
530
531    /**
532     * <p>Multiplies the value of this fraction by another, returning the
533     * result in reduced form.</p>
534     *
535     * @param fraction  the fraction to multiply by, must not be {@code null}
536     * @return a {@code Fraction} instance with the resulting values
537     * @throws NullArgumentException if the fraction is {@code null}
538     * @throws MathArithmeticException if the resulting numerator or denominator exceeds
539     *  {@code Integer.MAX_VALUE}
540     */
541    public Fraction multiply(Fraction fraction) {
542        if (fraction == null) {
543            throw new NullArgumentException(LocalizedFormats.FRACTION);
544        }
545        if (numerator == 0 || fraction.numerator == 0) {
546            return ZERO;
547        }
548        // knuth 4.5.1
549        // make sure we don't overflow unless the result *must* overflow.
550        int d1 = ArithmeticUtils.gcd(numerator, fraction.denominator);
551        int d2 = ArithmeticUtils.gcd(fraction.numerator, denominator);
552        return getReducedFraction
553        (ArithmeticUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
554                ArithmeticUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
555    }
556
557    /**
558     * Multiply the fraction by an integer.
559     * @param i the <tt>integer</tt> to multiply by.
560     * @return this * i
561     */
562    public Fraction multiply(final int i) {
563        return new Fraction(numerator * i, denominator);
564    }
565
566    /**
567     * <p>Divide the value of this fraction by another.</p>
568     *
569     * @param fraction  the fraction to divide by, must not be {@code null}
570     * @return a {@code Fraction} instance with the resulting values
571     * @throws IllegalArgumentException if the fraction is {@code null}
572     * @throws MathArithmeticException if the fraction to divide by is zero
573     * @throws MathArithmeticException if the resulting numerator or denominator exceeds
574     *  {@code Integer.MAX_VALUE}
575     */
576    public Fraction divide(Fraction fraction) {
577        if (fraction == null) {
578            throw new NullArgumentException(LocalizedFormats.FRACTION);
579        }
580        if (fraction.numerator == 0) {
581            throw new MathArithmeticException(LocalizedFormats.ZERO_FRACTION_TO_DIVIDE_BY,
582                                              fraction.numerator, fraction.denominator);
583        }
584        return multiply(fraction.reciprocal());
585    }
586
587    /**
588     * Divide the fraction by an integer.
589     * @param i the <tt>integer</tt> to divide by.
590     * @return this * i
591     */
592    public Fraction divide(final int i) {
593        return new Fraction(numerator, denominator * i);
594    }
595
596    /**
597     * <p>
598     * Gets the fraction percentage as a <tt>double</tt>. This calculates the
599     * fraction as the numerator divided by denominator multiplied by 100.
600     * </p>
601     *
602     * @return the fraction percentage as a <tt>double</tt>.
603     */
604    public double percentageValue() {
605        return 100 * doubleValue();
606    }
607
608    /**
609     * <p>Creates a {@code Fraction} instance with the 2 parts
610     * of a fraction Y/Z.</p>
611     *
612     * <p>Any negative signs are resolved to be on the numerator.</p>
613     *
614     * @param numerator  the numerator, for example the three in 'three sevenths'
615     * @param denominator  the denominator, for example the seven in 'three sevenths'
616     * @return a new fraction instance, with the numerator and denominator reduced
617     * @throws MathArithmeticException if the denominator is {@code zero}
618     */
619    public static Fraction getReducedFraction(int numerator, int denominator) {
620        if (denominator == 0) {
621            throw new MathArithmeticException(LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION,
622                                              numerator, denominator);
623        }
624        if (numerator==0) {
625            return ZERO; // normalize zero.
626        }
627        // allow 2^k/-2^31 as a valid fraction (where k>0)
628        if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
629            numerator/=2; denominator/=2;
630        }
631        if (denominator < 0) {
632            if (numerator==Integer.MIN_VALUE ||
633                    denominator==Integer.MIN_VALUE) {
634                throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_FRACTION,
635                                                  numerator, denominator);
636            }
637            numerator = -numerator;
638            denominator = -denominator;
639        }
640        // simplify fraction.
641        int gcd = ArithmeticUtils.gcd(numerator, denominator);
642        numerator /= gcd;
643        denominator /= gcd;
644        return new Fraction(numerator, denominator);
645    }
646
647    /**
648     * <p>
649     * Returns the {@code String} representing this fraction, ie
650     * "num / dem" or just "num" if the denominator is one.
651     * </p>
652     *
653     * @return a string representation of the fraction.
654     * @see java.lang.Object#toString()
655     */
656    @Override
657    public String toString() {
658        String str = null;
659        if (denominator == 1) {
660            str = Integer.toString(numerator);
661        } else if (numerator == 0) {
662            str = "0";
663        } else {
664            str = numerator + " / " + denominator;
665        }
666        return str;
667    }
668
669    /** {@inheritDoc} */
670    public FractionField getField() {
671        return FractionField.getInstance();
672    }
673
674}