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.lang3.math;
018
019import java.math.BigInteger;
020
021import org.apache.commons.lang3.Validate;
022
023/**
024 * <p><code>Fraction</code> is a <code>Number</code> implementation that
025 * stores fractions accurately.</p>
026 *
027 * <p>This class is immutable, and interoperable with most methods that accept
028 * a <code>Number</code>.</p>
029 *
030 * <p>Note that this class is intended for common use cases, it is <i>int</i>
031 * based and thus suffers from various overflow issues. For a BigInteger based
032 * equivalent, please see the Commons Math BigFraction class. </p>
033 *
034 * @since 2.0
035 */
036public final class Fraction extends Number implements Comparable<Fraction> {
037
038    /**
039     * Required for serialization support. Lang version 2.0.
040     *
041     * @see java.io.Serializable
042     */
043    private static final long serialVersionUID = 65382027393090L;
044
045    /**
046     * <code>Fraction</code> representation of 0.
047     */
048    public static final Fraction ZERO = new Fraction(0, 1);
049    /**
050     * <code>Fraction</code> representation of 1.
051     */
052    public static final Fraction ONE = new Fraction(1, 1);
053    /**
054     * <code>Fraction</code> representation of 1/2.
055     */
056    public static final Fraction ONE_HALF = new Fraction(1, 2);
057    /**
058     * <code>Fraction</code> representation of 1/3.
059     */
060    public static final Fraction ONE_THIRD = new Fraction(1, 3);
061    /**
062     * <code>Fraction</code> representation of 2/3.
063     */
064    public static final Fraction TWO_THIRDS = new Fraction(2, 3);
065    /**
066     * <code>Fraction</code> representation of 1/4.
067     */
068    public static final Fraction ONE_QUARTER = new Fraction(1, 4);
069    /**
070     * <code>Fraction</code> representation of 2/4.
071     */
072    public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
073    /**
074     * <code>Fraction</code> representation of 3/4.
075     */
076    public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
077    /**
078     * <code>Fraction</code> representation of 1/5.
079     */
080    public static final Fraction ONE_FIFTH = new Fraction(1, 5);
081    /**
082     * <code>Fraction</code> representation of 2/5.
083     */
084    public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
085    /**
086     * <code>Fraction</code> representation of 3/5.
087     */
088    public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
089    /**
090     * <code>Fraction</code> representation of 4/5.
091     */
092    public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
093
094
095    /**
096     * The numerator number part of the fraction (the three in three sevenths).
097     */
098    private final int numerator;
099    /**
100     * The denominator number part of the fraction (the seven in three sevenths).
101     */
102    private final int denominator;
103
104    /**
105     * Cached output hashCode (class is immutable).
106     */
107    private transient int hashCode = 0;
108    /**
109     * Cached output toString (class is immutable).
110     */
111    private transient String toString = null;
112    /**
113     * Cached output toProperString (class is immutable).
114     */
115    private transient String toProperString = null;
116
117    /**
118     * <p>Constructs a <code>Fraction</code> instance with the 2 parts
119     * of a fraction Y/Z.</p>
120     *
121     * @param numerator  the numerator, for example the three in 'three sevenths'
122     * @param denominator  the denominator, for example the seven in 'three sevenths'
123     */
124    private Fraction(final int numerator, final int denominator) {
125        super();
126        this.numerator = numerator;
127        this.denominator = denominator;
128    }
129
130    /**
131     * <p>Creates a <code>Fraction</code> instance with the 2 parts
132     * of a fraction Y/Z.</p>
133     *
134     * <p>Any negative signs are resolved to be on the numerator.</p>
135     *
136     * @param numerator  the numerator, for example the three in 'three sevenths'
137     * @param denominator  the denominator, for example the seven in 'three sevenths'
138     * @return a new fraction instance
139     * @throws ArithmeticException if the denominator is <code>zero</code>
140     * or the denominator is {@code negative} and the numerator is {@code Integer#MIN_VALUE}
141     */
142    public static Fraction getFraction(int numerator, int denominator) {
143        if (denominator == 0) {
144            throw new ArithmeticException("The denominator must not be zero");
145        }
146        if (denominator < 0) {
147            if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) {
148                throw new ArithmeticException("overflow: can't negate");
149            }
150            numerator = -numerator;
151            denominator = -denominator;
152        }
153        return new Fraction(numerator, denominator);
154    }
155
156    /**
157     * <p>Creates a <code>Fraction</code> instance with the 3 parts
158     * of a fraction X Y/Z.</p>
159     *
160     * <p>The negative sign must be passed in on the whole number part.</p>
161     *
162     * @param whole  the whole number, for example the one in 'one and three sevenths'
163     * @param numerator  the numerator, for example the three in 'one and three sevenths'
164     * @param denominator  the denominator, for example the seven in 'one and three sevenths'
165     * @return a new fraction instance
166     * @throws ArithmeticException if the denominator is <code>zero</code>
167     * @throws ArithmeticException if the denominator is negative
168     * @throws ArithmeticException if the numerator is negative
169     * @throws ArithmeticException if the resulting numerator exceeds
170     *  <code>Integer.MAX_VALUE</code>
171     */
172    public static Fraction getFraction(final int whole, final int numerator, final int denominator) {
173        if (denominator == 0) {
174            throw new ArithmeticException("The denominator must not be zero");
175        }
176        if (denominator < 0) {
177            throw new ArithmeticException("The denominator must not be negative");
178        }
179        if (numerator < 0) {
180            throw new ArithmeticException("The numerator must not be negative");
181        }
182        long numeratorValue;
183        if (whole < 0) {
184            numeratorValue = whole * (long) denominator - numerator;
185        } else {
186            numeratorValue = whole * (long) denominator + numerator;
187        }
188        if (numeratorValue < Integer.MIN_VALUE || numeratorValue > Integer.MAX_VALUE) {
189            throw new ArithmeticException("Numerator too large to represent as an Integer.");
190        }
191        return new Fraction((int) numeratorValue, denominator);
192    }
193
194    /**
195     * <p>Creates a reduced <code>Fraction</code> instance with the 2 parts
196     * of a fraction Y/Z.</p>
197     *
198     * <p>For example, if the input parameters represent 2/4, then the created
199     * fraction will be 1/2.</p>
200     *
201     * <p>Any negative signs are resolved to be on the numerator.</p>
202     *
203     * @param numerator  the numerator, for example the three in 'three sevenths'
204     * @param denominator  the denominator, for example the seven in 'three sevenths'
205     * @return a new fraction instance, with the numerator and denominator reduced
206     * @throws ArithmeticException if the denominator is <code>zero</code>
207     */
208    public static Fraction getReducedFraction(int numerator, int denominator) {
209        if (denominator == 0) {
210            throw new ArithmeticException("The denominator must not be zero");
211        }
212        if (numerator == 0) {
213            return ZERO; // normalize zero.
214        }
215        // allow 2^k/-2^31 as a valid fraction (where k>0)
216        if (denominator == Integer.MIN_VALUE && (numerator & 1) == 0) {
217            numerator /= 2;
218            denominator /= 2;
219        }
220        if (denominator < 0) {
221            if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) {
222                throw new ArithmeticException("overflow: can't negate");
223            }
224            numerator = -numerator;
225            denominator = -denominator;
226        }
227        // simplify fraction.
228        final int gcd = greatestCommonDivisor(numerator, denominator);
229        numerator /= gcd;
230        denominator /= gcd;
231        return new Fraction(numerator, denominator);
232    }
233
234    /**
235     * <p>Creates a <code>Fraction</code> instance from a <code>double</code> value.</p>
236     *
237     * <p>This method uses the <a href="http://archives.math.utk.edu/articles/atuyl/confrac/">
238     *  continued fraction algorithm</a>, computing a maximum of
239     *  25 convergents and bounding the denominator by 10,000.</p>
240     *
241     * @param value  the double value to convert
242     * @return a new fraction instance that is close to the value
243     * @throws ArithmeticException if <code>|value| &gt; Integer.MAX_VALUE</code>
244     *  or <code>value = NaN</code>
245     * @throws ArithmeticException if the calculated denominator is <code>zero</code>
246     * @throws ArithmeticException if the algorithm does not converge
247     */
248    public static Fraction getFraction(double value) {
249        final int sign = value < 0 ? -1 : 1;
250        value = Math.abs(value);
251        if (value > Integer.MAX_VALUE || Double.isNaN(value)) {
252            throw new ArithmeticException("The value must not be greater than Integer.MAX_VALUE or NaN");
253        }
254        final int wholeNumber = (int) value;
255        value -= wholeNumber;
256
257        int numer0 = 0; // the pre-previous
258        int denom0 = 1; // the pre-previous
259        int numer1 = 1; // the previous
260        int denom1 = 0; // the previous
261        int numer2 = 0; // the current, setup in calculation
262        int denom2 = 0; // the current, setup in calculation
263        int a1 = (int) value;
264        int a2 = 0;
265        double x1 = 1;
266        double x2 = 0;
267        double y1 = value - a1;
268        double y2 = 0;
269        double delta1, delta2 = Double.MAX_VALUE;
270        double fraction;
271        int i = 1;
272        do {
273            delta1 = delta2;
274            a2 = (int) (x1 / y1);
275            x2 = y1;
276            y2 = x1 - a2 * y1;
277            numer2 = a1 * numer1 + numer0;
278            denom2 = a1 * denom1 + denom0;
279            fraction = (double) numer2 / (double) denom2;
280            delta2 = Math.abs(value - fraction);
281            a1 = a2;
282            x1 = x2;
283            y1 = y2;
284            numer0 = numer1;
285            denom0 = denom1;
286            numer1 = numer2;
287            denom1 = denom2;
288            i++;
289        } while (delta1 > delta2 && denom2 <= 10000 && denom2 > 0 && i < 25);
290        if (i == 25) {
291            throw new ArithmeticException("Unable to convert double to fraction");
292        }
293        return getReducedFraction((numer0 + wholeNumber * denom0) * sign, denom0);
294    }
295
296    /**
297     * <p>Creates a Fraction from a <code>String</code>.</p>
298     *
299     * <p>The formats accepted are:</p>
300     *
301     * <ol>
302     *  <li><code>double</code> String containing a dot</li>
303     *  <li>'X Y/Z'</li>
304     *  <li>'Y/Z'</li>
305     *  <li>'X' (a simple whole number)</li>
306     * </ol>
307     * <p>and a .</p>
308     *
309     * @param str  the string to parse, must not be <code>null</code>
310     * @return the new <code>Fraction</code> instance
311     * @throws IllegalArgumentException if the string is <code>null</code>
312     * @throws NumberFormatException if the number format is invalid
313     */
314    public static Fraction getFraction(String str) {
315        Validate.isTrue(str != null, "The string must not be null");
316        // parse double format
317        int pos = str.indexOf('.');
318        if (pos >= 0) {
319            return getFraction(Double.parseDouble(str));
320        }
321
322        // parse X Y/Z format
323        pos = str.indexOf(' ');
324        if (pos > 0) {
325            final int whole = Integer.parseInt(str.substring(0, pos));
326            str = str.substring(pos + 1);
327            pos = str.indexOf('/');
328            if (pos < 0) {
329                throw new NumberFormatException("The fraction could not be parsed as the format X Y/Z");
330            }
331            final int numer = Integer.parseInt(str.substring(0, pos));
332            final int denom = Integer.parseInt(str.substring(pos + 1));
333            return getFraction(whole, numer, denom);
334        }
335
336        // parse Y/Z format
337        pos = str.indexOf('/');
338        if (pos < 0) {
339            // simple whole number
340            return getFraction(Integer.parseInt(str), 1);
341        }
342        final int numer = Integer.parseInt(str.substring(0, pos));
343        final int denom = Integer.parseInt(str.substring(pos + 1));
344        return getFraction(numer, denom);
345    }
346
347    // Accessors
348    //-------------------------------------------------------------------
349
350    /**
351     * <p>Gets the numerator part of the fraction.</p>
352     *
353     * <p>This method may return a value greater than the denominator, an
354     * improper fraction, such as the seven in 7/4.</p>
355     *
356     * @return the numerator fraction part
357     */
358    public int getNumerator() {
359        return numerator;
360    }
361
362    /**
363     * <p>Gets the denominator part of the fraction.</p>
364     *
365     * @return the denominator fraction part
366     */
367    public int getDenominator() {
368        return denominator;
369    }
370
371    /**
372     * <p>Gets the proper numerator, always positive.</p>
373     *
374     * <p>An improper fraction 7/4 can be resolved into a proper one, 1 3/4.
375     * This method returns the 3 from the proper fraction.</p>
376     *
377     * <p>If the fraction is negative such as -7/4, it can be resolved into
378     * -1 3/4, so this method returns the positive proper numerator, 3.</p>
379     *
380     * @return the numerator fraction part of a proper fraction, always positive
381     */
382    public int getProperNumerator() {
383        return Math.abs(numerator % denominator);
384    }
385
386    /**
387     * <p>Gets the proper whole part of the fraction.</p>
388     *
389     * <p>An improper fraction 7/4 can be resolved into a proper one, 1 3/4.
390     * This method returns the 1 from the proper fraction.</p>
391     *
392     * <p>If the fraction is negative such as -7/4, it can be resolved into
393     * -1 3/4, so this method returns the positive whole part -1.</p>
394     *
395     * @return the whole fraction part of a proper fraction, that includes the sign
396     */
397    public int getProperWhole() {
398        return numerator / denominator;
399    }
400
401    // Number methods
402    //-------------------------------------------------------------------
403
404    /**
405     * <p>Gets the fraction as an <code>int</code>. This returns the whole number
406     * part of the fraction.</p>
407     *
408     * @return the whole number fraction part
409     */
410    @Override
411    public int intValue() {
412        return numerator / denominator;
413    }
414
415    /**
416     * <p>Gets the fraction as a <code>long</code>. This returns the whole number
417     * part of the fraction.</p>
418     *
419     * @return the whole number fraction part
420     */
421    @Override
422    public long longValue() {
423        return (long) numerator / denominator;
424    }
425
426    /**
427     * <p>Gets the fraction as a <code>float</code>. This calculates the fraction
428     * as the numerator divided by denominator.</p>
429     *
430     * @return the fraction as a <code>float</code>
431     */
432    @Override
433    public float floatValue() {
434        return (float) numerator / (float) denominator;
435    }
436
437    /**
438     * <p>Gets the fraction as a <code>double</code>. This calculates the fraction
439     * as the numerator divided by denominator.</p>
440     *
441     * @return the fraction as a <code>double</code>
442     */
443    @Override
444    public double doubleValue() {
445        return (double) numerator / (double) denominator;
446    }
447
448    // Calculations
449    //-------------------------------------------------------------------
450
451    /**
452     * <p>Reduce the fraction to the smallest values for the numerator and
453     * denominator, returning the result.</p>
454     *
455     * <p>For example, if this fraction represents 2/4, then the result
456     * will be 1/2.</p>
457     *
458     * @return a new reduced fraction instance, or this if no simplification possible
459     */
460    public Fraction reduce() {
461        if (numerator == 0) {
462            return equals(ZERO) ? this : ZERO;
463        }
464        final int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
465        if (gcd == 1) {
466            return this;
467        }
468        return getFraction(numerator / gcd, denominator / gcd);
469    }
470
471    /**
472     * <p>Gets a fraction that is the inverse (1/fraction) of this one.</p>
473     *
474     * <p>The returned fraction is not reduced.</p>
475     *
476     * @return a new fraction instance with the numerator and denominator
477     *         inverted.
478     * @throws ArithmeticException if the fraction represents zero.
479     */
480    public Fraction invert() {
481        if (numerator == 0) {
482            throw new ArithmeticException("Unable to invert zero.");
483        }
484        if (numerator==Integer.MIN_VALUE) {
485            throw new ArithmeticException("overflow: can't negate numerator");
486        }
487        if (numerator<0) {
488            return new Fraction(-denominator, -numerator);
489        }
490        return new Fraction(denominator, numerator);
491    }
492
493    /**
494     * <p>Gets a fraction that is the negative (-fraction) of this one.</p>
495     *
496     * <p>The returned fraction is not reduced.</p>
497     *
498     * @return a new fraction instance with the opposite signed numerator
499     */
500    public Fraction negate() {
501        // the positive range is one smaller than the negative range of an int.
502        if (numerator==Integer.MIN_VALUE) {
503            throw new ArithmeticException("overflow: too large to negate");
504        }
505        return new Fraction(-numerator, denominator);
506    }
507
508    /**
509     * <p>Gets a fraction that is the positive equivalent of this one.</p>
510     * <p>More precisely: <code>(fraction &gt;= 0 ? this : -fraction)</code></p>
511     *
512     * <p>The returned fraction is not reduced.</p>
513     *
514     * @return <code>this</code> if it is positive, or a new positive fraction
515     *  instance with the opposite signed numerator
516     */
517    public Fraction abs() {
518        if (numerator >= 0) {
519            return this;
520        }
521        return negate();
522    }
523
524    /**
525     * <p>Gets a fraction that is raised to the passed in power.</p>
526     *
527     * <p>The returned fraction is in reduced form.</p>
528     *
529     * @param power  the power to raise the fraction to
530     * @return <code>this</code> if the power is one, <code>ONE</code> if the power
531     * is zero (even if the fraction equals ZERO) or a new fraction instance
532     * raised to the appropriate power
533     * @throws ArithmeticException if the resulting numerator or denominator exceeds
534     *  <code>Integer.MAX_VALUE</code>
535     */
536    public Fraction pow(final int power) {
537        if (power == 1) {
538            return this;
539        } else if (power == 0) {
540            return ONE;
541        } else if (power < 0) {
542            if (power == Integer.MIN_VALUE) { // MIN_VALUE can't be negated.
543                return this.invert().pow(2).pow(-(power / 2));
544            }
545            return this.invert().pow(-power);
546        } else {
547            final Fraction f = this.multiplyBy(this);
548            if (power % 2 == 0) { // if even...
549                return f.pow(power / 2);
550            }
551            return f.pow(power / 2).multiplyBy(this);
552        }
553    }
554
555    /**
556     * <p>Gets the greatest common divisor of the absolute value of
557     * two numbers, using the "binary gcd" method which avoids
558     * division and modulo operations.  See Knuth 4.5.2 algorithm B.
559     * This algorithm is due to Josef Stein (1961).</p>
560     *
561     * @param u  a non-zero number
562     * @param v  a non-zero number
563     * @return the greatest common divisor, never zero
564     */
565    private static int greatestCommonDivisor(int u, int v) {
566        // From Commons Math:
567        if (u == 0 || v == 0) {
568            if (u == Integer.MIN_VALUE || v == Integer.MIN_VALUE) {
569                throw new ArithmeticException("overflow: gcd is 2^31");
570            }
571            return Math.abs(u) + Math.abs(v);
572        }
573        // if either operand is abs 1, return 1:
574        if (Math.abs(u) == 1 || Math.abs(v) == 1) {
575            return 1;
576        }
577        // keep u and v negative, as negative integers range down to
578        // -2^31, while positive numbers can only be as large as 2^31-1
579        // (i.e. we can't necessarily negate a negative number without
580        // overflow)
581        if (u > 0) {
582            u = -u;
583        } // make u negative
584        if (v > 0) {
585            v = -v;
586        } // make v negative
587        // B1. [Find power of 2]
588        int k = 0;
589        while ((u & 1) == 0 && (v & 1) == 0 && k < 31) { // while u and v are both even...
590            u /= 2;
591            v /= 2;
592            k++; // cast out twos.
593        }
594        if (k == 31) {
595            throw new ArithmeticException("overflow: gcd is 2^31");
596        }
597        // B2. Initialize: u and v have been divided by 2^k and at least
598        // one is odd.
599        int t = (u & 1) == 1 ? v : -(u / 2)/* B3 */;
600        // t negative: u was odd, v may be even (t replaces v)
601        // t positive: u was even, v is odd (t replaces u)
602        do {
603            /* assert u<0 && v<0; */
604            // B4/B3: cast out twos from t.
605            while ((t & 1) == 0) { // while t is even..
606                t /= 2; // cast out twos
607            }
608            // B5 [reset max(u,v)]
609            if (t > 0) {
610                u = -t;
611            } else {
612                v = t;
613            }
614            // B6/B3. at this point both u and v should be odd.
615            t = (v - u) / 2;
616            // |u| larger: t positive (replace u)
617            // |v| larger: t negative (replace v)
618        } while (t != 0);
619        return -u * (1 << k); // gcd is u*2^k
620    }
621
622    // Arithmetic
623    //-------------------------------------------------------------------
624
625    /**
626     * Multiply two integers, checking for overflow.
627     *
628     * @param x a factor
629     * @param y a factor
630     * @return the product <code>x*y</code>
631     * @throws ArithmeticException if the result can not be represented as
632     *                             an int
633     */
634    private static int mulAndCheck(final int x, final int y) {
635        final long m = (long) x * (long) y;
636        if (m < Integer.MIN_VALUE || m > Integer.MAX_VALUE) {
637            throw new ArithmeticException("overflow: mul");
638        }
639        return (int) m;
640    }
641
642    /**
643     *  Multiply two non-negative integers, checking for overflow.
644     *
645     * @param x a non-negative factor
646     * @param y a non-negative factor
647     * @return the product <code>x*y</code>
648     * @throws ArithmeticException if the result can not be represented as
649     * an int
650     */
651    private static int mulPosAndCheck(final int x, final int y) {
652        /* assert x>=0 && y>=0; */
653        final long m = (long) x * (long) y;
654        if (m > Integer.MAX_VALUE) {
655            throw new ArithmeticException("overflow: mulPos");
656        }
657        return (int) m;
658    }
659
660    /**
661     * Add two integers, checking for overflow.
662     *
663     * @param x an addend
664     * @param y an addend
665     * @return the sum <code>x+y</code>
666     * @throws ArithmeticException if the result can not be represented as
667     * an int
668     */
669    private static int addAndCheck(final int x, final int y) {
670        final long s = (long) x + (long) y;
671        if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
672            throw new ArithmeticException("overflow: add");
673        }
674        return (int) s;
675    }
676
677    /**
678     * Subtract two integers, checking for overflow.
679     *
680     * @param x the minuend
681     * @param y the subtrahend
682     * @return the difference <code>x-y</code>
683     * @throws ArithmeticException if the result can not be represented as
684     * an int
685     */
686    private static int subAndCheck(final int x, final int y) {
687        final long s = (long) x - (long) y;
688        if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
689            throw new ArithmeticException("overflow: add");
690        }
691        return (int) s;
692    }
693
694    /**
695     * <p>Adds the value of this fraction to another, returning the result in reduced form.
696     * The algorithm follows Knuth, 4.5.1.</p>
697     *
698     * @param fraction  the fraction to add, must not be <code>null</code>
699     * @return a <code>Fraction</code> instance with the resulting values
700     * @throws IllegalArgumentException if the fraction is <code>null</code>
701     * @throws ArithmeticException if the resulting numerator or denominator exceeds
702     *  <code>Integer.MAX_VALUE</code>
703     */
704    public Fraction add(final Fraction fraction) {
705        return addSub(fraction, true /* add */);
706    }
707
708    /**
709     * <p>Subtracts the value of another fraction from the value of this one,
710     * returning the result in reduced form.</p>
711     *
712     * @param fraction  the fraction to subtract, must not be <code>null</code>
713     * @return a <code>Fraction</code> instance with the resulting values
714     * @throws IllegalArgumentException if the fraction is <code>null</code>
715     * @throws ArithmeticException if the resulting numerator or denominator
716     *   cannot be represented in an <code>int</code>.
717     */
718    public Fraction subtract(final Fraction fraction) {
719        return addSub(fraction, false /* subtract */);
720    }
721
722    /**
723     * Implement add and subtract using algorithm described in Knuth 4.5.1.
724     *
725     * @param fraction the fraction to subtract, must not be <code>null</code>
726     * @param isAdd true to add, false to subtract
727     * @return a <code>Fraction</code> instance with the resulting values
728     * @throws IllegalArgumentException if the fraction is <code>null</code>
729     * @throws ArithmeticException if the resulting numerator or denominator
730     *   cannot be represented in an <code>int</code>.
731     */
732    private Fraction addSub(final Fraction fraction, final boolean isAdd) {
733        Validate.isTrue(fraction != null, "The fraction must not be null");
734        // zero is identity for addition.
735        if (numerator == 0) {
736            return isAdd ? fraction : fraction.negate();
737        }
738        if (fraction.numerator == 0) {
739            return this;
740        }
741        // if denominators are randomly distributed, d1 will be 1 about 61%
742        // of the time.
743        final int d1 = greatestCommonDivisor(denominator, fraction.denominator);
744        if (d1 == 1) {
745            // result is ( (u*v' +/- u'v) / u'v')
746            final int uvp = mulAndCheck(numerator, fraction.denominator);
747            final int upv = mulAndCheck(fraction.numerator, denominator);
748            return new Fraction(isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv), mulPosAndCheck(denominator,
749                    fraction.denominator));
750        }
751        // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
752        // exercise 7. we're going to use a BigInteger.
753        // t = u(v'/d1) +/- v(u'/d1)
754        final BigInteger uvp = BigInteger.valueOf(numerator).multiply(BigInteger.valueOf(fraction.denominator / d1));
755        final BigInteger upv = BigInteger.valueOf(fraction.numerator).multiply(BigInteger.valueOf(denominator / d1));
756        final BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
757        // but d2 doesn't need extra precision because
758        // d2 = gcd(t,d1) = gcd(t mod d1, d1)
759        final int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
760        final int d2 = tmodd1 == 0 ? d1 : greatestCommonDivisor(tmodd1, d1);
761
762        // result is (t/d2) / (u'/d1)(v'/d2)
763        final BigInteger w = t.divide(BigInteger.valueOf(d2));
764        if (w.bitLength() > 31) {
765            throw new ArithmeticException("overflow: numerator too large after multiply");
766        }
767        return new Fraction(w.intValue(), mulPosAndCheck(denominator / d1, fraction.denominator / d2));
768    }
769
770    /**
771     * <p>Multiplies the value of this fraction by another, returning the
772     * result in reduced form.</p>
773     *
774     * @param fraction  the fraction to multiply by, must not be <code>null</code>
775     * @return a <code>Fraction</code> instance with the resulting values
776     * @throws IllegalArgumentException if the fraction is <code>null</code>
777     * @throws ArithmeticException if the resulting numerator or denominator exceeds
778     *  <code>Integer.MAX_VALUE</code>
779     */
780    public Fraction multiplyBy(final Fraction fraction) {
781        Validate.isTrue(fraction != null, "The fraction must not be null");
782        if (numerator == 0 || fraction.numerator == 0) {
783            return ZERO;
784        }
785        // knuth 4.5.1
786        // make sure we don't overflow unless the result *must* overflow.
787        final int d1 = greatestCommonDivisor(numerator, fraction.denominator);
788        final int d2 = greatestCommonDivisor(fraction.numerator, denominator);
789        return getReducedFraction(mulAndCheck(numerator / d1, fraction.numerator / d2),
790                mulPosAndCheck(denominator / d2, fraction.denominator / d1));
791    }
792
793    /**
794     * <p>Divide the value of this fraction by another.</p>
795     *
796     * @param fraction  the fraction to divide by, must not be <code>null</code>
797     * @return a <code>Fraction</code> instance with the resulting values
798     * @throws IllegalArgumentException if the fraction is <code>null</code>
799     * @throws ArithmeticException if the fraction to divide by is zero
800     * @throws ArithmeticException if the resulting numerator or denominator exceeds
801     *  <code>Integer.MAX_VALUE</code>
802     */
803    public Fraction divideBy(final Fraction fraction) {
804        Validate.isTrue(fraction != null, "The fraction must not be null");
805        if (fraction.numerator == 0) {
806            throw new ArithmeticException("The fraction to divide by must not be zero");
807        }
808        return multiplyBy(fraction.invert());
809    }
810
811    // Basics
812    //-------------------------------------------------------------------
813
814    /**
815     * <p>Compares this fraction to another object to test if they are equal.</p>.
816     *
817     * <p>To be equal, both values must be equal. Thus 2/4 is not equal to 1/2.</p>
818     *
819     * @param obj the reference object with which to compare
820     * @return <code>true</code> if this object is equal
821     */
822    @Override
823    public boolean equals(final Object obj) {
824        if (obj == this) {
825            return true;
826        }
827        if (!(obj instanceof Fraction)) {
828            return false;
829        }
830        final Fraction other = (Fraction) obj;
831        return getNumerator() == other.getNumerator() && getDenominator() == other.getDenominator();
832    }
833
834    /**
835     * <p>Gets a hashCode for the fraction.</p>
836     *
837     * @return a hash code value for this object
838     */
839    @Override
840    public int hashCode() {
841        if (hashCode == 0) {
842            // hash code update should be atomic.
843            hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator();
844        }
845        return hashCode;
846    }
847
848    /**
849     * <p>Compares this object to another based on size.</p>
850     *
851     * <p>Note: this class has a natural ordering that is inconsistent
852     * with equals, because, for example, equals treats 1/2 and 2/4 as
853     * different, whereas compareTo treats them as equal.
854     *
855     * @param other  the object to compare to
856     * @return -1 if this is less, 0 if equal, +1 if greater
857     * @throws ClassCastException if the object is not a <code>Fraction</code>
858     * @throws NullPointerException if the object is <code>null</code>
859     */
860    @Override
861    public int compareTo(final Fraction other) {
862        if (this == other) {
863            return 0;
864        }
865        if (numerator == other.numerator && denominator == other.denominator) {
866            return 0;
867        }
868
869        // otherwise see which is less
870        final long first = (long) numerator * (long) other.denominator;
871        final long second = (long) other.numerator * (long) denominator;
872        if (first == second) {
873            return 0;
874        } else if (first < second) {
875            return -1;
876        } else {
877            return 1;
878        }
879    }
880
881    /**
882     * <p>Gets the fraction as a <code>String</code>.</p>
883     *
884     * <p>The format used is '<i>numerator</i>/<i>denominator</i>' always.
885     *
886     * @return a <code>String</code> form of the fraction
887     */
888    @Override
889    public String toString() {
890        if (toString == null) {
891            toString = getNumerator() + "/" + getDenominator();
892        }
893        return toString;
894    }
895
896    /**
897     * <p>Gets the fraction as a proper <code>String</code> in the format X Y/Z.</p>
898     *
899     * <p>The format used in '<i>wholeNumber</i> <i>numerator</i>/<i>denominator</i>'.
900     * If the whole number is zero it will be omitted. If the numerator is zero,
901     * only the whole number is returned.</p>
902     *
903     * @return a <code>String</code> form of the fraction
904     */
905    public String toProperString() {
906        if (toProperString == null) {
907            if (numerator == 0) {
908                toProperString = "0";
909            } else if (numerator == denominator) {
910                toProperString = "1";
911            } else if (numerator == -1 * denominator) {
912                toProperString = "-1";
913            } else if ((numerator > 0 ? -numerator : numerator) < -denominator) {
914                // note that we do the magnitude comparison test above with
915                // NEGATIVE (not positive) numbers, since negative numbers
916                // have a larger range. otherwise numerator==Integer.MIN_VALUE
917                // is handled incorrectly.
918                final int properNumerator = getProperNumerator();
919                if (properNumerator == 0) {
920                    toProperString = Integer.toString(getProperWhole());
921                } else {
922                    toProperString = getProperWhole() + " " + properNumerator + "/" + getDenominator();
923                }
924            } else {
925                toProperString = getNumerator() + "/" + getDenominator();
926            }
927        }
928        return toProperString;
929    }
930}