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