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 }