View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    * 
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   * 
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.lang3.math;
18  
19  import java.math.BigInteger;
20  
21  /**
22   * <p><code>Fraction</code> is a <code>Number</code> implementation that
23   * stores fractions accurately.</p>
24   *
25   * <p>This class is immutable, and interoperable with most methods that accept
26   * a <code>Number</code>.</p>
27   *
28   * <p>Note that this class is intended for common use cases, it is <i>int</i>
29   * based and thus suffers from various overflow issues. For a BigInteger based 
30   * equivalent, please see the Commons Math BigFraction class. </p>
31   *
32   * @since 2.0
33   * @version $Id: Fraction.java 1583482 2014-03-31 22:54:57Z niallp $
34   */
35  public final class Fraction extends Number implements Comparable<Fraction> {
36  
37      /**
38       * Required for serialization support. Lang version 2.0.
39       * 
40       * @see java.io.Serializable
41       */
42      private static final long serialVersionUID = 65382027393090L;
43  
44      /**
45       * <code>Fraction</code> representation of 0.
46       */
47      public static final Fraction ZERO = new Fraction(0, 1);
48      /**
49       * <code>Fraction</code> representation of 1.
50       */
51      public static final Fraction ONE = new Fraction(1, 1);
52      /**
53       * <code>Fraction</code> representation of 1/2.
54       */
55      public static final Fraction ONE_HALF = new Fraction(1, 2);
56      /**
57       * <code>Fraction</code> representation of 1/3.
58       */
59      public static final Fraction ONE_THIRD = new Fraction(1, 3);
60      /**
61       * <code>Fraction</code> representation of 2/3.
62       */
63      public static final Fraction TWO_THIRDS = new Fraction(2, 3);
64      /**
65       * <code>Fraction</code> representation of 1/4.
66       */
67      public static final Fraction ONE_QUARTER = new Fraction(1, 4);
68      /**
69       * <code>Fraction</code> representation of 2/4.
70       */
71      public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
72      /**
73       * <code>Fraction</code> representation of 3/4.
74       */
75      public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
76      /**
77       * <code>Fraction</code> representation of 1/5.
78       */
79      public static final Fraction ONE_FIFTH = new Fraction(1, 5);
80      /**
81       * <code>Fraction</code> representation of 2/5.
82       */
83      public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
84      /**
85       * <code>Fraction</code> representation of 3/5.
86       */
87      public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
88      /**
89       * <code>Fraction</code> representation of 4/5.
90       */
91      public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
92  
93  
94      /**
95       * The numerator number part of the fraction (the three in three sevenths).
96       */
97      private final int numerator;
98      /**
99       * 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| &gt; 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      * <p>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 &gt;= 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 }