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