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