001: /*
002: * Copyright 2005 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.math.fraction;
017:
018: import java.math.BigInteger;
019: import org.apache.commons.math.ConvergenceException;
020: import org.apache.commons.math.util.MathUtils;
021:
022: /**
023: * Representation of a rational number.
024: *
025: * @since 1.1
026: * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
027: */
028: public class Fraction extends Number implements Comparable {
029:
030: /** A fraction representing "1 / 1". */
031: public static final Fraction ONE = new Fraction(1, 1);
032:
033: /** A fraction representing "0 / 1". */
034: public static final Fraction ZERO = new Fraction(0, 1);
035:
036: /** Serializable version identifier */
037: private static final long serialVersionUID = 65382027393090L;
038:
039: /** The denominator. */
040: private int denominator;
041:
042: /** The numerator. */
043: private int numerator;
044:
045: /**
046: * Create a fraction given the double value.
047: * @param value the double value to convert to a fraction.
048: * @throws ConvergenceException if the continued fraction failed to
049: * converge.
050: */
051: public Fraction(double value) throws ConvergenceException {
052: this (value, 1.0e-5, 100);
053: }
054:
055: /**
056: * Create a fraction given the double value.
057: * <p>
058: * References:
059: * <ul>
060: * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
061: * Continued Fraction</a> equations (11) and (22)-(26)</li>
062: * </ul>
063: * </p>
064: * @param value the double value to convert to a fraction.
065: * @param epsilon maximum error allowed. The resulting fraction is within
066: * <code>epsilon</code> of <code>value</code>, in absolute terms.
067: * @param maxIterations maximum number of convergents
068: * @throws ConvergenceException if the continued fraction failed to
069: * converge.
070: */
071: public Fraction(double value, double epsilon, int maxIterations)
072: throws ConvergenceException {
073: double r0 = value;
074: int a0 = (int) Math.floor(r0);
075:
076: // check for (almost) integer arguments, which should not go
077: // to iterations.
078: if (Math.abs(a0 - value) < epsilon) {
079: this .numerator = a0;
080: this .denominator = 1;
081: return;
082: }
083:
084: int p0 = 1;
085: int q0 = 0;
086: int p1 = a0;
087: int q1 = 1;
088:
089: int p2 = 0;
090: int q2 = 1;
091:
092: int n = 0;
093: boolean stop = false;
094: do {
095: ++n;
096: double r1 = 1.0 / (r0 - a0);
097: int a1 = (int) Math.floor(r1);
098: p2 = (a1 * p1) + p0;
099: q2 = (a1 * q1) + q0;
100:
101: double convergent = (double) p2 / (double) q2;
102: if (n < maxIterations
103: && 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(
136: "The denominator must not be zero");
137: }
138: if (den < 0) {
139: if (num == Integer.MIN_VALUE || 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(
287: "overflow: too large to negate");
288: }
289: return new Fraction(-numerator, denominator);
290: }
291:
292: /**
293: * Return the multiplicative inverse of this fraction.
294: * @return the reciprocal fraction
295: */
296: public Fraction reciprocal() {
297: return new Fraction(denominator, numerator);
298: }
299:
300: /**
301: * <p>Adds the value of this fraction to another, returning the result in reduced form.
302: * The algorithm follows Knuth, 4.5.1.</p>
303: *
304: * @param fraction the fraction to add, must not be <code>null</code>
305: * @return a <code>Fraction</code> instance with the resulting values
306: * @throws IllegalArgumentException if the fraction is <code>null</code>
307: * @throws ArithmeticException if the resulting numerator or denominator exceeds
308: * <code>Integer.MAX_VALUE</code>
309: */
310: public Fraction add(Fraction fraction) {
311: return addSub(fraction, true /* add */);
312: }
313:
314: /**
315: * <p>Subtracts the value of another fraction from the value of this one,
316: * returning the result in reduced form.</p>
317: *
318: * @param fraction the fraction to subtract, must not be <code>null</code>
319: * @return a <code>Fraction</code> instance with the resulting values
320: * @throws IllegalArgumentException if the fraction is <code>null</code>
321: * @throws ArithmeticException if the resulting numerator or denominator
322: * cannot be represented in an <code>int</code>.
323: */
324: public Fraction subtract(Fraction fraction) {
325: return addSub(fraction, false /* subtract */);
326: }
327:
328: /**
329: * Implement add and subtract using algorithm described in Knuth 4.5.1.
330: *
331: * @param fraction the fraction to subtract, must not be <code>null</code>
332: * @param isAdd true to add, false to subtract
333: * @return a <code>Fraction</code> instance with the resulting values
334: * @throws IllegalArgumentException if the fraction is <code>null</code>
335: * @throws ArithmeticException if the resulting numerator or denominator
336: * cannot be represented in an <code>int</code>.
337: */
338: private Fraction addSub(Fraction fraction, boolean isAdd) {
339: if (fraction == null) {
340: throw new IllegalArgumentException(
341: "The fraction must not be null");
342: }
343: // zero is identity for addition.
344: if (numerator == 0) {
345: return isAdd ? fraction : fraction.negate();
346: }
347: if (fraction.numerator == 0) {
348: return this ;
349: }
350: // if denominators are randomly distributed, d1 will be 1 about 61%
351: // of the time.
352: int d1 = MathUtils.gcd(denominator, fraction.denominator);
353: if (d1 == 1) {
354: // result is ( (u*v' +/- u'v) / u'v')
355: int uvp = MathUtils.mulAndCheck(numerator,
356: fraction.denominator);
357: int upv = MathUtils.mulAndCheck(fraction.numerator,
358: denominator);
359: return new Fraction(isAdd ? MathUtils.addAndCheck(uvp, upv)
360: : MathUtils.subAndCheck(uvp, upv), MathUtils
361: .mulAndCheck(denominator, fraction.denominator));
362: }
363: // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
364: // exercise 7. we're going to use a BigInteger.
365: // t = u(v'/d1) +/- v(u'/d1)
366: BigInteger uvp = BigInteger.valueOf(numerator).multiply(
367: BigInteger.valueOf(fraction.denominator / d1));
368: BigInteger upv = BigInteger.valueOf(fraction.numerator)
369: .multiply(BigInteger.valueOf(denominator / d1));
370: BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
371: // but d2 doesn't need extra precision because
372: // d2 = gcd(t,d1) = gcd(t mod d1, d1)
373: int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
374: int d2 = (tmodd1 == 0) ? d1 : MathUtils.gcd(tmodd1, d1);
375:
376: // result is (t/d2) / (u'/d1)(v'/d2)
377: BigInteger w = t.divide(BigInteger.valueOf(d2));
378: if (w.bitLength() > 31) {
379: throw new ArithmeticException(
380: "overflow: numerator too large after multiply");
381: }
382: return new Fraction(w.intValue(), MathUtils.mulAndCheck(
383: denominator / d1, fraction.denominator / d2));
384: }
385:
386: /**
387: * <p>Multiplies the value of this fraction by another, returning the
388: * result in reduced form.</p>
389: *
390: * @param fraction the fraction to multiply by, must not be <code>null</code>
391: * @return a <code>Fraction</code> instance with the resulting values
392: * @throws IllegalArgumentException if the fraction is <code>null</code>
393: * @throws ArithmeticException if the resulting numerator or denominator exceeds
394: * <code>Integer.MAX_VALUE</code>
395: */
396: public Fraction multiply(Fraction fraction) {
397: if (fraction == null) {
398: throw new IllegalArgumentException(
399: "The fraction must not be null");
400: }
401: if (numerator == 0 || fraction.numerator == 0) {
402: return ZERO;
403: }
404: // knuth 4.5.1
405: // make sure we don't overflow unless the result *must* overflow.
406: int d1 = MathUtils.gcd(numerator, fraction.denominator);
407: int d2 = MathUtils.gcd(fraction.numerator, denominator);
408: return getReducedFraction(MathUtils.mulAndCheck(numerator / d1,
409: fraction.numerator / d2), MathUtils.mulAndCheck(
410: denominator / d2, fraction.denominator / d1));
411: }
412:
413: /**
414: * <p>Divide the value of this fraction by another.</p>
415: *
416: * @param fraction the fraction to divide by, must not be <code>null</code>
417: * @return a <code>Fraction</code> instance with the resulting values
418: * @throws IllegalArgumentException if the fraction is <code>null</code>
419: * @throws ArithmeticException if the fraction to divide by is zero
420: * @throws ArithmeticException if the resulting numerator or denominator exceeds
421: * <code>Integer.MAX_VALUE</code>
422: */
423: public Fraction divide(Fraction fraction) {
424: if (fraction == null) {
425: throw new IllegalArgumentException(
426: "The fraction must not be null");
427: }
428: if (fraction.numerator == 0) {
429: throw new ArithmeticException(
430: "The fraction to divide by must not be zero");
431: }
432: return multiply(fraction.reciprocal());
433: }
434:
435: /**
436: * <p>Creates a <code>Fraction</code> instance with the 2 parts
437: * of a fraction Y/Z.</p>
438: *
439: * <p>Any negative signs are resolved to be on the numerator.</p>
440: *
441: * @param numerator the numerator, for example the three in 'three sevenths'
442: * @param denominator the denominator, for example the seven in 'three sevenths'
443: * @return a new fraction instance, with the numerator and denominator reduced
444: * @throws ArithmeticException if the denominator is <code>zero</code>
445: */
446: public static Fraction getReducedFraction(int numerator,
447: int denominator) {
448: if (denominator == 0) {
449: throw new ArithmeticException(
450: "The denominator must not be zero");
451: }
452: if (numerator == 0) {
453: return ZERO; // normalize zero.
454: }
455: // allow 2^k/-2^31 as a valid fraction (where k>0)
456: if (denominator == Integer.MIN_VALUE && (numerator & 1) == 0) {
457: numerator /= 2;
458: denominator /= 2;
459: }
460: if (denominator < 0) {
461: if (numerator == Integer.MIN_VALUE
462: || denominator == Integer.MIN_VALUE) {
463: throw new ArithmeticException("overflow: can't negate");
464: }
465: numerator = -numerator;
466: denominator = -denominator;
467: }
468: // simplify fraction.
469: int gcd = MathUtils.gcd(numerator, denominator);
470: numerator /= gcd;
471: denominator /= gcd;
472: return new Fraction(numerator, denominator);
473: }
474:
475: /**
476: * Reduce this fraction to lowest terms. This is accomplished by dividing
477: * both numerator and denominator by their greatest common divisor.
478: */
479: private void reduce() {
480: // reduce numerator and denominator by greatest common denominator.
481: int d = MathUtils.gcd(numerator, denominator);
482: if (d > 1) {
483: numerator /= d;
484: denominator /= d;
485: }
486:
487: // move sign to numerator.
488: if (denominator < 0) {
489: numerator *= -1;
490: denominator *= -1;
491: }
492: }
493: }
|