001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math.fraction;
018
019 import java.io.Serializable;
020 import java.math.BigInteger;
021
022 import org.apache.commons.math.FieldElement;
023 import org.apache.commons.math.MathRuntimeException;
024 import org.apache.commons.math.util.MathUtils;
025
026 /**
027 * Representation of a rational number.
028 *
029 * implements Serializable since 2.0
030 *
031 * @since 1.1
032 * @version $Revision: 795903 $ $Date: 2009-07-20 12:29:46 -0400 (Mon, 20 Jul 2009) $
033 */
034 public class Fraction
035 extends Number
036 implements FieldElement<Fraction>, Comparable<Fraction>, Serializable {
037
038 /** A fraction representing "2 / 1". */
039 public static final Fraction TWO = new Fraction(2, 1);
040
041 /** A fraction representing "1". */
042 public static final Fraction ONE = new Fraction(1, 1);
043
044 /** A fraction representing "0". */
045 public static final Fraction ZERO = new Fraction(0, 1);
046
047 /** A fraction representing "4/5". */
048 public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
049
050 /** A fraction representing "1/5". */
051 public static final Fraction ONE_FIFTH = new Fraction(1, 5);
052
053 /** A fraction representing "1/2". */
054 public static final Fraction ONE_HALF = new Fraction(1, 2);
055
056 /** A fraction representing "1/4". */
057 public static final Fraction ONE_QUARTER = new Fraction(1, 4);
058
059 /** A fraction representing "1/3". */
060 public static final Fraction ONE_THIRD = new Fraction(1, 3);
061
062 /** A fraction representing "3/5". */
063 public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
064
065 /** A fraction representing "3/4". */
066 public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
067
068 /** A fraction representing "2/5". */
069 public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
070
071 /** A fraction representing "2/4". */
072 public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
073
074 /** A fraction representing "2/3". */
075 public static final Fraction TWO_THIRDS = new Fraction(2, 3);
076
077 /** A fraction representing "-1 / 1". */
078 public static final Fraction MINUS_ONE = new Fraction(-1, 1);
079
080 /** Serializable version identifier */
081 private static final long serialVersionUID = 3698073679419233275L;
082
083 /** The denominator. */
084 private final int denominator;
085
086 /** The numerator. */
087 private final int numerator;
088
089 /**
090 * Create a fraction given the double value.
091 * @param value the double value to convert to a fraction.
092 * @throws FractionConversionException if the continued fraction failed to
093 * converge.
094 */
095 public Fraction(double value) throws FractionConversionException {
096 this(value, 1.0e-5, 100);
097 }
098
099 /**
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 }