001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     * 
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     * 
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.lang.math;
018    
019    import 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     * @author Apache Software Foundation
029     * @author Travis Reeder
030     * @author Tim O'Brien
031     * @author Pete Gieser
032     * @author C. Scott Ananian
033     * @since 2.0
034     * @version $Id: Fraction.java 905636 2010-02-02 14:03:32Z niallp $
035     */
036    public final class Fraction extends Number implements Comparable {
037    
038        /**
039         * Required for serialization support. Lang version 2.0.
040         * 
041         * @see java.io.Serializable
042         */
043        private static final long serialVersionUID = 65382027393090L;
044    
045        /**
046         * <code>Fraction</code> representation of 0.
047         */
048        public static final Fraction ZERO = new Fraction(0, 1);
049        /**
050         * <code>Fraction</code> representation of 1.
051         */
052        public static final Fraction ONE = new Fraction(1, 1);
053        /**
054         * <code>Fraction</code> representation of 1/2.
055         */
056        public static final Fraction ONE_HALF = new Fraction(1, 2);
057        /**
058         * <code>Fraction</code> representation of 1/3.
059         */
060        public static final Fraction ONE_THIRD = new Fraction(1, 3);
061        /**
062         * <code>Fraction</code> representation of 2/3.
063         */
064        public static final Fraction TWO_THIRDS = new Fraction(2, 3);
065        /**
066         * <code>Fraction</code> representation of 1/4.
067         */
068        public static final Fraction ONE_QUARTER = new Fraction(1, 4);
069        /**
070         * <code>Fraction</code> representation of 2/4.
071         */
072        public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
073        /**
074         * <code>Fraction</code> representation of 3/4.
075         */
076        public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
077        /**
078         * <code>Fraction</code> representation of 1/5.
079         */
080        public static final Fraction ONE_FIFTH = new Fraction(1, 5);
081        /**
082         * <code>Fraction</code> representation of 2/5.
083         */
084        public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
085        /**
086         * <code>Fraction</code> representation of 3/5.
087         */
088        public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
089        /**
090         * <code>Fraction</code> representation of 4/5.
091         */
092        public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
093    
094    
095        /**
096         * The numerator number part of the fraction (the three in three sevenths).
097         */
098        private final int numerator;
099        /**
100         * The denominator number part of the fraction (the seven in three sevenths).
101         */
102        private final int denominator;
103    
104        /**
105         * Cached output hashCode (class is immutable).
106         */
107        private transient int hashCode = 0;
108        /**
109         * Cached output toString (class is immutable).
110         */
111        private transient String toString = null;
112        /**
113         * Cached output toProperString (class is immutable).
114         */
115        private transient String toProperString = null;
116    
117        /**
118         * <p>Constructs a <code>Fraction</code> instance with the 2 parts
119         * of a fraction Y/Z.</p>
120         *
121         * @param numerator  the numerator, for example the three in 'three sevenths'
122         * @param denominator  the denominator, for example the seven in 'three sevenths'
123         */
124        private Fraction(int numerator, int denominator) {
125            super();
126            this.numerator = numerator;
127            this.denominator = denominator;
128        }
129    
130        /**
131         * <p>Creates a <code>Fraction</code> instance with the 2 parts
132         * of a fraction Y/Z.</p>
133         *
134         * <p>Any negative signs are resolved to be on the numerator.</p>
135         *
136         * @param numerator  the numerator, for example the three in 'three sevenths'
137         * @param denominator  the denominator, for example the seven in 'three sevenths'
138         * @return a new fraction instance
139         * @throws ArithmeticException if the denomiator is <code>zero</code>
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 denomiator 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(int whole, int numerator, 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            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            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            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                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                    int numer = Integer.parseInt(str.substring(0, pos));
339                    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                int numer = Integer.parseInt(str.substring(0, pos));
351                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        public int intValue() {
420            return numerator / denominator;
421        }
422    
423        /**
424         * <p>Gets the fraction as a <code>long</code>. This returns the whole number
425         * part of the fraction.</p>
426         *
427         * @return the whole number fraction part
428         */
429        public long longValue() {
430            return (long) numerator / denominator;
431        }
432    
433        /**
434         * <p>Gets the fraction as a <code>float</code>. This calculates the fraction
435         * as the numerator divided by denominator.</p>
436         *
437         * @return the fraction as a <code>float</code>
438         */
439        public float floatValue() {
440            return ((float) numerator) / ((float) denominator);
441        }
442    
443        /**
444         * <p>Gets the fraction as a <code>double</code>. This calculates the fraction
445         * as the numerator divided by denominator.</p>
446         *
447         * @return the fraction as a <code>double</code>
448         */
449        public double doubleValue() {
450            return ((double) numerator) / ((double) denominator);
451        }
452    
453        // Calculations
454        //-------------------------------------------------------------------
455    
456        /**
457         * <p>Reduce the fraction to the smallest values for the numerator and
458         * denominator, returning the result.</p>
459         * 
460         * <p>For example, if this fraction represents 2/4, then the result
461         * will be 1/2.</p>
462         *
463         * @return a new reduced fraction instance, or this if no simplification possible
464         */
465        public Fraction reduce() {
466            if (numerator == 0) {
467                return equals(ZERO) ? this : ZERO;
468            }
469            int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
470            if (gcd == 1) {
471                return this;
472            }
473            return Fraction.getFraction(numerator / gcd, denominator / gcd);
474        }
475    
476        /**
477         * <p>Gets a fraction that is the inverse (1/fraction) of this one.</p>
478         * 
479         * <p>The returned fraction is not reduced.</p>
480         *
481         * @return a new fraction instance with the numerator and denominator
482         *         inverted.
483         * @throws ArithmeticException if the fraction represents zero.
484         */
485        public Fraction invert() {
486            if (numerator == 0) {
487                throw new ArithmeticException("Unable to invert zero.");
488            }
489            if (numerator==Integer.MIN_VALUE) {
490                throw new ArithmeticException("overflow: can't negate numerator");
491            }
492            if (numerator<0) {
493                return new Fraction(-denominator, -numerator);
494            } else {
495                return new Fraction(denominator, numerator);
496            }
497        }
498    
499        /**
500         * <p>Gets a fraction that is the negative (-fraction) of this one.</p>
501         *
502         * <p>The returned fraction is not reduced.</p>
503         *
504         * @return a new fraction instance with the opposite signed numerator
505         */
506        public Fraction negate() {
507            // the positive range is one smaller than the negative range of an int.
508            if (numerator==Integer.MIN_VALUE) {
509                throw new ArithmeticException("overflow: too large to negate");
510            }
511            return new Fraction(-numerator, denominator);
512        }
513    
514        /**
515         * <p>Gets a fraction that is the positive equivalent of this one.</p>
516         * <p>More precisely: <code>(fraction >= 0 ? this : -fraction)</code></p>
517         *
518         * <p>The returned fraction is not reduced.</p>
519         *
520         * @return <code>this</code> if it is positive, or a new positive fraction
521         *  instance with the opposite signed numerator
522         */
523        public Fraction abs() {
524            if (numerator >= 0) {
525                return this;
526            }
527            return negate();
528        }
529    
530        /**
531         * <p>Gets a fraction that is raised to the passed in power.</p>
532         *
533         * <p>The returned fraction is in reduced form.</p>
534         *
535         * @param power  the power to raise the fraction to
536         * @return <code>this</code> if the power is one, <code>ONE</code> if the power
537         * is zero (even if the fraction equals ZERO) or a new fraction instance 
538         * raised to the appropriate power
539         * @throws ArithmeticException if the resulting numerator or denominator exceeds
540         *  <code>Integer.MAX_VALUE</code>
541         */
542        public Fraction pow(int power) {
543            if (power == 1) {
544                return this;
545            } else if (power == 0) {
546                return ONE;
547            } else if (power < 0) {
548                if (power==Integer.MIN_VALUE) { // MIN_VALUE can't be negated.
549                    return this.invert().pow(2).pow(-(power/2));
550                }
551                return this.invert().pow(-power);
552            } else {
553                Fraction f = this.multiplyBy(this);
554                if ((power % 2) == 0) { // if even...
555                    return f.pow(power/2);
556                } else { // if odd...
557                    return f.pow(power/2).multiplyBy(this);
558                }
559            }
560        }
561    
562        /**
563         * <p>Gets the greatest common divisor of the absolute value of
564         * two numbers, using the "binary gcd" method which avoids
565         * division and modulo operations.  See Knuth 4.5.2 algorithm B.
566         * This algorithm is due to Josef Stein (1961).</p>
567         *
568         * @param u  a non-zero number
569         * @param v  a non-zero number
570         * @return the greatest common divisor, never zero
571         */
572        private static int greatestCommonDivisor(int u, int v) {
573            //if either op. is abs 0 or 1, return 1:
574            if (Math.abs(u) <= 1 || Math.abs(v) <= 1) {
575                return 1;
576            }
577            // keep u and v negative, as negative integers range down to
578            // -2^31, while positive numbers can only be as large as 2^31-1
579            // (i.e. we can't necessarily negate a negative number without
580            // overflow)
581            if (u>0) { u=-u; } // make u negative
582            if (v>0) { v=-v; } // make v negative
583            // B1. [Find power of 2]
584            int k=0;
585            while ((u&1)==0 && (v&1)==0 && k<31) { // while u and v are both even...
586                u/=2; v/=2; k++; // cast out twos.
587            }
588            if (k==31) {
589                throw new ArithmeticException("overflow: gcd is 2^31");
590            }
591            // B2. Initialize: u and v have been divided by 2^k and at least
592            //     one is odd.
593            int t = ((u&1)==1) ? v : -(u/2)/*B3*/;
594            // t negative: u was odd, v may be even (t replaces v)
595            // t positive: u was even, v is odd (t replaces u)
596            do {
597                /* assert u<0 && v<0; */
598                // B4/B3: cast out twos from t.
599                while ((t&1)==0) { // while t is even..
600                    t/=2; // cast out twos
601                }
602                // B5 [reset max(u,v)]
603                if (t>0) {
604                    u = -t;
605                } else {
606                    v = t;
607                }
608                // B6/B3. at this point both u and v should be odd.
609                t = (v - u)/2;
610                // |u| larger: t positive (replace u)
611                // |v| larger: t negative (replace v)
612            } while (t!=0);
613            return -u*(1<<k); // gcd is u*2^k
614        }
615    
616        // Arithmetic
617        //-------------------------------------------------------------------
618    
619        /** 
620         * Multiply two integers, checking for overflow.
621         * 
622         * @param x a factor
623         * @param y a factor
624         * @return the product <code>x*y</code>
625         * @throws ArithmeticException if the result can not be represented as
626         *                             an int
627         */
628        private static int mulAndCheck(int x, int y) {
629            long m = ((long)x)*((long)y);
630            if (m < Integer.MIN_VALUE ||
631                m > Integer.MAX_VALUE) {
632                throw new ArithmeticException("overflow: mul");
633            }
634            return (int)m;
635        }
636        
637        /**
638         *  Multiply two non-negative integers, checking for overflow.
639         * 
640         * @param x a non-negative factor
641         * @param y a non-negative factor
642         * @return the product <code>x*y</code>
643         * @throws ArithmeticException if the result can not be represented as
644         * an int
645         */
646        private static int mulPosAndCheck(int x, int y) {
647            /* assert x>=0 && y>=0; */
648            long m = ((long)x)*((long)y);
649            if (m > Integer.MAX_VALUE) {
650                throw new ArithmeticException("overflow: mulPos");
651            }
652            return (int)m;
653        }
654        
655        /** 
656         * Add two integers, checking for overflow.
657         * 
658         * @param x an addend
659         * @param y an addend
660         * @return the sum <code>x+y</code>
661         * @throws ArithmeticException if the result can not be represented as
662         * an int
663         */
664        private static int addAndCheck(int x, int y) {
665            long s = (long)x+(long)y;
666            if (s < Integer.MIN_VALUE ||
667                s > Integer.MAX_VALUE) {
668                throw new ArithmeticException("overflow: add");
669            }
670            return (int)s;
671        }
672        
673        /** 
674         * Subtract two integers, checking for overflow.
675         * 
676         * @param x the minuend
677         * @param y the subtrahend
678         * @return the difference <code>x-y</code>
679         * @throws ArithmeticException if the result can not be represented as
680         * an int
681         */
682        private static int subAndCheck(int x, int y) {
683            long s = (long)x-(long)y;
684            if (s < Integer.MIN_VALUE ||
685                s > Integer.MAX_VALUE) {
686                throw new ArithmeticException("overflow: add");
687            }
688            return (int)s;
689        }
690        
691        /**
692         * <p>Adds the value of this fraction to another, returning the result in reduced form.
693         * The algorithm follows Knuth, 4.5.1.</p>
694         *
695         * @param fraction  the fraction to add, must not be <code>null</code>
696         * @return a <code>Fraction</code> instance with the resulting values
697         * @throws IllegalArgumentException if the fraction is <code>null</code>
698         * @throws ArithmeticException if the resulting numerator or denominator exceeds
699         *  <code>Integer.MAX_VALUE</code>
700         */
701        public Fraction add(Fraction fraction) {
702            return addSub(fraction, true /* add */);
703        }
704    
705        /**
706         * <p>Subtracts the value of another fraction from the value of this one, 
707         * returning the result in reduced form.</p>
708         *
709         * @param fraction  the fraction to subtract, must not be <code>null</code>
710         * @return a <code>Fraction</code> instance with the resulting values
711         * @throws IllegalArgumentException if the fraction is <code>null</code>
712         * @throws ArithmeticException if the resulting numerator or denominator
713         *   cannot be represented in an <code>int</code>.
714         */
715        public Fraction subtract(Fraction fraction) {
716            return addSub(fraction, false /* subtract */);
717        }
718    
719        /** 
720         * Implement add and subtract using algorithm described in Knuth 4.5.1.
721         * 
722         * @param fraction the fraction to subtract, must not be <code>null</code>
723         * @param isAdd true to add, false to subtract
724         * @return a <code>Fraction</code> instance with the resulting values
725         * @throws IllegalArgumentException if the fraction is <code>null</code>
726         * @throws ArithmeticException if the resulting numerator or denominator
727         *   cannot be represented in an <code>int</code>.
728         */
729        private Fraction addSub(Fraction fraction, boolean isAdd) {
730            if (fraction == null) {
731                throw new IllegalArgumentException("The fraction must not be null");
732            }
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            int d1 = greatestCommonDivisor(denominator, fraction.denominator);
743            if (d1==1) {
744                // result is ( (u*v' +/- u'v) / u'v')
745                int uvp = mulAndCheck(numerator, fraction.denominator);
746                int upv = mulAndCheck(fraction.numerator, denominator);
747                return new Fraction
748                    (isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv),
749                     mulPosAndCheck(denominator, fraction.denominator));
750            }
751            // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
752            // exercise 7.  we're going to use a BigInteger.
753            // t = u(v'/d1) +/- v(u'/d1)
754            BigInteger uvp = BigInteger.valueOf(numerator)
755                .multiply(BigInteger.valueOf(fraction.denominator/d1));
756            BigInteger upv = BigInteger.valueOf(fraction.numerator)
757                .multiply(BigInteger.valueOf(denominator/d1));
758            BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
759            // but d2 doesn't need extra precision because
760            // d2 = gcd(t,d1) = gcd(t mod d1, d1)
761            int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
762            int d2 = (tmodd1==0)?d1:greatestCommonDivisor(tmodd1, d1);
763    
764            // result is (t/d2) / (u'/d1)(v'/d2)
765            BigInteger w = t.divide(BigInteger.valueOf(d2));
766            if (w.bitLength() > 31) {
767                throw new ArithmeticException
768                    ("overflow: numerator too large after multiply");
769            }
770            return new Fraction
771                (w.intValue(),
772                 mulPosAndCheck(denominator/d1, fraction.denominator/d2));
773        }
774    
775        /**
776         * <p>Multiplies the value of this fraction by another, returning the 
777         * result in reduced form.</p>
778         *
779         * @param fraction  the fraction to multiply by, must not be <code>null</code>
780         * @return a <code>Fraction</code> instance with the resulting values
781         * @throws IllegalArgumentException if the fraction is <code>null</code>
782         * @throws ArithmeticException if the resulting numerator or denominator exceeds
783         *  <code>Integer.MAX_VALUE</code>
784         */
785        public Fraction multiplyBy(Fraction fraction) {
786            if (fraction == null) {
787                throw new IllegalArgumentException("The fraction must not be null");
788            }
789            if (numerator == 0 || fraction.numerator == 0) {
790                return ZERO;
791            }
792            // knuth 4.5.1
793            // make sure we don't overflow unless the result *must* overflow.
794            int d1 = greatestCommonDivisor(numerator, fraction.denominator);
795            int d2 = greatestCommonDivisor(fraction.numerator, denominator);
796            return getReducedFraction
797                (mulAndCheck(numerator/d1, fraction.numerator/d2),
798                 mulPosAndCheck(denominator/d2, fraction.denominator/d1));
799        }
800    
801        /**
802         * <p>Divide the value of this fraction by another.</p>
803         *
804         * @param fraction  the fraction to divide by, must not be <code>null</code>
805         * @return a <code>Fraction</code> instance with the resulting values
806         * @throws IllegalArgumentException if the fraction is <code>null</code>
807         * @throws ArithmeticException if the fraction to divide by is zero
808         * @throws ArithmeticException if the resulting numerator or denominator exceeds
809         *  <code>Integer.MAX_VALUE</code>
810         */
811        public Fraction divideBy(Fraction fraction) {
812            if (fraction == null) {
813                throw new IllegalArgumentException("The fraction must not be null");
814            }
815            if (fraction.numerator == 0) {
816                throw new ArithmeticException("The fraction to divide by must not be zero");
817            }
818            return multiplyBy(fraction.invert());
819        }
820    
821        // Basics
822        //-------------------------------------------------------------------
823    
824        /**
825         * <p>Compares this fraction to another object to test if they are equal.</p>.
826         *
827         * <p>To be equal, both values must be equal. Thus 2/4 is not equal to 1/2.</p>
828         *
829         * @param obj the reference object with which to compare
830         * @return <code>true</code> if this object is equal
831         */
832        public boolean equals(Object obj) {
833            if (obj == this) {
834                return true;
835            }
836            if (obj instanceof Fraction == false) {
837                return false;
838            }
839            Fraction other = (Fraction) obj;
840            return (getNumerator() == other.getNumerator() &&
841                    getDenominator() == other.getDenominator());
842        }
843    
844        /**
845         * <p>Gets a hashCode for the fraction.</p>
846         *
847         * @return a hash code value for this object
848         */
849        public int hashCode() {
850            if (hashCode == 0) {
851                // hashcode update should be atomic.
852                hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator();
853            }
854            return hashCode;
855        }
856    
857        /**
858         * <p>Compares this object to another based on size.</p>
859         *
860         * <p>Note: this class has a natural ordering that is inconsistent
861         * with equals, because, for example, equals treats 1/2 and 2/4 as
862         * different, whereas compareTo treats them as equal.
863         *
864         * @param object  the object to compare to
865         * @return -1 if this is less, 0 if equal, +1 if greater
866         * @throws ClassCastException if the object is not a <code>Fraction</code>
867         * @throws NullPointerException if the object is <code>null</code>
868         */
869        public int compareTo(Object object) {
870            Fraction other = (Fraction) object;
871            if (this==other) {
872                return 0;
873            }
874            if (numerator == other.numerator && denominator == other.denominator) {
875                return 0;
876            }
877    
878            // otherwise see which is less
879            long first = (long) numerator * (long) other.denominator;
880            long second = (long) other.numerator * (long) denominator;
881            if (first == second) {
882                return 0;
883            } else if (first < second) {
884                return -1;
885            } else {
886                return 1;
887            }
888        }
889    
890        /**
891         * <p>Gets the fraction as a <code>String</code>.</p>
892         *
893         * <p>The format used is '<i>numerator</i>/<i>denominator</i>' always.
894         *
895         * @return a <code>String</code> form of the fraction
896         */
897        public String toString() {
898            if (toString == null) {
899                toString = new StringBuffer(32)
900                    .append(getNumerator())
901                    .append('/')
902                    .append(getDenominator()).toString();
903            }
904            return toString;
905        }
906    
907        /**
908         * <p>Gets the fraction as a proper <code>String</code> in the format X Y/Z.</p>
909         *
910         * <p>The format used in '<i>wholeNumber</i> <i>numerator</i>/<i>denominator</i>'.
911         * If the whole number is zero it will be ommitted. If the numerator is zero,
912         * only the whole number is returned.</p>
913         *
914         * @return a <code>String</code> form of the fraction
915         */
916        public String toProperString() {
917            if (toProperString == null) {
918                if (numerator == 0) {
919                    toProperString = "0";
920                } else if (numerator == denominator) {
921                    toProperString = "1";
922                } else if (numerator == -1 * denominator) {
923                    toProperString = "-1";
924                } else if ((numerator>0?-numerator:numerator) < -denominator) {
925                    // note that we do the magnitude comparison test above with
926                    // NEGATIVE (not positive) numbers, since negative numbers
927                    // have a larger range.  otherwise numerator==Integer.MIN_VALUE
928                    // is handled incorrectly.
929                    int properNumerator = getProperNumerator();
930                    if (properNumerator == 0) {
931                        toProperString = Integer.toString(getProperWhole());
932                    } else {
933                        toProperString = new StringBuffer(32)
934                            .append(getProperWhole()).append(' ')
935                            .append(properNumerator).append('/')
936                            .append(getDenominator()).toString();
937                    }
938                } else {
939                    toProperString = new StringBuffer(32)
940                        .append(getNumerator()).append('/')
941                        .append(getDenominator()).toString();
942                }
943            }
944            return toProperString;
945        }
946    }