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.math3.fraction; 018 019 import java.io.Serializable; 020 import java.math.BigInteger; 021 022 import org.apache.commons.math3.FieldElement; 023 import org.apache.commons.math3.exception.util.LocalizedFormats; 024 import org.apache.commons.math3.exception.MathArithmeticException; 025 import org.apache.commons.math3.exception.NullArgumentException; 026 import org.apache.commons.math3.util.ArithmeticUtils; 027 import org.apache.commons.math3.util.FastMath; 028 029 /** 030 * Representation of a rational number. 031 * 032 * implements Serializable since 2.0 033 * 034 * @since 1.1 035 * @version $Id: Fraction.java 1416643 2012-12-03 19:37:14Z tn $ 036 */ 037 public class Fraction 038 extends Number 039 implements FieldElement<Fraction>, Comparable<Fraction>, Serializable { 040 041 /** A fraction representing "2 / 1". */ 042 public static final Fraction TWO = new Fraction(2, 1); 043 044 /** A fraction representing "1". */ 045 public static final Fraction ONE = new Fraction(1, 1); 046 047 /** A fraction representing "0". */ 048 public static final Fraction ZERO = new Fraction(0, 1); 049 050 /** A fraction representing "4/5". */ 051 public static final Fraction FOUR_FIFTHS = new Fraction(4, 5); 052 053 /** A fraction representing "1/5". */ 054 public static final Fraction ONE_FIFTH = new Fraction(1, 5); 055 056 /** A fraction representing "1/2". */ 057 public static final Fraction ONE_HALF = new Fraction(1, 2); 058 059 /** A fraction representing "1/4". */ 060 public static final Fraction ONE_QUARTER = new Fraction(1, 4); 061 062 /** A fraction representing "1/3". */ 063 public static final Fraction ONE_THIRD = new Fraction(1, 3); 064 065 /** A fraction representing "3/5". */ 066 public static final Fraction THREE_FIFTHS = new Fraction(3, 5); 067 068 /** A fraction representing "3/4". */ 069 public static final Fraction THREE_QUARTERS = new Fraction(3, 4); 070 071 /** A fraction representing "2/5". */ 072 public static final Fraction TWO_FIFTHS = new Fraction(2, 5); 073 074 /** A fraction representing "2/4". */ 075 public static final Fraction TWO_QUARTERS = new Fraction(2, 4); 076 077 /** A fraction representing "2/3". */ 078 public static final Fraction TWO_THIRDS = new Fraction(2, 3); 079 080 /** A fraction representing "-1 / 1". */ 081 public static final Fraction MINUS_ONE = new Fraction(-1, 1); 082 083 /** Serializable version identifier */ 084 private static final long serialVersionUID = 3698073679419233275L; 085 086 /** The denominator. */ 087 private final int denominator; 088 089 /** The numerator. */ 090 private final int numerator; 091 092 /** 093 * Create a fraction given the double value. 094 * @param value the double value to convert to a fraction. 095 * @throws FractionConversionException if the continued fraction failed to 096 * converge. 097 */ 098 public Fraction(double value) throws FractionConversionException { 099 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} of {@code value}, 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} of {@code value}, 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 (FastMath.abs(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 ((FastMath.abs(p2) > overflow) || (FastMath.abs(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 MathArithmeticException if the denominator is {@code zero} 255 */ 256 public Fraction(int num, int den) { 257 if (den == 0) { 258 throw new MathArithmeticException(LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION, 259 num, den); 260 } 261 if (den < 0) { 262 if (num == Integer.MIN_VALUE || 263 den == Integer.MIN_VALUE) { 264 throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_FRACTION, 265 num, den); 266 } 267 num = -num; 268 den = -den; 269 } 270 // reduce numerator and denominator by greatest common denominator. 271 final int d = ArithmeticUtils.gcd(num, den); 272 if (d > 1) { 273 num /= d; 274 den /= d; 275 } 276 277 // move sign to numerator. 278 if (den < 0) { 279 num = -num; 280 den = -den; 281 } 282 this.numerator = num; 283 this.denominator = den; 284 } 285 286 /** 287 * Returns the absolute value of this fraction. 288 * @return the absolute value. 289 */ 290 public Fraction abs() { 291 Fraction ret; 292 if (numerator >= 0) { 293 ret = this; 294 } else { 295 ret = negate(); 296 } 297 return ret; 298 } 299 300 /** 301 * Compares this object to another based on size. 302 * @param object the object to compare to 303 * @return -1 if this is less than <tt>object</tt>, +1 if this is greater 304 * than <tt>object</tt>, 0 if they are equal. 305 */ 306 public int compareTo(Fraction object) { 307 long nOd = ((long) numerator) * object.denominator; 308 long dOn = ((long) denominator) * object.numerator; 309 return (nOd < dOn) ? -1 : ((nOd > dOn) ? +1 : 0); 310 } 311 312 /** 313 * Gets the fraction as a <tt>double</tt>. This calculates the fraction as 314 * the numerator divided by denominator. 315 * @return the fraction as a <tt>double</tt> 316 */ 317 @Override 318 public double doubleValue() { 319 return (double)numerator / (double)denominator; 320 } 321 322 /** 323 * Test for the equality of two fractions. If the lowest term 324 * numerator and denominators are the same for both fractions, the two 325 * fractions are considered to be equal. 326 * @param other fraction to test for equality to this fraction 327 * @return true if two fractions are equal, false if object is 328 * <tt>null</tt>, not an instance of {@link Fraction}, or not equal 329 * to this fraction instance. 330 */ 331 @Override 332 public boolean equals(Object other) { 333 if (this == other) { 334 return true; 335 } 336 if (other instanceof Fraction) { 337 // since fractions are always in lowest terms, numerators and 338 // denominators can be compared directly for equality. 339 Fraction rhs = (Fraction)other; 340 return (numerator == rhs.numerator) && 341 (denominator == rhs.denominator); 342 } 343 return false; 344 } 345 346 /** 347 * Gets the fraction as a <tt>float</tt>. This calculates the fraction as 348 * the numerator divided by denominator. 349 * @return the fraction as a <tt>float</tt> 350 */ 351 @Override 352 public float floatValue() { 353 return (float)doubleValue(); 354 } 355 356 /** 357 * Access the denominator. 358 * @return the denominator. 359 */ 360 public int getDenominator() { 361 return denominator; 362 } 363 364 /** 365 * Access the numerator. 366 * @return the numerator. 367 */ 368 public int getNumerator() { 369 return numerator; 370 } 371 372 /** 373 * Gets a hashCode for the fraction. 374 * @return a hash code value for this object 375 */ 376 @Override 377 public int hashCode() { 378 return 37 * (37 * 17 + numerator) + denominator; 379 } 380 381 /** 382 * Gets the fraction as an <tt>int</tt>. This returns the whole number part 383 * of the fraction. 384 * @return the whole number fraction part 385 */ 386 @Override 387 public int intValue() { 388 return (int)doubleValue(); 389 } 390 391 /** 392 * Gets the fraction as a <tt>long</tt>. This returns the whole number part 393 * of the fraction. 394 * @return the whole number fraction part 395 */ 396 @Override 397 public long longValue() { 398 return (long)doubleValue(); 399 } 400 401 /** 402 * Return the additive inverse of this fraction. 403 * @return the negation of this fraction. 404 */ 405 public Fraction negate() { 406 if (numerator==Integer.MIN_VALUE) { 407 throw new MathArithmeticException(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} 425 * @return a {@code Fraction} instance with the resulting values 426 * @throws NullArgumentException if the fraction is {@code null} 427 * @throws MathArithmeticException if the resulting numerator or denominator exceeds 428 * {@code Integer.MAX_VALUE} 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} 448 * @return a {@code Fraction} instance with the resulting values 449 * @throws NullArgumentException if the fraction is {@code null} 450 * @throws MathArithmeticException if the resulting numerator or denominator 451 * cannot be represented in an {@code int}. 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} 470 * @param isAdd true to add, false to subtract 471 * @return a {@code Fraction} instance with the resulting values 472 * @throws NullArgumentException if the fraction is {@code null} 473 * @throws MathArithmeticException if the resulting numerator or denominator 474 * cannot be represented in an {@code int}. 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 = ArithmeticUtils.gcd(denominator, fraction.denominator); 490 if (d1==1) { 491 // result is ( (u*v' +/- u'v) / u'v') 492 int uvp = ArithmeticUtils.mulAndCheck(numerator, fraction.denominator); 493 int upv = ArithmeticUtils.mulAndCheck(fraction.numerator, denominator); 494 return new Fraction 495 (isAdd ? ArithmeticUtils.addAndCheck(uvp, upv) : 496 ArithmeticUtils.subAndCheck(uvp, upv), 497 ArithmeticUtils.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:ArithmeticUtils.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 new MathArithmeticException(LocalizedFormats.NUMERATOR_OVERFLOW_AFTER_MULTIPLY, 516 w); 517 } 518 return new Fraction (w.intValue(), 519 ArithmeticUtils.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} 528 * @return a {@code Fraction} instance with the resulting values 529 * @throws NullArgumentException if the fraction is {@code null} 530 * @throws MathArithmeticException if the resulting numerator or denominator exceeds 531 * {@code Integer.MAX_VALUE} 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 = ArithmeticUtils.gcd(numerator, fraction.denominator); 543 int d2 = ArithmeticUtils.gcd(fraction.numerator, denominator); 544 return getReducedFraction 545 (ArithmeticUtils.mulAndCheck(numerator/d1, fraction.numerator/d2), 546 ArithmeticUtils.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} 562 * @return a {@code Fraction} instance with the resulting values 563 * @throws IllegalArgumentException if the fraction is {@code null} 564 * @throws MathArithmeticException if the fraction to divide by is zero 565 * @throws MathArithmeticException if the resulting numerator or denominator exceeds 566 * {@code Integer.MAX_VALUE} 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 new MathArithmeticException(LocalizedFormats.ZERO_FRACTION_TO_DIVIDE_BY, 574 fraction.numerator, fraction.denominator); 575 } 576 return multiply(fraction.reciprocal()); 577 } 578 579 /** 580 * Divide the fraction by an integer. 581 * @param i the <tt>integer</tt> to divide by. 582 * @return this * i 583 */ 584 public Fraction divide(final int i) { 585 return new Fraction(numerator, denominator * i); 586 } 587 588 /** 589 * <p> 590 * Gets the fraction percentage as a <tt>double</tt>. This calculates the 591 * fraction as the numerator divided by denominator multiplied by 100. 592 * </p> 593 * 594 * @return the fraction percentage as a <tt>double</tt>. 595 */ 596 public double percentageValue() { 597 return 100 * doubleValue(); 598 } 599 600 /** 601 * <p>Creates a {@code Fraction} instance with the 2 parts 602 * of a fraction Y/Z.</p> 603 * 604 * <p>Any negative signs are resolved to be on the numerator.</p> 605 * 606 * @param numerator the numerator, for example the three in 'three sevenths' 607 * @param denominator the denominator, for example the seven in 'three sevenths' 608 * @return a new fraction instance, with the numerator and denominator reduced 609 * @throws MathArithmeticException if the denominator is {@code zero} 610 */ 611 public static Fraction getReducedFraction(int numerator, int denominator) { 612 if (denominator == 0) { 613 throw new MathArithmeticException(LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION, 614 numerator, denominator); 615 } 616 if (numerator==0) { 617 return ZERO; // normalize zero. 618 } 619 // allow 2^k/-2^31 as a valid fraction (where k>0) 620 if (denominator==Integer.MIN_VALUE && (numerator&1)==0) { 621 numerator/=2; denominator/=2; 622 } 623 if (denominator < 0) { 624 if (numerator==Integer.MIN_VALUE || 625 denominator==Integer.MIN_VALUE) { 626 throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_FRACTION, 627 numerator, denominator); 628 } 629 numerator = -numerator; 630 denominator = -denominator; 631 } 632 // simplify fraction. 633 int gcd = ArithmeticUtils.gcd(numerator, denominator); 634 numerator /= gcd; 635 denominator /= gcd; 636 return new Fraction(numerator, denominator); 637 } 638 639 /** 640 * <p> 641 * Returns the {@code String} representing this fraction, ie 642 * "num / dem" or just "num" if the denominator is one. 643 * </p> 644 * 645 * @return a string representation of the fraction. 646 * @see java.lang.Object#toString() 647 */ 648 @Override 649 public String toString() { 650 String str = null; 651 if (denominator == 1) { 652 str = Integer.toString(numerator); 653 } else if (numerator == 0) { 654 str = "0"; 655 } else { 656 str = numerator + " / " + denominator; 657 } 658 return str; 659 } 660 661 /** {@inheritDoc} */ 662 public FractionField getField() { 663 return FractionField.getInstance(); 664 } 665 666 }