source: src/main/java/agents/org/apache/commons/math/fraction/Fraction.java

Last change on this file was 1, checked in by Wouter Pasman, 7 years ago

Initial import : Genius 9.0.0

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