Fraction


1   /*
2    * Copyright 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.math.fraction;
17  
18  import java.math.BigInteger  ;
19  import org.apache.commons.math.ConvergenceException;
20  import org.apache.commons.math.util.MathUtils;
21  
22  /**
23   * Representation of a rational number.
24   *
25   * @since 1.1
26   * @version $Revision$ $Date: 2005-06-25 18:52:37 -0700 (Sat, 25 Jun 2005) $
27   */
28  public class Fraction extends Number   implements Comparable   {
29  
30      /** A fraction representing "1 / 1". */
31      public static final Fraction ONE = new Fraction(1, 1);
32  
33      /** A fraction representing "0 / 1". */
34      public static final Fraction ZERO = new Fraction(0, 1);
35      
36      /** Serializable version identifier */
37      static final long serialVersionUID = 65382027393090L;
38      
39      /** The denominator. */
40      private int denominator;
41      
42      /** The numerator. */
43      private int numerator;
44  
45      /**
46       * Create a fraction given the double value.
47       * @param value the double value to convert to a fraction.
48       * @throws ConvergenceException if the continued fraction failed to
49       *         converge.
50       */
51      public Fraction(double value) throws ConvergenceException {
52          this(value, 1.0e-5, 100);
53      }
54  
55      /**
56       * Create a fraction given the double value.
57       * <p>
58       * References:
59       * <ul>
60       * <li><a HREF="http://mathworld.wolfram.com/ContinuedFraction.html">
61       * Continued Fraction</a> equations (11) and (22)-(26)</li>
62       * </ul>
63       * </p>
64       * @param value the double value to convert to a fraction.
65       * @param epsilon maximum error allowed.  The resulting fraction is within
66       *        <code>epsilon</code> of <code>value</code>, in absolute terms.
67       * @param maxIterations maximum number of convergents
68       * @throws ConvergenceException if the continued fraction failed to
69       *         converge.
70       */
71      public Fraction(double value, double epsilon, int maxIterations)
72          throws ConvergenceException
73      {
74          double r0 = value;
75          int a0 = (int)Math.floor(r0);
76  
77          // check for (almost) integer arguments, which should not go
78          // to iterations.
79          if (Math.abs(a0 - value) < epsilon) {
80              this.numerator = a0;
81              this.denominator = 1;
82              return;
83          }
84          
85          int p0 = 1;
86          int q0 = 0;
87          int p1 = a0;
88          int q1 = 1;
89  
90          int p2 = 0;
91          int q2 = 1;
92  
93          int n = 0;
94          boolean stop = false;
95          do {
96              ++n;
97              double r1 = 1.0 / (r0 - a0);
98              int a1 = (int)Math.floor(r1);
99              p2 = (a1 * p1) + p0;
100             q2 = (a1 * q1) + q0;
101             
102             double convergent = (double)p2 / (double)q2;
103             if (n < maxIterations && Math.abs(convergent - value) > epsilon) {
104                 p0 = p1;
105                 p1 = p2;
106                 q0 = q1;
107                 q1 = q2;
108                 a0 = a1;
109                 r0 = r1;
110             } else {
111                 stop = true;
112             }
113         } while (!stop);
114 
115         if (n >= maxIterations) {
116             throw new ConvergenceException(
117                     "Unable to convert double to fraction");
118         }
119         
120         this.numerator = p2;
121         this.denominator = q2;
122         reduce();
123     }
124     
125     /**
126      * Create a fraction given the numerator and denominator.  The fraction is
127      * reduced to lowest terms.
128      * @param num the numerator.
129      * @param den the denominator.
130      * @throws ArithmeticException if the denomiator is <code>zero</code>
131      */
132     public Fraction(int num, int den) {
133         super();
134         if (den == 0) {
135             throw new ArithmeticException  ("The denominator must not be zero");
136         }
137         if (den < 0) {
138             if (num == Integer.MIN_VALUE ||
139                     den == Integer.MIN_VALUE) {
140                 throw new ArithmeticException  ("overflow: can't negate");
141             }
142             num = -num;
143             den = -den;
144         }
145         this.numerator = num;
146         this.denominator = den;
147         reduce();
148     }
149     
150     /**
151      * Returns the absolute value of this fraction.
152      * @return the absolute value.
153      */
154     public Fraction abs() {
155         Fraction ret;
156         if (numerator >= 0) {
157             ret = this;
158         } else {
159             ret = negate();
160         }
161         return ret;        
162     }
163     
164     /**
165      * Compares this object to another based on size.
166      * @param object the object to compare to
167      * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
168      *         than <tt>object</tt>, 0 if they are equal.
169      */
170     public int compareTo(Object   object) {
171         int ret = 0;
172         
173         if (this != object) { 
174             Fraction other = (Fraction)object;
175             double first = doubleValue();
176             double second = other.doubleValue();
177             
178             if (first < second) {
179                 ret = -1;
180             } else if (first > second) {
181                 ret = 1;
182             }
183         }
184         
185         return ret;
186     }
187     
188     /**
189      * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
190      * the numerator divided by denominator.
191      * @return the fraction as a <tt>double</tt>
192      */
193     public double doubleValue() {
194         return (double)numerator / (double)denominator;
195     }
196     
197     /**
198      * Test for the equality of two fractions.  If the lowest term
199      * numerator and denominators are the same for both fractions, the two
200      * fractions are considered to be equal.
201      * @param other fraction to test for equality to this fraction
202      * @return true if two fractions are equal, false if object is
203      *         <tt>null</tt>, not an instance of {@link Fraction}, or not equal
204      *         to this fraction instance.
205      */
206     public boolean equals(Object   other) {
207         boolean ret;
208         
209         if (this == other) { 
210             ret = true;
211         } else if (other == null) {
212             ret = false;
213         } else {
214             try {
215                 // since fractions are always in lowest terms, numerators and
216                 // denominators can be compared directly for equality.
217                 Fraction rhs = (Fraction)other;
218                 ret = (numerator == rhs.numerator) &&
219                     (denominator == rhs.denominator);
220             } catch (ClassCastException   ex) {
221                 // ignore exception
222                 ret = false;
223             }
224         }
225         
226         return ret;
227     }
228     
229     /**
230      * Gets the fraction as a <tt>float</tt>. This calculates the fraction as
231      * the numerator divided by denominator.
232      * @return the fraction as a <tt>float</tt>
233      */
234     public float floatValue() {
235         return (float)doubleValue();
236     }
237     
238     /**
239      * Access the denominator.
240      * @return the denominator.
241      */
242     public int getDenominator() {
243         return denominator;
244     }
245     
246     /**
247      * Access the numerator.
248      * @return the numerator.
249      */
250     public int getNumerator() {
251         return numerator;
252     }
253     
254     /**
255      * Gets a hashCode for the fraction.
256      * @return a hash code value for this object
257      */
258     public int hashCode() {
259         return 37 * (37 * 17 + getNumerator()) + getDenominator();
260     }
261     
262     /**
263      * Gets the fraction as an <tt>int</tt>. This returns the whole number part
264      * of the fraction.
265      * @return the whole number fraction part
266      */
267     public int intValue() {
268         return (int)doubleValue();
269     }
270     
271     /**
272      * Gets the fraction as a <tt>long</tt>. This returns the whole number part
273      * of the fraction.
274      * @return the whole number fraction part
275      */
276     public long longValue() {
277         return (long)doubleValue();
278     }
279     
280     /**
281      * Return the additive inverse of this fraction.
282      * @return the negation of this fraction.
283      */
284     public Fraction negate() {
285         if (numerator==Integer.MIN_VALUE) {
286             throw new ArithmeticException  ("overflow: too large to negate");
287         }
288         return new Fraction(-numerator, denominator);
289     }
290 
291     /**
292      * Return the multiplicative inverse of this fraction.
293      * @return the reciprocal fraction
294      */
295     public Fraction reciprocal() {
296         return new Fraction(denominator, numerator);
297     }
298     
299     /**
300      * <p>Adds the value of this fraction to another, returning the result in reduced form.
301      * The algorithm follows Knuth, 4.5.1.</p>
302      *
303      * @param fraction  the fraction to add, must not be <code>null</code>
304      * @return a <code>Fraction</code> instance with the resulting values
305      * @throws IllegalArgumentException if the fraction is <code>null</code>
306      * @throws ArithmeticException if the resulting numerator or denominator exceeds
307      *  <code>Integer.MAX_VALUE</code>
308      */
309     public Fraction add(Fraction fraction) {
310         return addSub(fraction, true /* add */);
311     }
312 
313     /**
314      * <p>Subtracts the value of another fraction from the value of this one, 
315      * returning the result in reduced form.</p>
316      *
317      * @param fraction  the fraction to subtract, must not be <code>null</code>
318      * @return a <code>Fraction</code> instance with the resulting values
319      * @throws IllegalArgumentException if the fraction is <code>null</code>
320      * @throws ArithmeticException if the resulting numerator or denominator
321      *   cannot be represented in an <code>int</code>.
322      */
323     public Fraction subtract(Fraction fraction) {
324         return addSub(fraction, false /* subtract */);
325     }
326 
327     /** 
328      * Implement add and subtract using algorithm described in Knuth 4.5.1.
329      * 
330      * @param fraction the fraction to subtract, must not be <code>null</code>
331      * @param isAdd true to add, false to subtract
332      * @return a <code>Fraction</code> instance with the resulting values
333      * @throws IllegalArgumentException if the fraction is <code>null</code>
334      * @throws ArithmeticException if the resulting numerator or denominator
335      *   cannot be represented in an <code>int</code>.
336      */
337     private Fraction addSub(Fraction fraction, boolean isAdd) {
338         if (fraction == null) {
339             throw new IllegalArgumentException  ("The fraction must not be null");
340         }
341         // zero is identity for addition.
342         if (numerator == 0) {
343             return isAdd ? fraction : fraction.negate();
344         }
345         if (fraction.numerator == 0) {
346             return this;
347         }     
348         // if denominators are randomly distributed, d1 will be 1 about 61%
349         // of the time.
350         int d1 = MathUtils.gcd(denominator, fraction.denominator);
351         if (d1==1) {
352             // result is ( (u*v' +/- u'v) / u'v')
353             int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
354             int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
355             return new Fraction
356                 (isAdd ? MathUtils.addAndCheck(uvp, upv) : 
357                  MathUtils.subAndCheck(uvp, upv),
358                  MathUtils.mulAndCheck(denominator, fraction.denominator));
359         }
360         // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
361         // exercise 7.  we're going to use a BigInteger.
362         // t = u(v'/d1) +/- v(u'/d1)
363         BigInteger   uvp = BigInteger.valueOf(numerator)
364         .multiply(BigInteger.valueOf(fraction.denominator/d1));
365         BigInteger   upv = BigInteger.valueOf(fraction.numerator)
366         .multiply(BigInteger.valueOf(denominator/d1));
367         BigInteger   t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
368         // but d2 doesn't need extra precision because
369         // d2 = gcd(t,d1) = gcd(t mod d1, d1)
370         int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
371         int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1);
372 
373         // result is (t/d2) / (u'/d1)(v'/d2)
374         BigInteger   w = t.divide(BigInteger.valueOf(d2));
375         if (w.bitLength() > 31) {
376             throw new ArithmeticException  
377             ("overflow: numerator too large after multiply");
378         }
379         return new Fraction (w.intValue(), 
380                 MathUtils.mulAndCheck(denominator/d1, 
381                         fraction.denominator/d2));
382     }
383 
384     /**
385      * <p>Multiplies the value of this fraction by another, returning the 
386      * result in reduced form.</p>
387      *
388      * @param fraction  the fraction to multiply by, must not be <code>null</code>
389      * @return a <code>Fraction</code> instance with the resulting values
390      * @throws IllegalArgumentException if the fraction is <code>null</code>
391      * @throws ArithmeticException if the resulting numerator or denominator exceeds
392      *  <code>Integer.MAX_VALUE</code>
393      */
394     public Fraction multiply(Fraction fraction) {
395         if (fraction == null) {
396             throw new IllegalArgumentException  ("The fraction must not be null");
397         }
398         if (numerator == 0 || fraction.numerator == 0) {
399             return ZERO;
400         }
401         // knuth 4.5.1
402         // make sure we don't overflow unless the result *must* overflow.
403         int d1 = MathUtils.gcd(numerator, fraction.denominator);
404         int d2 = MathUtils.gcd(fraction.numerator, denominator);
405         return getReducedFraction
406         (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
407                 MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
408     }
409 
410     /**
411      * <p>Divide the value of this fraction by another.</p>
412      *
413      * @param fraction  the fraction to divide by, must not be <code>null</code>
414      * @return a <code>Fraction</code> instance with the resulting values
415      * @throws IllegalArgumentException if the fraction is <code>null</code>
416      * @throws ArithmeticException if the fraction to divide by is zero
417      * @throws ArithmeticException if the resulting numerator or denominator exceeds
418      *  <code>Integer.MAX_VALUE</code>
419      */
420     public Fraction divide(Fraction fraction) {
421         if (fraction == null) {
422             throw new IllegalArgumentException  ("The fraction must not be null");
423         }
424         if (fraction.numerator == 0) {
425             throw new ArithmeticException  ("The fraction to divide by must not be zero");
426         }
427         return multiply(fraction.reciprocal());
428     }
429     
430     /**
431      * <p>Creates a <code>Fraction</code> instance with the 2 parts
432      * of a fraction Y/Z.</p>
433      *
434      * <p>Any negative signs are resolved to be on the numerator.</p>
435      *
436      * @param numerator  the numerator, for example the three in 'three sevenths'
437      * @param denominator  the denominator, for example the seven in 'three sevenths'
438      * @return a new fraction instance, with the numerator and denominator reduced
439      * @throws ArithmeticException if the denominator is <code>zero</code>
440      */
441     public static Fraction getReducedFraction(int numerator, int denominator) {
442         if (denominator == 0) {
443             throw new ArithmeticException  ("The denominator must not be zero");
444         }
445         if (numerator==0) {
446             return ZERO; // normalize zero.
447         }
448         // allow 2^k/-2^31 as a valid fraction (where k>0)
449         if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
450             numerator/=2; denominator/=2;
451         }
452         if (denominator < 0) {
453             if (numerator==Integer.MIN_VALUE ||
454                     denominator==Integer.MIN_VALUE) {
455                 throw new ArithmeticException  ("overflow: can't negate");
456             }
457             numerator = -numerator;
458             denominator = -denominator;
459         }
460         // simplify fraction.
461         int gcd = MathUtils.gcd(numerator, denominator);
462         numerator /= gcd;
463         denominator /= gcd;
464         return new Fraction(numerator, denominator);
465     }
466     
467     /**
468      * Reduce this fraction to lowest terms.  This is accomplished by dividing
469      * both numerator and denominator by their greatest common divisor.
470      */
471     private void reduce() {
472         // reduce numerator and denominator by greatest common denominator.
473         int d = MathUtils.gcd(numerator, denominator);
474         if (d > 1) {
475             numerator /= d;
476             denominator /= d;
477         }
478 
479         // move sign to numerator.
480         if (denominator < 0) {
481             numerator *= -1;
482             denominator *= -1;
483         }
484     }
485 }
486
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags