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