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 }