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