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