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