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