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 */ 17 package org.apache.commons.math.fraction; 18 19 import java.io.Serializable; 20 import java.math.BigInteger; 21 22 import org.apache.commons.math.FieldElement; 23 import org.apache.commons.math.MathRuntimeException; 24 import org.apache.commons.math.exception.util.LocalizedFormats; 25 import org.apache.commons.math.exception.NullArgumentException; 26 import org.apache.commons.math.util.MathUtils; 27 import org.apache.commons.math.util.FastMath; 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 */ 37 public 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 */ Fraction(double value)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 */ Fraction(double value, double epsilon, int maxIterations)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 */ Fraction(double value, int maxDenominator)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 */ Fraction(double value, double epsilon, int maxDenominator, int maxIterations)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 */ Fraction(int num)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 */ Fraction(int num, int den)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 */ abs()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 */ compareTo(Fraction object)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 doubleValue()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 equals(Object other)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 floatValue()351 public float floatValue() { 352 return (float)doubleValue(); 353 } 354 355 /** 356 * Access the denominator. 357 * @return the denominator. 358 */ getDenominator()359 public int getDenominator() { 360 return denominator; 361 } 362 363 /** 364 * Access the numerator. 365 * @return the numerator. 366 */ getNumerator()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 hashCode()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 intValue()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 longValue()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 */ negate()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 */ reciprocal()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 */ add(Fraction fraction)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 */ add(final int i)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 */ subtract(Fraction fraction)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 */ subtract(final int i)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 */ addSub(Fraction fraction, boolean isAdd)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 */ multiply(Fraction fraction)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 */ multiply(final int i)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 */ divide(Fraction fraction)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 */ divide(final int i)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 */ getReducedFraction(int numerator, int denominator)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 toString()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} */ getField()651 public FractionField getField() { 652 return FractionField.getInstance(); 653 } 654 655 } 656