1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package org.apache.commons.math.fraction;
17
18 import java.math.BigInteger;
19 import org.apache.commons.math.ConvergenceException;
20 import org.apache.commons.math.util.MathUtils;
21
22 /**
23 * Representation of a rational number.
24 *
25 * @since 1.1
26 * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
27 */
28 public class Fraction extends Number implements Comparable {
29
30 /** A fraction representing "1 / 1". */
31 public static final Fraction ONE = new Fraction(1, 1);
32
33 /** A fraction representing "0 / 1". */
34 public static final Fraction ZERO = new Fraction(0, 1);
35
36 /** Serializable version identifier */
37 private static final long serialVersionUID = 65382027393090L;
38
39 /** The denominator. */
40 private int denominator;
41
42 /** The numerator. */
43 private int numerator;
44
45 /**
46 * Create a fraction given the double value.
47 * @param value the double value to convert to a fraction.
48 * @throws ConvergenceException if the continued fraction failed to
49 * converge.
50 */
51 public Fraction(double value) throws ConvergenceException {
52 this(value, 1.0e-5, 100);
53 }
54
55 /**
56 * Create a fraction given the double value.
57 * <p>
58 * References:
59 * <ul>
60 * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
61 * Continued Fraction</a> equations (11) and (22)-(26)</li>
62 * </ul>
63 * </p>
64 * @param value the double value to convert to a fraction.
65 * @param epsilon maximum error allowed. The resulting fraction is within
66 * <code>epsilon</code> of <code>value</code>, in absolute terms.
67 * @param maxIterations maximum number of convergents
68 * @throws ConvergenceException if the continued fraction failed to
69 * converge.
70 */
71 public Fraction(double value, double epsilon, int maxIterations)
72 throws ConvergenceException
73 {
74 double r0 = value;
75 int a0 = (int)Math.floor(r0);
76
77
78
79 if (Math.abs(a0 - value) < epsilon) {
80 this.numerator = a0;
81 this.denominator = 1;
82 return;
83 }
84
85 int p0 = 1;
86 int q0 = 0;
87 int p1 = a0;
88 int q1 = 1;
89
90 int p2 = 0;
91 int q2 = 1;
92
93 int n = 0;
94 boolean stop = false;
95 do {
96 ++n;
97 double r1 = 1.0 / (r0 - a0);
98 int a1 = (int)Math.floor(r1);
99 p2 = (a1 * p1) + p0;
100 q2 = (a1 * q1) + q0;
101
102 double convergent = (double)p2 / (double)q2;
103 if (n < maxIterations && Math.abs(convergent - value) > epsilon) {
104 p0 = p1;
105 p1 = p2;
106 q0 = q1;
107 q1 = q2;
108 a0 = a1;
109 r0 = r1;
110 } else {
111 stop = true;
112 }
113 } while (!stop);
114
115 if (n >= maxIterations) {
116 throw new ConvergenceException(
117 "Unable to convert double to fraction");
118 }
119
120 this.numerator = p2;
121 this.denominator = q2;
122 reduce();
123 }
124
125 /**
126 * Create a fraction given the numerator and denominator. The fraction is
127 * reduced to lowest terms.
128 * @param num the numerator.
129 * @param den the denominator.
130 * @throws ArithmeticException if the denomiator is <code>zero</code>
131 */
132 public Fraction(int num, int den) {
133 super();
134 if (den == 0) {
135 throw new ArithmeticException("The denominator must not be zero");
136 }
137 if (den < 0) {
138 if (num == Integer.MIN_VALUE ||
139 den == Integer.MIN_VALUE) {
140 throw new ArithmeticException("overflow: can't negate");
141 }
142 num = -num;
143 den = -den;
144 }
145 this.numerator = num;
146 this.denominator = den;
147 reduce();
148 }
149
150 /**
151 * Returns the absolute value of this fraction.
152 * @return the absolute value.
153 */
154 public Fraction abs() {
155 Fraction ret;
156 if (numerator >= 0) {
157 ret = this;
158 } else {
159 ret = negate();
160 }
161 return ret;
162 }
163
164 /**
165 * Compares this object to another based on size.
166 * @param object the object to compare to
167 * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
168 * than <tt>object</tt>, 0 if they are equal.
169 */
170 public int compareTo(Object object) {
171 int ret = 0;
172
173 if (this != object) {
174 Fraction other = (Fraction)object;
175 double first = doubleValue();
176 double second = other.doubleValue();
177
178 if (first < second) {
179 ret = -1;
180 } else if (first > second) {
181 ret = 1;
182 }
183 }
184
185 return ret;
186 }
187
188 /**
189 * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
190 * the numerator divided by denominator.
191 * @return the fraction as a <tt>double</tt>
192 */
193 public double doubleValue() {
194 return (double)numerator / (double)denominator;
195 }
196
197 /**
198 * Test for the equality of two fractions. If the lowest term
199 * numerator and denominators are the same for both fractions, the two
200 * fractions are considered to be equal.
201 * @param other fraction to test for equality to this fraction
202 * @return true if two fractions are equal, false if object is
203 * <tt>null</tt>, not an instance of {@link Fraction}, or not equal
204 * to this fraction instance.
205 */
206 public boolean equals(Object other) {
207 boolean ret;
208
209 if (this == other) {
210 ret = true;
211 } else if (other == null) {
212 ret = false;
213 } else {
214 try {
215
216
217 Fraction rhs = (Fraction)other;
218 ret = (numerator == rhs.numerator) &&
219 (denominator == rhs.denominator);
220 } catch (ClassCastException ex) {
221
222 ret = false;
223 }
224 }
225
226 return ret;
227 }
228
229 /**
230 * Gets the fraction as a <tt>float</tt>. This calculates the fraction as
231 * the numerator divided by denominator.
232 * @return the fraction as a <tt>float</tt>
233 */
234 public float floatValue() {
235 return (float)doubleValue();
236 }
237
238 /**
239 * Access the denominator.
240 * @return the denominator.
241 */
242 public int getDenominator() {
243 return denominator;
244 }
245
246 /**
247 * Access the numerator.
248 * @return the numerator.
249 */
250 public int getNumerator() {
251 return numerator;
252 }
253
254 /**
255 * Gets a hashCode for the fraction.
256 * @return a hash code value for this object
257 */
258 public int hashCode() {
259 return 37 * (37 * 17 + getNumerator()) + getDenominator();
260 }
261
262 /**
263 * Gets the fraction as an <tt>int</tt>. This returns the whole number part
264 * of the fraction.
265 * @return the whole number fraction part
266 */
267 public int intValue() {
268 return (int)doubleValue();
269 }
270
271 /**
272 * Gets the fraction as a <tt>long</tt>. This returns the whole number part
273 * of the fraction.
274 * @return the whole number fraction part
275 */
276 public long longValue() {
277 return (long)doubleValue();
278 }
279
280 /**
281 * Return the additive inverse of this fraction.
282 * @return the negation of this fraction.
283 */
284 public Fraction negate() {
285 if (numerator==Integer.MIN_VALUE) {
286 throw new ArithmeticException("overflow: too large to negate");
287 }
288 return new Fraction(-numerator, denominator);
289 }
290
291 /**
292 * Return the multiplicative inverse of this fraction.
293 * @return the reciprocal fraction
294 */
295 public Fraction reciprocal() {
296 return new Fraction(denominator, numerator);
297 }
298
299 /**
300 * <p>Adds the value of this fraction to another, returning the result in reduced form.
301 * The algorithm follows Knuth, 4.5.1.</p>
302 *
303 * @param fraction the fraction to add, must not be <code>null</code>
304 * @return a <code>Fraction</code> instance with the resulting values
305 * @throws IllegalArgumentException if the fraction is <code>null</code>
306 * @throws ArithmeticException if the resulting numerator or denominator exceeds
307 * <code>Integer.MAX_VALUE</code>
308 */
309 public Fraction add(Fraction fraction) {
310 return addSub(fraction, true
311 }
312
313 /**
314 * <p>Subtracts the value of another fraction from the value of this one,
315 * returning the result in reduced form.</p>
316 *
317 * @param fraction the fraction to subtract, must not be <code>null</code>
318 * @return a <code>Fraction</code> instance with the resulting values
319 * @throws IllegalArgumentException if the fraction is <code>null</code>
320 * @throws ArithmeticException if the resulting numerator or denominator
321 * cannot be represented in an <code>int</code>.
322 */
323 public Fraction subtract(Fraction fraction) {
324 return addSub(fraction, false
325 }
326
327 /**
328 * Implement add and subtract using algorithm described in Knuth 4.5.1.
329 *
330 * @param fraction the fraction to subtract, must not be <code>null</code>
331 * @param isAdd true to add, false to subtract
332 * @return a <code>Fraction</code> instance with the resulting values
333 * @throws IllegalArgumentException if the fraction is <code>null</code>
334 * @throws ArithmeticException if the resulting numerator or denominator
335 * cannot be represented in an <code>int</code>.
336 */
337 private Fraction addSub(Fraction fraction, boolean isAdd) {
338 if (fraction == null) {
339 throw new IllegalArgumentException("The fraction must not be null");
340 }
341
342 if (numerator == 0) {
343 return isAdd ? fraction : fraction.negate();
344 }
345 if (fraction.numerator == 0) {
346 return this;
347 }
348
349
350 int d1 = MathUtils.gcd(denominator, fraction.denominator);
351 if (d1==1) {
352
353 int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
354 int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
355 return new Fraction
356 (isAdd ? MathUtils.addAndCheck(uvp, upv) :
357 MathUtils.subAndCheck(uvp, upv),
358 MathUtils.mulAndCheck(denominator, fraction.denominator));
359 }
360
361
362
363 BigInteger uvp = BigInteger.valueOf(numerator)
364 .multiply(BigInteger.valueOf(fraction.denominator/d1));
365 BigInteger upv = BigInteger.valueOf(fraction.numerator)
366 .multiply(BigInteger.valueOf(denominator/d1));
367 BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
368
369
370 int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
371 int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1);
372
373
374 BigInteger w = t.divide(BigInteger.valueOf(d2));
375 if (w.bitLength() > 31) {
376 throw new ArithmeticException
377 ("overflow: numerator too large after multiply");
378 }
379 return new Fraction (w.intValue(),
380 MathUtils.mulAndCheck(denominator/d1,
381 fraction.denominator/d2));
382 }
383
384 /**
385 * <p>Multiplies the value of this fraction by another, returning the
386 * result in reduced form.</p>
387 *
388 * @param fraction the fraction to multiply by, must not be <code>null</code>
389 * @return a <code>Fraction</code> instance with the resulting values
390 * @throws IllegalArgumentException if the fraction is <code>null</code>
391 * @throws ArithmeticException if the resulting numerator or denominator exceeds
392 * <code>Integer.MAX_VALUE</code>
393 */
394 public Fraction multiply(Fraction fraction) {
395 if (fraction == null) {
396 throw new IllegalArgumentException("The fraction must not be null");
397 }
398 if (numerator == 0 || fraction.numerator == 0) {
399 return ZERO;
400 }
401
402
403 int d1 = MathUtils.gcd(numerator, fraction.denominator);
404 int d2 = MathUtils.gcd(fraction.numerator, denominator);
405 return getReducedFraction
406 (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
407 MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
408 }
409
410 /**
411 * <p>Divide the value of this fraction by another.</p>
412 *
413 * @param fraction the fraction to divide by, must not be <code>null</code>
414 * @return a <code>Fraction</code> instance with the resulting values
415 * @throws IllegalArgumentException if the fraction is <code>null</code>
416 * @throws ArithmeticException if the fraction to divide by is zero
417 * @throws ArithmeticException if the resulting numerator or denominator exceeds
418 * <code>Integer.MAX_VALUE</code>
419 */
420 public Fraction divide(Fraction fraction) {
421 if (fraction == null) {
422 throw new IllegalArgumentException("The fraction must not be null");
423 }
424 if (fraction.numerator == 0) {
425 throw new ArithmeticException("The fraction to divide by must not be zero");
426 }
427 return multiply(fraction.reciprocal());
428 }
429
430 /**
431 * <p>Creates a <code>Fraction</code> instance with the 2 parts
432 * of a fraction Y/Z.</p>
433 *
434 * <p>Any negative signs are resolved to be on the numerator.</p>
435 *
436 * @param numerator the numerator, for example the three in 'three sevenths'
437 * @param denominator the denominator, for example the seven in 'three sevenths'
438 * @return a new fraction instance, with the numerator and denominator reduced
439 * @throws ArithmeticException if the denominator is <code>zero</code>
440 */
441 public static Fraction getReducedFraction(int numerator, int denominator) {
442 if (denominator == 0) {
443 throw new ArithmeticException("The denominator must not be zero");
444 }
445 if (numerator==0) {
446 return ZERO;
447 }
448
449 if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
450 numerator/=2; denominator/=2;
451 }
452 if (denominator < 0) {
453 if (numerator==Integer.MIN_VALUE ||
454 denominator==Integer.MIN_VALUE) {
455 throw new ArithmeticException("overflow: can't negate");
456 }
457 numerator = -numerator;
458 denominator = -denominator;
459 }
460
461 int gcd = MathUtils.gcd(numerator, denominator);
462 numerator /= gcd;
463 denominator /= gcd;
464 return new Fraction(numerator, denominator);
465 }
466
467 /**
468 * Reduce this fraction to lowest terms. This is accomplished by dividing
469 * both numerator and denominator by their greatest common divisor.
470 */
471 private void reduce() {
472
473 int d = MathUtils.gcd(numerator, denominator);
474 if (d > 1) {
475 numerator /= d;
476 denominator /= d;
477 }
478
479
480 if (denominator < 0) {
481 numerator *= -1;
482 denominator *= -1;
483 }
484 }
485 }