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  import org.apache.commons.lang3.Validate;
22  
23  /**
24   * <p><code>Fraction</code> is a <code>Number</code> implementation that
25   * stores fractions accurately.</p>
26   *
27   * <p>This class is immutable, and interoperable with most methods that accept
28   * a <code>Number</code>.</p>
29   *
30   * <p>Note that this class is intended for common use cases, it is <i>int</i>
31   * based and thus suffers from various overflow issues. For a BigInteger based
32   * equivalent, please see the Commons Math BigFraction class. </p>
33   *
34   * @since 2.0
35   */
36  public final class Fraction extends Number implements Comparable<Fraction> {
37  
38      /**
39       * Required for serialization support. Lang version 2.0.
40       *
41       * @see java.io.Serializable
42       */
43      private static final long serialVersionUID = 65382027393090L;
44  
45      /**
46       * <code>Fraction</code> representation of 0.
47       */
48      public static final Fraction ZERO = new Fraction(0, 1);
49      /**
50       * <code>Fraction</code> representation of 1.
51       */
52      public static final Fraction ONE = new Fraction(1, 1);
53      /**
54       * <code>Fraction</code> representation of 1/2.
55       */
56      public static final Fraction ONE_HALF = new Fraction(1, 2);
57      /**
58       * <code>Fraction</code> representation of 1/3.
59       */
60      public static final Fraction ONE_THIRD = new Fraction(1, 3);
61      /**
62       * <code>Fraction</code> representation of 2/3.
63       */
64      public static final Fraction TWO_THIRDS = new Fraction(2, 3);
65      /**
66       * <code>Fraction</code> representation of 1/4.
67       */
68      public static final Fraction ONE_QUARTER = new Fraction(1, 4);
69      /**
70       * <code>Fraction</code> representation of 2/4.
71       */
72      public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
73      /**
74       * <code>Fraction</code> representation of 3/4.
75       */
76      public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
77      /**
78       * <code>Fraction</code> representation of 1/5.
79       */
80      public static final Fraction ONE_FIFTH = new Fraction(1, 5);
81      /**
82       * <code>Fraction</code> representation of 2/5.
83       */
84      public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
85      /**
86       * <code>Fraction</code> representation of 3/5.
87       */
88      public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
89      /**
90       * <code>Fraction</code> representation of 4/5.
91       */
92      public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
93  
94  
95      /**
96       * The numerator number part of the fraction (the three in three sevenths).
97       */
98      private final int numerator;
99      /**
100      * The denominator number part of the fraction (the seven in three sevenths).
101      */
102     private final int denominator;
103 
104     /**
105      * Cached output hashCode (class is immutable).
106      */
107     private transient int hashCode = 0;
108     /**
109      * Cached output toString (class is immutable).
110      */
111     private transient String toString = null;
112     /**
113      * Cached output toProperString (class is immutable).
114      */
115     private transient String toProperString = null;
116 
117     /**
118      * <p>Constructs a <code>Fraction</code> instance with the 2 parts
119      * of a fraction Y/Z.</p>
120      *
121      * @param numerator  the numerator, for example the three in 'three sevenths'
122      * @param denominator  the denominator, for example the seven in 'three sevenths'
123      */
124     private Fraction(final int numerator, final int denominator) {
125         super();
126         this.numerator = numerator;
127         this.denominator = denominator;
128     }
129 
130     /**
131      * <p>Creates a <code>Fraction</code> instance with the 2 parts
132      * of a fraction Y/Z.</p>
133      *
134      * <p>Any negative signs are resolved to be on the numerator.</p>
135      *
136      * @param numerator  the numerator, for example the three in 'three sevenths'
137      * @param denominator  the denominator, for example the seven in 'three sevenths'
138      * @return a new fraction instance
139      * @throws ArithmeticException if the denominator is <code>zero</code>
140      * or the denominator is {@code negative} and the numerator is {@code Integer#MIN_VALUE}
141      */
142     public static Fraction getFraction(int numerator, int denominator) {
143         if (denominator == 0) {
144             throw new ArithmeticException("The denominator must not be zero");
145         }
146         if (denominator < 0) {
147             if (numerator == Integer.MIN_VALUE || 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 || numeratorValue > Integer.MAX_VALUE) {
189             throw new ArithmeticException("Numerator too large to represent as an Integer.");
190         }
191         return new Fraction((int) numeratorValue, denominator);
192     }
193 
194     /**
195      * <p>Creates a reduced <code>Fraction</code> instance with the 2 parts
196      * of a fraction Y/Z.</p>
197      *
198      * <p>For example, if the input parameters represent 2/4, then the created
199      * fraction will be 1/2.</p>
200      *
201      * <p>Any negative signs are resolved to be on the numerator.</p>
202      *
203      * @param numerator  the numerator, for example the three in 'three sevenths'
204      * @param denominator  the denominator, for example the seven in 'three sevenths'
205      * @return a new fraction instance, with the numerator and denominator reduced
206      * @throws ArithmeticException if the denominator is <code>zero</code>
207      */
208     public static Fraction getReducedFraction(int numerator, int denominator) {
209         if (denominator == 0) {
210             throw new ArithmeticException("The denominator must not be zero");
211         }
212         if (numerator == 0) {
213             return ZERO; // normalize zero.
214         }
215         // allow 2^k/-2^31 as a valid fraction (where k>0)
216         if (denominator == Integer.MIN_VALUE && (numerator & 1) == 0) {
217             numerator /= 2;
218             denominator /= 2;
219         }
220         if (denominator < 0) {
221             if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) {
222                 throw new ArithmeticException("overflow: can't negate");
223             }
224             numerator = -numerator;
225             denominator = -denominator;
226         }
227         // simplify fraction.
228         final int gcd = greatestCommonDivisor(numerator, denominator);
229         numerator /= gcd;
230         denominator /= gcd;
231         return new Fraction(numerator, denominator);
232     }
233 
234     /**
235      * <p>Creates a <code>Fraction</code> instance from a <code>double</code> value.</p>
236      *
237      * <p>This method uses the <a href="http://archives.math.utk.edu/articles/atuyl/confrac/">
238      *  continued fraction algorithm</a>, computing a maximum of
239      *  25 convergents and bounding the denominator by 10,000.</p>
240      *
241      * @param value  the double value to convert
242      * @return a new fraction instance that is close to the value
243      * @throws ArithmeticException if <code>|value| &gt; Integer.MAX_VALUE</code>
244      *  or <code>value = NaN</code>
245      * @throws ArithmeticException if the calculated denominator is <code>zero</code>
246      * @throws ArithmeticException if the the algorithm does not converge
247      */
248     public static Fraction getFraction(double value) {
249         final int sign = value < 0 ? -1 : 1;
250         value = Math.abs(value);
251         if (value > Integer.MAX_VALUE || Double.isNaN(value)) {
252             throw new ArithmeticException("The value must not be greater than Integer.MAX_VALUE or NaN");
253         }
254         final int wholeNumber = (int) value;
255         value -= wholeNumber;
256 
257         int numer0 = 0; // the pre-previous
258         int denom0 = 1; // the pre-previous
259         int numer1 = 1; // the previous
260         int denom1 = 0; // the previous
261         int numer2 = 0; // the current, setup in calculation
262         int denom2 = 0; // the current, setup in calculation
263         int a1 = (int) value;
264         int a2 = 0;
265         double x1 = 1;
266         double x2 = 0;
267         double y1 = value - a1;
268         double y2 = 0;
269         double delta1, delta2 = Double.MAX_VALUE;
270         double fraction;
271         int i = 1;
272         // System.out.println("---");
273         do {
274             delta1 = delta2;
275             a2 = (int) (x1 / y1);
276             x2 = y1;
277             y2 = x1 - a2 * y1;
278             numer2 = a1 * numer1 + numer0;
279             denom2 = a1 * denom1 + denom0;
280             fraction = (double) numer2 / (double) denom2;
281             delta2 = Math.abs(value - fraction);
282             // System.out.println(numer2 + " " + denom2 + " " + fraction + " " + delta2 + " " + y1);
283             a1 = a2;
284             x1 = x2;
285             y1 = y2;
286             numer0 = numer1;
287             denom0 = denom1;
288             numer1 = numer2;
289             denom1 = denom2;
290             i++;
291             // System.out.println(">>" + delta1 +" "+ delta2+" "+(delta1 > delta2)+" "+i+" "+denom2);
292         } while (delta1 > delta2 && denom2 <= 10000 && denom2 > 0 && i < 25);
293         if (i == 25) {
294             throw new ArithmeticException("Unable to convert double to fraction");
295         }
296         return getReducedFraction((numer0 + wholeNumber * denom0) * sign, denom0);
297     }
298 
299     /**
300      * <p>Creates a Fraction from a <code>String</code>.</p>
301      *
302      * <p>The formats accepted are:</p>
303      *
304      * <ol>
305      *  <li><code>double</code> String containing a dot</li>
306      *  <li>'X Y/Z'</li>
307      *  <li>'Y/Z'</li>
308      *  <li>'X' (a simple whole number)</li>
309      * </ol>
310      * <p>and a .</p>
311      *
312      * @param str  the string to parse, must not be <code>null</code>
313      * @return the new <code>Fraction</code> instance
314      * @throws IllegalArgumentException if the string is <code>null</code>
315      * @throws NumberFormatException if the number format is invalid
316      */
317     public static Fraction getFraction(String str) {
318         Validate.isTrue(str != null, "The string must not be null");
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         Validate.isTrue(fraction != null, "The fraction must not be null");
737         // zero is identity for addition.
738         if (numerator == 0) {
739             return isAdd ? fraction : fraction.negate();
740         }
741         if (fraction.numerator == 0) {
742             return this;
743         }
744         // if denominators are randomly distributed, d1 will be 1 about 61%
745         // of the time.
746         final int d1 = greatestCommonDivisor(denominator, fraction.denominator);
747         if (d1 == 1) {
748             // result is ( (u*v' +/- u'v) / u'v')
749             final int uvp = mulAndCheck(numerator, fraction.denominator);
750             final int upv = mulAndCheck(fraction.numerator, denominator);
751             return new Fraction(isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv), mulPosAndCheck(denominator,
752                     fraction.denominator));
753         }
754         // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
755         // exercise 7. we're going to use a BigInteger.
756         // t = u(v'/d1) +/- v(u'/d1)
757         final BigInteger uvp = BigInteger.valueOf(numerator).multiply(BigInteger.valueOf(fraction.denominator / d1));
758         final BigInteger upv = BigInteger.valueOf(fraction.numerator).multiply(BigInteger.valueOf(denominator / d1));
759         final BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
760         // but d2 doesn't need extra precision because
761         // d2 = gcd(t,d1) = gcd(t mod d1, d1)
762         final int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
763         final int d2 = tmodd1 == 0 ? d1 : greatestCommonDivisor(tmodd1, d1);
764 
765         // result is (t/d2) / (u'/d1)(v'/d2)
766         final BigInteger w = t.divide(BigInteger.valueOf(d2));
767         if (w.bitLength() > 31) {
768             throw new ArithmeticException("overflow: numerator too large after multiply");
769         }
770         return new Fraction(w.intValue(), mulPosAndCheck(denominator / d1, fraction.denominator / d2));
771     }
772 
773     /**
774      * <p>Multiplies the value of this fraction by another, returning the
775      * result in reduced form.</p>
776      *
777      * @param fraction  the fraction to multiply by, must not be <code>null</code>
778      * @return a <code>Fraction</code> instance with the resulting values
779      * @throws IllegalArgumentException if the fraction is <code>null</code>
780      * @throws ArithmeticException if the resulting numerator or denominator exceeds
781      *  <code>Integer.MAX_VALUE</code>
782      */
783     public Fraction multiplyBy(final Fraction fraction) {
784         Validate.isTrue(fraction != null, "The fraction must not be null");
785         if (numerator == 0 || fraction.numerator == 0) {
786             return ZERO;
787         }
788         // knuth 4.5.1
789         // make sure we don't overflow unless the result *must* overflow.
790         final int d1 = greatestCommonDivisor(numerator, fraction.denominator);
791         final int d2 = greatestCommonDivisor(fraction.numerator, denominator);
792         return getReducedFraction(mulAndCheck(numerator / d1, fraction.numerator / d2),
793                 mulPosAndCheck(denominator / d2, fraction.denominator / d1));
794     }
795 
796     /**
797      * <p>Divide the value of this fraction by another.</p>
798      *
799      * @param fraction  the fraction to divide by, must not be <code>null</code>
800      * @return a <code>Fraction</code> instance with the resulting values
801      * @throws IllegalArgumentException if the fraction is <code>null</code>
802      * @throws ArithmeticException if the fraction to divide by is zero
803      * @throws ArithmeticException if the resulting numerator or denominator exceeds
804      *  <code>Integer.MAX_VALUE</code>
805      */
806     public Fraction divideBy(final Fraction fraction) {
807         Validate.isTrue(fraction != null, "The fraction must not be null");
808         if (fraction.numerator == 0) {
809             throw new ArithmeticException("The fraction to divide by must not be zero");
810         }
811         return multiplyBy(fraction.invert());
812     }
813 
814     // Basics
815     //-------------------------------------------------------------------
816 
817     /**
818      * <p>Compares this fraction to another object to test if they are equal.</p>.
819      *
820      * <p>To be equal, both values must be equal. Thus 2/4 is not equal to 1/2.</p>
821      *
822      * @param obj the reference object with which to compare
823      * @return <code>true</code> if this object is equal
824      */
825     @Override
826     public boolean equals(final Object obj) {
827         if (obj == this) {
828             return true;
829         }
830         if (obj instanceof Fraction == false) {
831             return false;
832         }
833         final Fraction other = (Fraction) obj;
834         return getNumerator() == other.getNumerator() && getDenominator() == other.getDenominator();
835     }
836 
837     /**
838      * <p>Gets a hashCode for the fraction.</p>
839      *
840      * @return a hash code value for this object
841      */
842     @Override
843     public int hashCode() {
844         if (hashCode == 0) {
845             // hash code update should be atomic.
846             hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator();
847         }
848         return hashCode;
849     }
850 
851     /**
852      * <p>Compares this object to another based on size.</p>
853      *
854      * <p>Note: this class has a natural ordering that is inconsistent
855      * with equals, because, for example, equals treats 1/2 and 2/4 as
856      * different, whereas compareTo treats them as equal.
857      *
858      * @param other  the object to compare to
859      * @return -1 if this is less, 0 if equal, +1 if greater
860      * @throws ClassCastException if the object is not a <code>Fraction</code>
861      * @throws NullPointerException if the object is <code>null</code>
862      */
863     @Override
864     public int compareTo(final Fraction other) {
865         if (this == other) {
866             return 0;
867         }
868         if (numerator == other.numerator && denominator == other.denominator) {
869             return 0;
870         }
871 
872         // otherwise see which is less
873         final long first = (long) numerator * (long) other.denominator;
874         final long second = (long) other.numerator * (long) denominator;
875         if (first == second) {
876             return 0;
877         } else if (first < second) {
878             return -1;
879         } else {
880             return 1;
881         }
882     }
883 
884     /**
885      * <p>Gets the fraction as a <code>String</code>.</p>
886      *
887      * <p>The format used is '<i>numerator</i>/<i>denominator</i>' always.
888      *
889      * @return a <code>String</code> form of the fraction
890      */
891     @Override
892     public String toString() {
893         if (toString == null) {
894             toString = getNumerator() + "/" + getDenominator();
895         }
896         return toString;
897     }
898 
899     /**
900      * <p>Gets the fraction as a proper <code>String</code> in the format X Y/Z.</p>
901      *
902      * <p>The format used in '<i>wholeNumber</i> <i>numerator</i>/<i>denominator</i>'.
903      * If the whole number is zero it will be omitted. If the numerator is zero,
904      * only the whole number is returned.</p>
905      *
906      * @return a <code>String</code> form of the fraction
907      */
908     public String toProperString() {
909         if (toProperString == null) {
910             if (numerator == 0) {
911                 toProperString = "0";
912             } else if (numerator == denominator) {
913                 toProperString = "1";
914             } else if (numerator == -1 * denominator) {
915                 toProperString = "-1";
916             } else if ((numerator > 0 ? -numerator : numerator) < -denominator) {
917                 // note that we do the magnitude comparison test above with
918                 // NEGATIVE (not positive) numbers, since negative numbers
919                 // have a larger range. otherwise numerator==Integer.MIN_VALUE
920                 // is handled incorrectly.
921                 final int properNumerator = getProperNumerator();
922                 if (properNumerator == 0) {
923                     toProperString = Integer.toString(getProperWhole());
924                 } else {
925                     toProperString = getProperWhole() + " " + properNumerator + "/" + getDenominator();
926                 }
927             } else {
928                 toProperString = getNumerator() + "/" + getDenominator();
929             }
930         }
931         return toProperString;
932     }
933 }