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