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 */ 017package org.apache.commons.lang3.math; 018 019import java.math.BigInteger; 020 021import org.apache.commons.lang3.Validate; 022 023/** 024 * <p><code>Fraction</code> is a <code>Number</code> implementation that 025 * stores fractions accurately.</p> 026 * 027 * <p>This class is immutable, and interoperable with most methods that accept 028 * a <code>Number</code>.</p> 029 * 030 * <p>Note that this class is intended for common use cases, it is <i>int</i> 031 * based and thus suffers from various overflow issues. For a BigInteger based 032 * equivalent, please see the Commons Math BigFraction class. </p> 033 * 034 * @since 2.0 035 */ 036public final class Fraction extends Number implements Comparable<Fraction> { 037 038 /** 039 * Required for serialization support. Lang version 2.0. 040 * 041 * @see java.io.Serializable 042 */ 043 private static final long serialVersionUID = 65382027393090L; 044 045 /** 046 * <code>Fraction</code> representation of 0. 047 */ 048 public static final Fraction ZERO = new Fraction(0, 1); 049 /** 050 * <code>Fraction</code> representation of 1. 051 */ 052 public static final Fraction ONE = new Fraction(1, 1); 053 /** 054 * <code>Fraction</code> representation of 1/2. 055 */ 056 public static final Fraction ONE_HALF = new Fraction(1, 2); 057 /** 058 * <code>Fraction</code> representation of 1/3. 059 */ 060 public static final Fraction ONE_THIRD = new Fraction(1, 3); 061 /** 062 * <code>Fraction</code> representation of 2/3. 063 */ 064 public static final Fraction TWO_THIRDS = new Fraction(2, 3); 065 /** 066 * <code>Fraction</code> representation of 1/4. 067 */ 068 public static final Fraction ONE_QUARTER = new Fraction(1, 4); 069 /** 070 * <code>Fraction</code> representation of 2/4. 071 */ 072 public static final Fraction TWO_QUARTERS = new Fraction(2, 4); 073 /** 074 * <code>Fraction</code> representation of 3/4. 075 */ 076 public static final Fraction THREE_QUARTERS = new Fraction(3, 4); 077 /** 078 * <code>Fraction</code> representation of 1/5. 079 */ 080 public static final Fraction ONE_FIFTH = new Fraction(1, 5); 081 /** 082 * <code>Fraction</code> representation of 2/5. 083 */ 084 public static final Fraction TWO_FIFTHS = new Fraction(2, 5); 085 /** 086 * <code>Fraction</code> representation of 3/5. 087 */ 088 public static final Fraction THREE_FIFTHS = new Fraction(3, 5); 089 /** 090 * <code>Fraction</code> representation of 4/5. 091 */ 092 public static final Fraction FOUR_FIFTHS = new Fraction(4, 5); 093 094 095 /** 096 * The numerator number part of the fraction (the three in three sevenths). 097 */ 098 private final int numerator; 099 /** 100 * The denominator number part of the fraction (the seven in three sevenths). 101 */ 102 private final int denominator; 103 104 /** 105 * Cached output hashCode (class is immutable). 106 */ 107 private transient int hashCode = 0; 108 /** 109 * Cached output toString (class is immutable). 110 */ 111 private transient String toString = null; 112 /** 113 * Cached output toProperString (class is immutable). 114 */ 115 private transient String toProperString = null; 116 117 /** 118 * <p>Constructs a <code>Fraction</code> instance with the 2 parts 119 * of a fraction Y/Z.</p> 120 * 121 * @param numerator the numerator, for example the three in 'three sevenths' 122 * @param denominator the denominator, for example the seven in 'three sevenths' 123 */ 124 private Fraction(final int numerator, final int denominator) { 125 super(); 126 this.numerator = numerator; 127 this.denominator = denominator; 128 } 129 130 /** 131 * <p>Creates a <code>Fraction</code> instance with the 2 parts 132 * of a fraction Y/Z.</p> 133 * 134 * <p>Any negative signs are resolved to be on the numerator.</p> 135 * 136 * @param numerator the numerator, for example the three in 'three sevenths' 137 * @param denominator the denominator, for example the seven in 'three sevenths' 138 * @return a new fraction instance 139 * @throws ArithmeticException if the denominator is <code>zero</code> 140 * or the denominator is {@code negative} and the numerator is {@code Integer#MIN_VALUE} 141 */ 142 public static Fraction getFraction(int numerator, int denominator) { 143 if (denominator == 0) { 144 throw new ArithmeticException("The denominator must not be zero"); 145 } 146 if (denominator < 0) { 147 if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) { 148 throw new ArithmeticException("overflow: can't negate"); 149 } 150 numerator = -numerator; 151 denominator = -denominator; 152 } 153 return new Fraction(numerator, denominator); 154 } 155 156 /** 157 * <p>Creates a <code>Fraction</code> instance with the 3 parts 158 * of a fraction X Y/Z.</p> 159 * 160 * <p>The negative sign must be passed in on the whole number part.</p> 161 * 162 * @param whole the whole number, for example the one in 'one and three sevenths' 163 * @param numerator the numerator, for example the three in 'one and three sevenths' 164 * @param denominator the denominator, for example the seven in 'one and three sevenths' 165 * @return a new fraction instance 166 * @throws ArithmeticException if the denominator is <code>zero</code> 167 * @throws ArithmeticException if the denominator is negative 168 * @throws ArithmeticException if the numerator is negative 169 * @throws ArithmeticException if the resulting numerator exceeds 170 * <code>Integer.MAX_VALUE</code> 171 */ 172 public static Fraction getFraction(final int whole, final int numerator, final int denominator) { 173 if (denominator == 0) { 174 throw new ArithmeticException("The denominator must not be zero"); 175 } 176 if (denominator < 0) { 177 throw new ArithmeticException("The denominator must not be negative"); 178 } 179 if (numerator < 0) { 180 throw new ArithmeticException("The numerator must not be negative"); 181 } 182 long numeratorValue; 183 if (whole < 0) { 184 numeratorValue = whole * (long) denominator - numerator; 185 } else { 186 numeratorValue = whole * (long) denominator + numerator; 187 } 188 if (numeratorValue < Integer.MIN_VALUE || numeratorValue > Integer.MAX_VALUE) { 189 throw new ArithmeticException("Numerator too large to represent as an Integer."); 190 } 191 return new Fraction((int) numeratorValue, denominator); 192 } 193 194 /** 195 * <p>Creates a reduced <code>Fraction</code> instance with the 2 parts 196 * of a fraction Y/Z.</p> 197 * 198 * <p>For example, if the input parameters represent 2/4, then the created 199 * fraction will be 1/2.</p> 200 * 201 * <p>Any negative signs are resolved to be on the numerator.</p> 202 * 203 * @param numerator the numerator, for example the three in 'three sevenths' 204 * @param denominator the denominator, for example the seven in 'three sevenths' 205 * @return a new fraction instance, with the numerator and denominator reduced 206 * @throws ArithmeticException if the denominator is <code>zero</code> 207 */ 208 public static Fraction getReducedFraction(int numerator, int denominator) { 209 if (denominator == 0) { 210 throw new ArithmeticException("The denominator must not be zero"); 211 } 212 if (numerator == 0) { 213 return ZERO; // normalize zero. 214 } 215 // allow 2^k/-2^31 as a valid fraction (where k>0) 216 if (denominator == Integer.MIN_VALUE && (numerator & 1) == 0) { 217 numerator /= 2; 218 denominator /= 2; 219 } 220 if (denominator < 0) { 221 if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) { 222 throw new ArithmeticException("overflow: can't negate"); 223 } 224 numerator = -numerator; 225 denominator = -denominator; 226 } 227 // simplify fraction. 228 final int gcd = greatestCommonDivisor(numerator, denominator); 229 numerator /= gcd; 230 denominator /= gcd; 231 return new Fraction(numerator, denominator); 232 } 233 234 /** 235 * <p>Creates a <code>Fraction</code> instance from a <code>double</code> value.</p> 236 * 237 * <p>This method uses the <a href="http://archives.math.utk.edu/articles/atuyl/confrac/"> 238 * continued fraction algorithm</a>, computing a maximum of 239 * 25 convergents and bounding the denominator by 10,000.</p> 240 * 241 * @param value the double value to convert 242 * @return a new fraction instance that is close to the value 243 * @throws ArithmeticException if <code>|value| > Integer.MAX_VALUE</code> 244 * or <code>value = NaN</code> 245 * @throws ArithmeticException if the calculated denominator is <code>zero</code> 246 * @throws ArithmeticException if the algorithm does not converge 247 */ 248 public static Fraction getFraction(double value) { 249 final int sign = value < 0 ? -1 : 1; 250 value = Math.abs(value); 251 if (value > Integer.MAX_VALUE || Double.isNaN(value)) { 252 throw new ArithmeticException("The value must not be greater than Integer.MAX_VALUE or NaN"); 253 } 254 final int wholeNumber = (int) value; 255 value -= wholeNumber; 256 257 int numer0 = 0; // the pre-previous 258 int denom0 = 1; // the pre-previous 259 int numer1 = 1; // the previous 260 int denom1 = 0; // the previous 261 int numer2 = 0; // the current, setup in calculation 262 int denom2 = 0; // the current, setup in calculation 263 int a1 = (int) value; 264 int a2 = 0; 265 double x1 = 1; 266 double x2 = 0; 267 double y1 = value - a1; 268 double y2 = 0; 269 double delta1, delta2 = Double.MAX_VALUE; 270 double fraction; 271 int i = 1; 272 do { 273 delta1 = delta2; 274 a2 = (int) (x1 / y1); 275 x2 = y1; 276 y2 = x1 - a2 * y1; 277 numer2 = a1 * numer1 + numer0; 278 denom2 = a1 * denom1 + denom0; 279 fraction = (double) numer2 / (double) denom2; 280 delta2 = Math.abs(value - fraction); 281 a1 = a2; 282 x1 = x2; 283 y1 = y2; 284 numer0 = numer1; 285 denom0 = denom1; 286 numer1 = numer2; 287 denom1 = denom2; 288 i++; 289 } while (delta1 > delta2 && denom2 <= 10000 && denom2 > 0 && i < 25); 290 if (i == 25) { 291 throw new ArithmeticException("Unable to convert double to fraction"); 292 } 293 return getReducedFraction((numer0 + wholeNumber * denom0) * sign, denom0); 294 } 295 296 /** 297 * <p>Creates a Fraction from a <code>String</code>.</p> 298 * 299 * <p>The formats accepted are:</p> 300 * 301 * <ol> 302 * <li><code>double</code> String containing a dot</li> 303 * <li>'X Y/Z'</li> 304 * <li>'Y/Z'</li> 305 * <li>'X' (a simple whole number)</li> 306 * </ol> 307 * <p>and a .</p> 308 * 309 * @param str the string to parse, must not be <code>null</code> 310 * @return the new <code>Fraction</code> instance 311 * @throws IllegalArgumentException if the string is <code>null</code> 312 * @throws NumberFormatException if the number format is invalid 313 */ 314 public static Fraction getFraction(String str) { 315 Validate.isTrue(str != null, "The string must not be null"); 316 // parse double format 317 int pos = str.indexOf('.'); 318 if (pos >= 0) { 319 return getFraction(Double.parseDouble(str)); 320 } 321 322 // parse X Y/Z format 323 pos = str.indexOf(' '); 324 if (pos > 0) { 325 final int whole = Integer.parseInt(str.substring(0, pos)); 326 str = str.substring(pos + 1); 327 pos = str.indexOf('/'); 328 if (pos < 0) { 329 throw new NumberFormatException("The fraction could not be parsed as the format X Y/Z"); 330 } 331 final int numer = Integer.parseInt(str.substring(0, pos)); 332 final int denom = Integer.parseInt(str.substring(pos + 1)); 333 return getFraction(whole, numer, denom); 334 } 335 336 // parse Y/Z format 337 pos = str.indexOf('/'); 338 if (pos < 0) { 339 // simple whole number 340 return getFraction(Integer.parseInt(str), 1); 341 } 342 final int numer = Integer.parseInt(str.substring(0, pos)); 343 final int denom = Integer.parseInt(str.substring(pos + 1)); 344 return getFraction(numer, denom); 345 } 346 347 // Accessors 348 //------------------------------------------------------------------- 349 350 /** 351 * <p>Gets the numerator part of the fraction.</p> 352 * 353 * <p>This method may return a value greater than the denominator, an 354 * improper fraction, such as the seven in 7/4.</p> 355 * 356 * @return the numerator fraction part 357 */ 358 public int getNumerator() { 359 return numerator; 360 } 361 362 /** 363 * <p>Gets the denominator part of the fraction.</p> 364 * 365 * @return the denominator fraction part 366 */ 367 public int getDenominator() { 368 return denominator; 369 } 370 371 /** 372 * <p>Gets the proper numerator, always positive.</p> 373 * 374 * <p>An improper fraction 7/4 can be resolved into a proper one, 1 3/4. 375 * This method returns the 3 from the proper fraction.</p> 376 * 377 * <p>If the fraction is negative such as -7/4, it can be resolved into 378 * -1 3/4, so this method returns the positive proper numerator, 3.</p> 379 * 380 * @return the numerator fraction part of a proper fraction, always positive 381 */ 382 public int getProperNumerator() { 383 return Math.abs(numerator % denominator); 384 } 385 386 /** 387 * <p>Gets the proper whole part of the fraction.</p> 388 * 389 * <p>An improper fraction 7/4 can be resolved into a proper one, 1 3/4. 390 * This method returns the 1 from the proper fraction.</p> 391 * 392 * <p>If the fraction is negative such as -7/4, it can be resolved into 393 * -1 3/4, so this method returns the positive whole part -1.</p> 394 * 395 * @return the whole fraction part of a proper fraction, that includes the sign 396 */ 397 public int getProperWhole() { 398 return numerator / denominator; 399 } 400 401 // Number methods 402 //------------------------------------------------------------------- 403 404 /** 405 * <p>Gets the fraction as an <code>int</code>. This returns the whole number 406 * part of the fraction.</p> 407 * 408 * @return the whole number fraction part 409 */ 410 @Override 411 public int intValue() { 412 return numerator / denominator; 413 } 414 415 /** 416 * <p>Gets the fraction as a <code>long</code>. This returns the whole number 417 * part of the fraction.</p> 418 * 419 * @return the whole number fraction part 420 */ 421 @Override 422 public long longValue() { 423 return (long) numerator / denominator; 424 } 425 426 /** 427 * <p>Gets the fraction as a <code>float</code>. This calculates the fraction 428 * as the numerator divided by denominator.</p> 429 * 430 * @return the fraction as a <code>float</code> 431 */ 432 @Override 433 public float floatValue() { 434 return (float) numerator / (float) denominator; 435 } 436 437 /** 438 * <p>Gets the fraction as a <code>double</code>. This calculates the fraction 439 * as the numerator divided by denominator.</p> 440 * 441 * @return the fraction as a <code>double</code> 442 */ 443 @Override 444 public double doubleValue() { 445 return (double) numerator / (double) denominator; 446 } 447 448 // Calculations 449 //------------------------------------------------------------------- 450 451 /** 452 * <p>Reduce the fraction to the smallest values for the numerator and 453 * denominator, returning the result.</p> 454 * 455 * <p>For example, if this fraction represents 2/4, then the result 456 * will be 1/2.</p> 457 * 458 * @return a new reduced fraction instance, or this if no simplification possible 459 */ 460 public Fraction reduce() { 461 if (numerator == 0) { 462 return equals(ZERO) ? this : ZERO; 463 } 464 final int gcd = greatestCommonDivisor(Math.abs(numerator), denominator); 465 if (gcd == 1) { 466 return this; 467 } 468 return getFraction(numerator / gcd, denominator / gcd); 469 } 470 471 /** 472 * <p>Gets a fraction that is the inverse (1/fraction) of this one.</p> 473 * 474 * <p>The returned fraction is not reduced.</p> 475 * 476 * @return a new fraction instance with the numerator and denominator 477 * inverted. 478 * @throws ArithmeticException if the fraction represents zero. 479 */ 480 public Fraction invert() { 481 if (numerator == 0) { 482 throw new ArithmeticException("Unable to invert zero."); 483 } 484 if (numerator==Integer.MIN_VALUE) { 485 throw new ArithmeticException("overflow: can't negate numerator"); 486 } 487 if (numerator<0) { 488 return new Fraction(-denominator, -numerator); 489 } 490 return new Fraction(denominator, numerator); 491 } 492 493 /** 494 * <p>Gets a fraction that is the negative (-fraction) of this one.</p> 495 * 496 * <p>The returned fraction is not reduced.</p> 497 * 498 * @return a new fraction instance with the opposite signed numerator 499 */ 500 public Fraction negate() { 501 // the positive range is one smaller than the negative range of an int. 502 if (numerator==Integer.MIN_VALUE) { 503 throw new ArithmeticException("overflow: too large to negate"); 504 } 505 return new Fraction(-numerator, denominator); 506 } 507 508 /** 509 * <p>Gets a fraction that is the positive equivalent of this one.</p> 510 * <p>More precisely: <code>(fraction >= 0 ? this : -fraction)</code></p> 511 * 512 * <p>The returned fraction is not reduced.</p> 513 * 514 * @return <code>this</code> if it is positive, or a new positive fraction 515 * instance with the opposite signed numerator 516 */ 517 public Fraction abs() { 518 if (numerator >= 0) { 519 return this; 520 } 521 return negate(); 522 } 523 524 /** 525 * <p>Gets a fraction that is raised to the passed in power.</p> 526 * 527 * <p>The returned fraction is in reduced form.</p> 528 * 529 * @param power the power to raise the fraction to 530 * @return <code>this</code> if the power is one, <code>ONE</code> if the power 531 * is zero (even if the fraction equals ZERO) or a new fraction instance 532 * raised to the appropriate power 533 * @throws ArithmeticException if the resulting numerator or denominator exceeds 534 * <code>Integer.MAX_VALUE</code> 535 */ 536 public Fraction pow(final int power) { 537 if (power == 1) { 538 return this; 539 } else if (power == 0) { 540 return ONE; 541 } else if (power < 0) { 542 if (power == Integer.MIN_VALUE) { // MIN_VALUE can't be negated. 543 return this.invert().pow(2).pow(-(power / 2)); 544 } 545 return this.invert().pow(-power); 546 } else { 547 final Fraction f = this.multiplyBy(this); 548 if (power % 2 == 0) { // if even... 549 return f.pow(power / 2); 550 } 551 return f.pow(power / 2).multiplyBy(this); 552 } 553 } 554 555 /** 556 * <p>Gets the greatest common divisor of the absolute value of 557 * two numbers, using the "binary gcd" method which avoids 558 * division and modulo operations. See Knuth 4.5.2 algorithm B. 559 * This algorithm is due to Josef Stein (1961).</p> 560 * 561 * @param u a non-zero number 562 * @param v a non-zero number 563 * @return the greatest common divisor, never zero 564 */ 565 private static int greatestCommonDivisor(int u, int v) { 566 // From Commons Math: 567 if (u == 0 || v == 0) { 568 if (u == Integer.MIN_VALUE || v == Integer.MIN_VALUE) { 569 throw new ArithmeticException("overflow: gcd is 2^31"); 570 } 571 return Math.abs(u) + Math.abs(v); 572 } 573 // if either operand is abs 1, return 1: 574 if (Math.abs(u) == 1 || Math.abs(v) == 1) { 575 return 1; 576 } 577 // keep u and v negative, as negative integers range down to 578 // -2^31, while positive numbers can only be as large as 2^31-1 579 // (i.e. we can't necessarily negate a negative number without 580 // overflow) 581 if (u > 0) { 582 u = -u; 583 } // make u negative 584 if (v > 0) { 585 v = -v; 586 } // make v negative 587 // B1. [Find power of 2] 588 int k = 0; 589 while ((u & 1) == 0 && (v & 1) == 0 && k < 31) { // while u and v are both even... 590 u /= 2; 591 v /= 2; 592 k++; // cast out twos. 593 } 594 if (k == 31) { 595 throw new ArithmeticException("overflow: gcd is 2^31"); 596 } 597 // B2. Initialize: u and v have been divided by 2^k and at least 598 // one is odd. 599 int t = (u & 1) == 1 ? v : -(u / 2)/* B3 */; 600 // t negative: u was odd, v may be even (t replaces v) 601 // t positive: u was even, v is odd (t replaces u) 602 do { 603 /* assert u<0 && v<0; */ 604 // B4/B3: cast out twos from t. 605 while ((t & 1) == 0) { // while t is even.. 606 t /= 2; // cast out twos 607 } 608 // B5 [reset max(u,v)] 609 if (t > 0) { 610 u = -t; 611 } else { 612 v = t; 613 } 614 // B6/B3. at this point both u and v should be odd. 615 t = (v - u) / 2; 616 // |u| larger: t positive (replace u) 617 // |v| larger: t negative (replace v) 618 } while (t != 0); 619 return -u * (1 << k); // gcd is u*2^k 620 } 621 622 // Arithmetic 623 //------------------------------------------------------------------- 624 625 /** 626 * Multiply two integers, checking for overflow. 627 * 628 * @param x a factor 629 * @param y a factor 630 * @return the product <code>x*y</code> 631 * @throws ArithmeticException if the result can not be represented as 632 * an int 633 */ 634 private static int mulAndCheck(final int x, final int y) { 635 final long m = (long) x * (long) y; 636 if (m < Integer.MIN_VALUE || m > Integer.MAX_VALUE) { 637 throw new ArithmeticException("overflow: mul"); 638 } 639 return (int) m; 640 } 641 642 /** 643 * Multiply two non-negative integers, checking for overflow. 644 * 645 * @param x a non-negative factor 646 * @param y a non-negative factor 647 * @return the product <code>x*y</code> 648 * @throws ArithmeticException if the result can not be represented as 649 * an int 650 */ 651 private static int mulPosAndCheck(final int x, final int y) { 652 /* assert x>=0 && y>=0; */ 653 final long m = (long) x * (long) y; 654 if (m > Integer.MAX_VALUE) { 655 throw new ArithmeticException("overflow: mulPos"); 656 } 657 return (int) m; 658 } 659 660 /** 661 * Add two integers, checking for overflow. 662 * 663 * @param x an addend 664 * @param y an addend 665 * @return the sum <code>x+y</code> 666 * @throws ArithmeticException if the result can not be represented as 667 * an int 668 */ 669 private static int addAndCheck(final int x, final int y) { 670 final long s = (long) x + (long) y; 671 if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) { 672 throw new ArithmeticException("overflow: add"); 673 } 674 return (int) s; 675 } 676 677 /** 678 * Subtract two integers, checking for overflow. 679 * 680 * @param x the minuend 681 * @param y the subtrahend 682 * @return the difference <code>x-y</code> 683 * @throws ArithmeticException if the result can not be represented as 684 * an int 685 */ 686 private static int subAndCheck(final int x, final int y) { 687 final long s = (long) x - (long) y; 688 if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) { 689 throw new ArithmeticException("overflow: add"); 690 } 691 return (int) s; 692 } 693 694 /** 695 * <p>Adds the value of this fraction to another, returning the result in reduced form. 696 * The algorithm follows Knuth, 4.5.1.</p> 697 * 698 * @param fraction the fraction to add, must not be <code>null</code> 699 * @return a <code>Fraction</code> instance with the resulting values 700 * @throws IllegalArgumentException if the fraction is <code>null</code> 701 * @throws ArithmeticException if the resulting numerator or denominator exceeds 702 * <code>Integer.MAX_VALUE</code> 703 */ 704 public Fraction add(final Fraction fraction) { 705 return addSub(fraction, true /* add */); 706 } 707 708 /** 709 * <p>Subtracts the value of another fraction from the value of this one, 710 * returning the result in reduced form.</p> 711 * 712 * @param fraction the fraction to subtract, must not be <code>null</code> 713 * @return a <code>Fraction</code> instance with the resulting values 714 * @throws IllegalArgumentException if the fraction is <code>null</code> 715 * @throws ArithmeticException if the resulting numerator or denominator 716 * cannot be represented in an <code>int</code>. 717 */ 718 public Fraction subtract(final Fraction fraction) { 719 return addSub(fraction, false /* subtract */); 720 } 721 722 /** 723 * Implement add and subtract using algorithm described in Knuth 4.5.1. 724 * 725 * @param fraction the fraction to subtract, must not be <code>null</code> 726 * @param isAdd true to add, false to subtract 727 * @return a <code>Fraction</code> instance with the resulting values 728 * @throws IllegalArgumentException if the fraction is <code>null</code> 729 * @throws ArithmeticException if the resulting numerator or denominator 730 * cannot be represented in an <code>int</code>. 731 */ 732 private Fraction addSub(final Fraction fraction, final boolean isAdd) { 733 Validate.isTrue(fraction != null, "The fraction must not be null"); 734 // zero is identity for addition. 735 if (numerator == 0) { 736 return isAdd ? fraction : fraction.negate(); 737 } 738 if (fraction.numerator == 0) { 739 return this; 740 } 741 // if denominators are randomly distributed, d1 will be 1 about 61% 742 // of the time. 743 final int d1 = greatestCommonDivisor(denominator, fraction.denominator); 744 if (d1 == 1) { 745 // result is ( (u*v' +/- u'v) / u'v') 746 final int uvp = mulAndCheck(numerator, fraction.denominator); 747 final int upv = mulAndCheck(fraction.numerator, denominator); 748 return new Fraction(isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv), mulPosAndCheck(denominator, 749 fraction.denominator)); 750 } 751 // the quantity 't' requires 65 bits of precision; see knuth 4.5.1 752 // exercise 7. we're going to use a BigInteger. 753 // t = u(v'/d1) +/- v(u'/d1) 754 final BigInteger uvp = BigInteger.valueOf(numerator).multiply(BigInteger.valueOf(fraction.denominator / d1)); 755 final BigInteger upv = BigInteger.valueOf(fraction.numerator).multiply(BigInteger.valueOf(denominator / d1)); 756 final BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv); 757 // but d2 doesn't need extra precision because 758 // d2 = gcd(t,d1) = gcd(t mod d1, d1) 759 final int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue(); 760 final int d2 = tmodd1 == 0 ? d1 : greatestCommonDivisor(tmodd1, d1); 761 762 // result is (t/d2) / (u'/d1)(v'/d2) 763 final BigInteger w = t.divide(BigInteger.valueOf(d2)); 764 if (w.bitLength() > 31) { 765 throw new ArithmeticException("overflow: numerator too large after multiply"); 766 } 767 return new Fraction(w.intValue(), mulPosAndCheck(denominator / d1, fraction.denominator / d2)); 768 } 769 770 /** 771 * <p>Multiplies the value of this fraction by another, returning the 772 * result in reduced form.</p> 773 * 774 * @param fraction the fraction to multiply by, must not be <code>null</code> 775 * @return a <code>Fraction</code> instance with the resulting values 776 * @throws IllegalArgumentException if the fraction is <code>null</code> 777 * @throws ArithmeticException if the resulting numerator or denominator exceeds 778 * <code>Integer.MAX_VALUE</code> 779 */ 780 public Fraction multiplyBy(final Fraction fraction) { 781 Validate.isTrue(fraction != null, "The fraction must not be null"); 782 if (numerator == 0 || fraction.numerator == 0) { 783 return ZERO; 784 } 785 // knuth 4.5.1 786 // make sure we don't overflow unless the result *must* overflow. 787 final int d1 = greatestCommonDivisor(numerator, fraction.denominator); 788 final int d2 = greatestCommonDivisor(fraction.numerator, denominator); 789 return getReducedFraction(mulAndCheck(numerator / d1, fraction.numerator / d2), 790 mulPosAndCheck(denominator / d2, fraction.denominator / d1)); 791 } 792 793 /** 794 * <p>Divide the value of this fraction by another.</p> 795 * 796 * @param fraction the fraction to divide by, must not be <code>null</code> 797 * @return a <code>Fraction</code> instance with the resulting values 798 * @throws IllegalArgumentException if the fraction is <code>null</code> 799 * @throws ArithmeticException if the fraction to divide by is zero 800 * @throws ArithmeticException if the resulting numerator or denominator exceeds 801 * <code>Integer.MAX_VALUE</code> 802 */ 803 public Fraction divideBy(final Fraction fraction) { 804 Validate.isTrue(fraction != null, "The fraction must not be null"); 805 if (fraction.numerator == 0) { 806 throw new ArithmeticException("The fraction to divide by must not be zero"); 807 } 808 return multiplyBy(fraction.invert()); 809 } 810 811 // Basics 812 //------------------------------------------------------------------- 813 814 /** 815 * <p>Compares this fraction to another object to test if they are equal.</p>. 816 * 817 * <p>To be equal, both values must be equal. Thus 2/4 is not equal to 1/2.</p> 818 * 819 * @param obj the reference object with which to compare 820 * @return <code>true</code> if this object is equal 821 */ 822 @Override 823 public boolean equals(final Object obj) { 824 if (obj == this) { 825 return true; 826 } 827 if (!(obj instanceof Fraction)) { 828 return false; 829 } 830 final Fraction other = (Fraction) obj; 831 return getNumerator() == other.getNumerator() && getDenominator() == other.getDenominator(); 832 } 833 834 /** 835 * <p>Gets a hashCode for the fraction.</p> 836 * 837 * @return a hash code value for this object 838 */ 839 @Override 840 public int hashCode() { 841 if (hashCode == 0) { 842 // hash code update should be atomic. 843 hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator(); 844 } 845 return hashCode; 846 } 847 848 /** 849 * <p>Compares this object to another based on size.</p> 850 * 851 * <p>Note: this class has a natural ordering that is inconsistent 852 * with equals, because, for example, equals treats 1/2 and 2/4 as 853 * different, whereas compareTo treats them as equal. 854 * 855 * @param other the object to compare to 856 * @return -1 if this is less, 0 if equal, +1 if greater 857 * @throws ClassCastException if the object is not a <code>Fraction</code> 858 * @throws NullPointerException if the object is <code>null</code> 859 */ 860 @Override 861 public int compareTo(final Fraction other) { 862 if (this == other) { 863 return 0; 864 } 865 if (numerator == other.numerator && denominator == other.denominator) { 866 return 0; 867 } 868 869 // otherwise see which is less 870 final long first = (long) numerator * (long) other.denominator; 871 final long second = (long) other.numerator * (long) denominator; 872 if (first == second) { 873 return 0; 874 } else if (first < second) { 875 return -1; 876 } else { 877 return 1; 878 } 879 } 880 881 /** 882 * <p>Gets the fraction as a <code>String</code>.</p> 883 * 884 * <p>The format used is '<i>numerator</i>/<i>denominator</i>' always. 885 * 886 * @return a <code>String</code> form of the fraction 887 */ 888 @Override 889 public String toString() { 890 if (toString == null) { 891 toString = getNumerator() + "/" + getDenominator(); 892 } 893 return toString; 894 } 895 896 /** 897 * <p>Gets the fraction as a proper <code>String</code> in the format X Y/Z.</p> 898 * 899 * <p>The format used in '<i>wholeNumber</i> <i>numerator</i>/<i>denominator</i>'. 900 * If the whole number is zero it will be omitted. If the numerator is zero, 901 * only the whole number is returned.</p> 902 * 903 * @return a <code>String</code> form of the fraction 904 */ 905 public String toProperString() { 906 if (toProperString == null) { 907 if (numerator == 0) { 908 toProperString = "0"; 909 } else if (numerator == denominator) { 910 toProperString = "1"; 911 } else if (numerator == -1 * denominator) { 912 toProperString = "-1"; 913 } else if ((numerator > 0 ? -numerator : numerator) < -denominator) { 914 // note that we do the magnitude comparison test above with 915 // NEGATIVE (not positive) numbers, since negative numbers 916 // have a larger range. otherwise numerator==Integer.MIN_VALUE 917 // is handled incorrectly. 918 final int properNumerator = getProperNumerator(); 919 if (properNumerator == 0) { 920 toProperString = Integer.toString(getProperWhole()); 921 } else { 922 toProperString = getProperWhole() + " " + properNumerator + "/" + getDenominator(); 923 } 924 } else { 925 toProperString = getNumerator() + "/" + getDenominator(); 926 } 927 } 928 return toProperString; 929 } 930}