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