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