Fraction


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