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