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.math.fraction;
18  
19  import java.io.Serializable;
20  import java.math.BigInteger;
21  
22  import org.apache.commons.math.FieldElement;
23  import org.apache.commons.math.MathRuntimeException;
24  import org.apache.commons.math.util.MathUtils;
25  
26  /**
27   * Representation of a rational number.
28   *
29   * implements Serializable since 2.0
30   * 
31   * @since 1.1
32   * @version $Revision: 795903 $ $Date: 2009-07-20 12:29:46 -0400 (Mon, 20 Jul 2009) $
33   */
34  public class Fraction
35      extends Number
36      implements FieldElement<Fraction>, Comparable<Fraction>, Serializable {
37  
38      /** A fraction representing "2 / 1". */
39      public static final Fraction TWO = new Fraction(2, 1);
40  
41      /** A fraction representing "1". */
42      public static final Fraction ONE = new Fraction(1, 1);
43  
44      /** A fraction representing "0". */
45      public static final Fraction ZERO = new Fraction(0, 1);
46  
47      /** A fraction representing "4/5". */
48      public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
49  
50      /** A fraction representing "1/5". */
51      public static final Fraction ONE_FIFTH = new Fraction(1, 5);
52  
53      /** A fraction representing "1/2". */
54      public static final Fraction ONE_HALF = new Fraction(1, 2);
55  
56      /** A fraction representing "1/4". */
57      public static final Fraction ONE_QUARTER = new Fraction(1, 4);
58  
59      /** A fraction representing "1/3". */
60      public static final Fraction ONE_THIRD = new Fraction(1, 3);
61  
62      /** A fraction representing "3/5". */
63      public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
64  
65      /** A fraction representing "3/4". */
66      public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
67  
68      /** A fraction representing "2/5". */
69      public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
70  
71      /** A fraction representing "2/4". */
72      public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
73  
74      /** A fraction representing "2/3". */
75      public static final Fraction TWO_THIRDS = new Fraction(2, 3);
76  
77      /** A fraction representing "-1 / 1". */
78      public static final Fraction MINUS_ONE = new Fraction(-1, 1);
79  
80      /** Serializable version identifier */
81      private static final long serialVersionUID = 3698073679419233275L;
82  
83      /** The denominator. */
84      private final int denominator;
85      
86      /** The numerator. */
87      private final int numerator;
88  
89      /**
90       * Create a fraction given the double value.
91       * @param value the double value to convert to a fraction.
92       * @throws FractionConversionException if the continued fraction failed to
93       *         converge.
94       */
95      public Fraction(double value) throws FractionConversionException {
96          this(value, 1.0e-5, 100);
97      }
98  
99      /**
100      * Create a fraction given the double value and maximum error allowed.
101      * <p>
102      * References:
103      * <ul>
104      * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
105      * Continued Fraction</a> equations (11) and (22)-(26)</li>
106      * </ul>
107      * </p>
108      * @param value the double value to convert to a fraction.
109      * @param epsilon maximum error allowed.  The resulting fraction is within
110      *        <code>epsilon</code> of <code>value</code>, in absolute terms.
111      * @param maxIterations maximum number of convergents
112      * @throws FractionConversionException if the continued fraction failed to
113      *         converge.
114      */
115     public Fraction(double value, double epsilon, int maxIterations)
116         throws FractionConversionException
117     {
118         this(value, epsilon, Integer.MAX_VALUE, maxIterations);
119     }
120 
121     /**
122      * Create a fraction given the double value and maximum denominator.
123      * <p>
124      * References:
125      * <ul>
126      * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
127      * Continued Fraction</a> equations (11) and (22)-(26)</li>
128      * </ul>
129      * </p>
130      * @param value the double value to convert to a fraction.
131      * @param maxDenominator The maximum allowed value for denominator
132      * @throws FractionConversionException if the continued fraction failed to
133      *         converge
134      */
135     public Fraction(double value, int maxDenominator)
136         throws FractionConversionException
137     {
138        this(value, 0, maxDenominator, 100);
139     }
140 
141     /**
142      * Create a fraction given the double value and either the maximum error
143      * allowed or the maximum number of denominator digits.
144      * <p>
145      *
146      * NOTE: This constructor is called with EITHER
147      *   - a valid epsilon value and the maxDenominator set to Integer.MAX_VALUE
148      *     (that way the maxDenominator has no effect).
149      * OR
150      *   - a valid maxDenominator value and the epsilon value set to zero
151      *     (that way epsilon only has effect if there is an exact match before
152      *     the maxDenominator value is reached).
153      * </p><p>
154      *
155      * It has been done this way so that the same code can be (re)used for both
156      * scenarios. However this could be confusing to users if it were part of
157      * the public API and this constructor should therefore remain PRIVATE.
158      * </p>
159      *
160      * See JIRA issue ticket MATH-181 for more details:
161      *
162      *     https://issues.apache.org/jira/browse/MATH-181
163      *
164      * @param value the double value to convert to a fraction.
165      * @param epsilon maximum error allowed.  The resulting fraction is within
166      *        <code>epsilon</code> of <code>value</code>, in absolute terms.
167      * @param maxDenominator maximum denominator value allowed.
168      * @param maxIterations maximum number of convergents
169      * @throws FractionConversionException if the continued fraction failed to
170      *         converge.
171      */
172     private Fraction(double value, double epsilon, int maxDenominator, int maxIterations)
173         throws FractionConversionException
174     {
175         long overflow = Integer.MAX_VALUE;
176         double r0 = value;
177         long a0 = (long)Math.floor(r0);
178         if (a0 > overflow) {
179             throw new FractionConversionException(value, a0, 1l);
180         }
181 
182         // check for (almost) integer arguments, which should not go
183         // to iterations.
184         if (Math.abs(a0 - value) < epsilon) {
185             this.numerator = (int) a0;
186             this.denominator = 1;
187             return;
188         }
189 
190         long p0 = 1;
191         long q0 = 0;
192         long p1 = a0;
193         long q1 = 1;
194 
195         long p2 = 0;
196         long q2 = 1;
197 
198         int n = 0;
199         boolean stop = false;
200         do {
201             ++n;
202             double r1 = 1.0 / (r0 - a0);
203             long a1 = (long)Math.floor(r1);
204             p2 = (a1 * p1) + p0;
205             q2 = (a1 * q1) + q0;
206             if ((p2 > overflow) || (q2 > overflow)) {
207                 throw new FractionConversionException(value, p2, q2);
208             }
209             
210             double convergent = (double)p2 / (double)q2;
211             if (n < maxIterations && Math.abs(convergent - value) > epsilon && q2 < maxDenominator) {
212                 p0 = p1;
213                 p1 = p2;
214                 q0 = q1;
215                 q1 = q2;
216                 a0 = a1;
217                 r0 = r1;
218             } else {
219                 stop = true;
220             }
221         } while (!stop);
222 
223         if (n >= maxIterations) {
224             throw new FractionConversionException(value, maxIterations);
225         }
226         
227         if (q2 < maxDenominator) {
228             this.numerator = (int) p2;
229             this.denominator = (int) q2;
230         } else {
231             this.numerator = (int) p1;
232             this.denominator = (int) q1;
233         }
234 
235     }
236     
237     /**
238      * Create a fraction from an int. 
239      * The fraction is num / 1.
240      * @param num the numerator.
241      */
242     public Fraction(int num) {
243         this(num, 1);
244     }
245     
246     /**
247      * Create a fraction given the numerator and denominator.  The fraction is
248      * reduced to lowest terms.
249      * @param num the numerator.
250      * @param den the denominator.
251      * @throws ArithmeticException if the denominator is <code>zero</code>
252      */
253     public Fraction(int num, int den) {
254         if (den == 0) {
255             throw MathRuntimeException.createArithmeticException("zero denominator in fraction {0}/{1}",
256                                                                  num, den);
257         }
258         if (den < 0) {
259             if (num == Integer.MIN_VALUE || den == Integer.MIN_VALUE) {
260                 throw MathRuntimeException.createArithmeticException("overflow in fraction {0}/{1}, cannot negate",
261                                                                      num, den);
262             }
263             num = -num;
264             den = -den;
265         }
266         // reduce numerator and denominator by greatest common denominator.
267         final int d = MathUtils.gcd(num, den);
268         if (d > 1) {
269             num /= d;
270             den /= d;
271         }
272         
273         // move sign to numerator.
274         if (den < 0) {
275             num = -num;
276             den = -den;
277         }
278         this.numerator   = num;
279         this.denominator = den;
280     }
281     
282     /**
283      * Returns the absolute value of this fraction.
284      * @return the absolute value.
285      */
286     public Fraction abs() {
287         Fraction ret;
288         if (numerator >= 0) {
289             ret = this;
290         } else {
291             ret = negate();
292         }
293         return ret;        
294     }
295     
296     /**
297      * Compares this object to another based on size.
298      * @param object the object to compare to
299      * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
300      *         than <tt>object</tt>, 0 if they are equal.
301      */
302     public int compareTo(Fraction object) {
303         long nOd = ((long) numerator) * object.denominator;
304         long dOn = ((long) denominator) * object.numerator;
305         return (nOd < dOn) ? -1 : ((nOd > dOn) ? +1 : 0);
306     }
307 
308     /**
309      * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
310      * the numerator divided by denominator.
311      * @return the fraction as a <tt>double</tt>
312      */
313     @Override
314     public double doubleValue() {
315         return (double)numerator / (double)denominator;
316     }
317     
318     /**
319      * Test for the equality of two fractions.  If the lowest term
320      * numerator and denominators are the same for both fractions, the two
321      * fractions are considered to be equal.
322      * @param other fraction to test for equality to this fraction
323      * @return true if two fractions are equal, false if object is
324      *         <tt>null</tt>, not an instance of {@link Fraction}, or not equal
325      *         to this fraction instance.
326      */
327     @Override
328     public boolean equals(Object other) {
329         boolean ret;
330         
331         if (this == other) { 
332             ret = true;
333         } else if (other == null) {
334             ret = false;
335         } else {
336             try {
337                 // since fractions are always in lowest terms, numerators and
338                 // denominators can be compared directly for equality.
339                 Fraction rhs = (Fraction)other;
340                 ret = (numerator == rhs.numerator) &&
341                     (denominator == rhs.denominator);
342             } catch (ClassCastException ex) {
343                 // ignore exception
344                 ret = false;
345             }
346         }
347         
348         return ret;
349     }
350     
351     /**
352      * Gets the fraction as a <tt>float</tt>. This calculates the fraction as
353      * the numerator divided by denominator.
354      * @return the fraction as a <tt>float</tt>
355      */
356     @Override
357     public float floatValue() {
358         return (float)doubleValue();
359     }
360     
361     /**
362      * Access the denominator.
363      * @return the denominator.
364      */
365     public int getDenominator() {
366         return denominator;
367     }
368     
369     /**
370      * Access the numerator.
371      * @return the numerator.
372      */
373     public int getNumerator() {
374         return numerator;
375     }
376     
377     /**
378      * Gets a hashCode for the fraction.
379      * @return a hash code value for this object
380      */
381     @Override
382     public int hashCode() {
383         return 37 * (37 * 17 + getNumerator()) + getDenominator();
384     }
385     
386     /**
387      * Gets the fraction as an <tt>int</tt>. This returns the whole number part
388      * of the fraction.
389      * @return the whole number fraction part
390      */
391     @Override
392     public int intValue() {
393         return (int)doubleValue();
394     }
395     
396     /**
397      * Gets the fraction as a <tt>long</tt>. This returns the whole number part
398      * of the fraction.
399      * @return the whole number fraction part
400      */
401     @Override
402     public long longValue() {
403         return (long)doubleValue();
404     }
405     
406     /**
407      * Return the additive inverse of this fraction.
408      * @return the negation of this fraction.
409      */
410     public Fraction negate() {
411         if (numerator==Integer.MIN_VALUE) {
412             throw MathRuntimeException.createArithmeticException("overflow in fraction {0}/{1}, cannot negate",
413                                                                  numerator, denominator);
414         }
415         return new Fraction(-numerator, denominator);
416     }
417 
418     /**
419      * Return the multiplicative inverse of this fraction.
420      * @return the reciprocal fraction
421      */
422     public Fraction reciprocal() {
423         return new Fraction(denominator, numerator);
424     }
425     
426     /**
427      * <p>Adds the value of this fraction to another, returning the result in reduced form.
428      * The algorithm follows Knuth, 4.5.1.</p>
429      *
430      * @param fraction  the fraction to add, must not be <code>null</code>
431      * @return a <code>Fraction</code> instance with the resulting values
432      * @throws IllegalArgumentException if the fraction is <code>null</code>
433      * @throws ArithmeticException if the resulting numerator or denominator exceeds
434      *  <code>Integer.MAX_VALUE</code>
435      */
436     public Fraction add(Fraction fraction) {
437         return addSub(fraction, true /* add */);
438     }
439 
440     /**
441      * Add an integer to the fraction.
442      * @param i the <tt>integer</tt> to add.
443      * @return this + i
444      */
445     public Fraction add(final int i) {
446         return new Fraction(numerator + i * denominator, denominator);
447     }
448 
449     /**
450      * <p>Subtracts the value of another fraction from the value of this one, 
451      * returning the result in reduced form.</p>
452      *
453      * @param fraction  the fraction to subtract, must not be <code>null</code>
454      * @return a <code>Fraction</code> instance with the resulting values
455      * @throws IllegalArgumentException if the fraction is <code>null</code>
456      * @throws ArithmeticException if the resulting numerator or denominator
457      *   cannot be represented in an <code>int</code>.
458      */
459     public Fraction subtract(Fraction fraction) {
460         return addSub(fraction, false /* subtract */);
461     }
462 
463     /**
464      * Subtract an integer from the fraction.
465      * @param i the <tt>integer</tt> to subtract.
466      * @return this - i
467      */
468     public Fraction subtract(final int i) {
469         return new Fraction(numerator - i * denominator, denominator);
470     }
471 
472     /** 
473      * Implement add and subtract using algorithm described in Knuth 4.5.1.
474      * 
475      * @param fraction the fraction to subtract, must not be <code>null</code>
476      * @param isAdd true to add, false to subtract
477      * @return a <code>Fraction</code> instance with the resulting values
478      * @throws IllegalArgumentException if the fraction is <code>null</code>
479      * @throws ArithmeticException if the resulting numerator or denominator
480      *   cannot be represented in an <code>int</code>.
481      */
482     private Fraction addSub(Fraction fraction, boolean isAdd) {
483         if (fraction == null) {
484             throw MathRuntimeException.createIllegalArgumentException("null fraction");
485         }
486         // zero is identity for addition.
487         if (numerator == 0) {
488             return isAdd ? fraction : fraction.negate();
489         }
490         if (fraction.numerator == 0) {
491             return this;
492         }     
493         // if denominators are randomly distributed, d1 will be 1 about 61%
494         // of the time.
495         int d1 = MathUtils.gcd(denominator, fraction.denominator);
496         if (d1==1) {
497             // result is ( (u*v' +/- u'v) / u'v')
498             int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
499             int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
500             return new Fraction
501                 (isAdd ? MathUtils.addAndCheck(uvp, upv) : 
502                  MathUtils.subAndCheck(uvp, upv),
503                  MathUtils.mulAndCheck(denominator, fraction.denominator));
504         }
505         // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
506         // exercise 7.  we're going to use a BigInteger.
507         // t = u(v'/d1) +/- v(u'/d1)
508         BigInteger uvp = BigInteger.valueOf(numerator)
509         .multiply(BigInteger.valueOf(fraction.denominator/d1));
510         BigInteger upv = BigInteger.valueOf(fraction.numerator)
511         .multiply(BigInteger.valueOf(denominator/d1));
512         BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
513         // but d2 doesn't need extra precision because
514         // d2 = gcd(t,d1) = gcd(t mod d1, d1)
515         int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
516         int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1);
517 
518         // result is (t/d2) / (u'/d1)(v'/d2)
519         BigInteger w = t.divide(BigInteger.valueOf(d2));
520         if (w.bitLength() > 31) {
521             throw MathRuntimeException.createArithmeticException("overflow, numerator too large after multiply: {0}",
522                                                                  w);
523         }
524         return new Fraction (w.intValue(), 
525                 MathUtils.mulAndCheck(denominator/d1, 
526                         fraction.denominator/d2));
527     }
528 
529     /**
530      * <p>Multiplies the value of this fraction by another, returning the 
531      * result in reduced form.</p>
532      *
533      * @param fraction  the fraction to multiply by, must not be <code>null</code>
534      * @return a <code>Fraction</code> instance with the resulting values
535      * @throws IllegalArgumentException if the fraction is <code>null</code>
536      * @throws ArithmeticException if the resulting numerator or denominator exceeds
537      *  <code>Integer.MAX_VALUE</code>
538      */
539     public Fraction multiply(Fraction fraction) {
540         if (fraction == null) {
541             throw MathRuntimeException.createIllegalArgumentException("null fraction");
542         }
543         if (numerator == 0 || fraction.numerator == 0) {
544             return ZERO;
545         }
546         // knuth 4.5.1
547         // make sure we don't overflow unless the result *must* overflow.
548         int d1 = MathUtils.gcd(numerator, fraction.denominator);
549         int d2 = MathUtils.gcd(fraction.numerator, denominator);
550         return getReducedFraction
551         (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
552                 MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
553     }
554 
555     /**
556      * Multiply the fraction by an integer.
557      * @param i the <tt>integer</tt> to multiply by.
558      * @return this * i
559      */
560     public Fraction multiply(final int i) {
561         return new Fraction(numerator * i, denominator);
562     }
563 
564     /**
565      * <p>Divide the value of this fraction by another.</p>
566      *
567      * @param fraction  the fraction to divide by, must not be <code>null</code>
568      * @return a <code>Fraction</code> instance with the resulting values
569      * @throws IllegalArgumentException if the fraction is <code>null</code>
570      * @throws ArithmeticException if the fraction to divide by is zero
571      * @throws ArithmeticException if the resulting numerator or denominator exceeds
572      *  <code>Integer.MAX_VALUE</code>
573      */
574     public Fraction divide(Fraction fraction) {
575         if (fraction == null) {
576             throw MathRuntimeException.createIllegalArgumentException("null fraction");
577         }
578         if (fraction.numerator == 0) {
579             throw MathRuntimeException.createArithmeticException(
580                     "the fraction to divide by must not be zero: {0}/{1}",
581                     fraction.numerator, fraction.denominator);
582         }
583         return multiply(fraction.reciprocal());
584     }
585 
586     /**
587      * Divide the fraction by an integer.
588      * @param i the <tt>integer</tt> to divide by.
589      * @return this * i
590      */
591     public Fraction divide(final int i) {
592         return new Fraction(numerator, denominator * i);
593     }
594 
595     /**
596      * <p>Creates a <code>Fraction</code> instance with the 2 parts
597      * of a fraction Y/Z.</p>
598      *
599      * <p>Any negative signs are resolved to be on the numerator.</p>
600      *
601      * @param numerator  the numerator, for example the three in 'three sevenths'
602      * @param denominator  the denominator, for example the seven in 'three sevenths'
603      * @return a new fraction instance, with the numerator and denominator reduced
604      * @throws ArithmeticException if the denominator is <code>zero</code>
605      */
606     public static Fraction getReducedFraction(int numerator, int denominator) {
607         if (denominator == 0) {
608             throw MathRuntimeException.createArithmeticException(
609                     "zero denominator in fraction {0}/{1}",
610                     numerator, denominator);
611         }
612         if (numerator==0) {
613             return ZERO; // normalize zero.
614         }
615         // allow 2^k/-2^31 as a valid fraction (where k>0)
616         if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
617             numerator/=2; denominator/=2;
618         }
619         if (denominator < 0) {
620             if (numerator==Integer.MIN_VALUE ||
621                     denominator==Integer.MIN_VALUE) {
622                 throw MathRuntimeException.createArithmeticException(
623                         "overflow in fraction {0}/{1}, cannot negate",
624                         numerator, denominator);
625             }
626             numerator = -numerator;
627             denominator = -denominator;
628         }
629         // simplify fraction.
630         int gcd = MathUtils.gcd(numerator, denominator);
631         numerator /= gcd;
632         denominator /= gcd;
633         return new Fraction(numerator, denominator);
634     }
635 
636     /**
637      * <p>
638      * Returns the <code>String</code> representing this fraction, ie
639      * "num / dem" or just "num" if the denominator is one.
640      * </p>
641      * 
642      * @return a string representation of the fraction.
643      * @see java.lang.Object#toString()
644      */
645     @Override
646     public String toString() {
647         String str = null;
648         if (denominator == 1) {
649             str = Integer.toString(numerator);
650         } else if (numerator == 0) {
651             str = "0";
652         } else {
653             str = numerator + " / " + denominator;
654         }
655         return str;
656     }
657 
658     /** {@inheritDoc} */
659     public FractionField getField() {
660         return FractionField.getInstance();
661     }
662 
663 }