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