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