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 agents.org.apache.commons.math.fraction;
|
---|
18 |
|
---|
19 | import java.io.Serializable;
|
---|
20 | import java.math.BigInteger;
|
---|
21 |
|
---|
22 | import agents.org.apache.commons.math.FieldElement;
|
---|
23 | import agents.org.apache.commons.math.MathRuntimeException;
|
---|
24 | import agents.org.apache.commons.math.exception.NullArgumentException;
|
---|
25 | import agents.org.apache.commons.math.exception.util.LocalizedFormats;
|
---|
26 | import agents.org.apache.commons.math.util.FastMath;
|
---|
27 | import agents.org.apache.commons.math.util.MathUtils;
|
---|
28 |
|
---|
29 | /**
|
---|
30 | * Representation of a rational number.
|
---|
31 | *
|
---|
32 | * implements Serializable since 2.0
|
---|
33 | *
|
---|
34 | * @since 1.1
|
---|
35 | * @version $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $
|
---|
36 | */
|
---|
37 | public class Fraction
|
---|
38 | extends Number
|
---|
39 | implements FieldElement<Fraction>, Comparable<Fraction>, Serializable {
|
---|
40 |
|
---|
41 | /** A fraction representing "2 / 1". */
|
---|
42 | public static final Fraction TWO = new Fraction(2, 1);
|
---|
43 |
|
---|
44 | /** A fraction representing "1". */
|
---|
45 | public static final Fraction ONE = new Fraction(1, 1);
|
---|
46 |
|
---|
47 | /** A fraction representing "0". */
|
---|
48 | public static final Fraction ZERO = new Fraction(0, 1);
|
---|
49 |
|
---|
50 | /** A fraction representing "4/5". */
|
---|
51 | public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
|
---|
52 |
|
---|
53 | /** A fraction representing "1/5". */
|
---|
54 | public static final Fraction ONE_FIFTH = new Fraction(1, 5);
|
---|
55 |
|
---|
56 | /** A fraction representing "1/2". */
|
---|
57 | public static final Fraction ONE_HALF = new Fraction(1, 2);
|
---|
58 |
|
---|
59 | /** A fraction representing "1/4". */
|
---|
60 | public static final Fraction ONE_QUARTER = new Fraction(1, 4);
|
---|
61 |
|
---|
62 | /** A fraction representing "1/3". */
|
---|
63 | public static final Fraction ONE_THIRD = new Fraction(1, 3);
|
---|
64 |
|
---|
65 | /** A fraction representing "3/5". */
|
---|
66 | public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
|
---|
67 |
|
---|
68 | /** A fraction representing "3/4". */
|
---|
69 | public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
|
---|
70 |
|
---|
71 | /** A fraction representing "2/5". */
|
---|
72 | public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
|
---|
73 |
|
---|
74 | /** A fraction representing "2/4". */
|
---|
75 | public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
|
---|
76 |
|
---|
77 | /** A fraction representing "2/3". */
|
---|
78 | public static final Fraction TWO_THIRDS = new Fraction(2, 3);
|
---|
79 |
|
---|
80 | /** A fraction representing "-1 / 1". */
|
---|
81 | public static final Fraction MINUS_ONE = new Fraction(-1, 1);
|
---|
82 |
|
---|
83 | /** Serializable version identifier */
|
---|
84 | private static final long serialVersionUID = 3698073679419233275L;
|
---|
85 |
|
---|
86 | /** The denominator. */
|
---|
87 | private final int denominator;
|
---|
88 |
|
---|
89 | /** The numerator. */
|
---|
90 | private final int numerator;
|
---|
91 |
|
---|
92 | /**
|
---|
93 | * Create a fraction given the double value.
|
---|
94 | * @param value the double value to convert to a fraction.
|
---|
95 | * @throws FractionConversionException if the continued fraction failed to
|
---|
96 | * converge.
|
---|
97 | */
|
---|
98 | public Fraction(double value) throws FractionConversionException {
|
---|
99 | this(value, 1.0e-5, 100);
|
---|
100 | }
|
---|
101 |
|
---|
102 | /**
|
---|
103 | * Create a fraction given the double value and maximum error allowed.
|
---|
104 | * <p>
|
---|
105 | * References:
|
---|
106 | * <ul>
|
---|
107 | * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
|
---|
108 | * Continued Fraction</a> equations (11) and (22)-(26)</li>
|
---|
109 | * </ul>
|
---|
110 | * </p>
|
---|
111 | * @param value the double value to convert to a fraction.
|
---|
112 | * @param epsilon maximum error allowed. The resulting fraction is within
|
---|
113 | * <code>epsilon</code> of <code>value</code>, in absolute terms.
|
---|
114 | * @param maxIterations maximum number of convergents
|
---|
115 | * @throws FractionConversionException if the continued fraction failed to
|
---|
116 | * converge.
|
---|
117 | */
|
---|
118 | public Fraction(double value, double epsilon, int maxIterations)
|
---|
119 | throws FractionConversionException
|
---|
120 | {
|
---|
121 | this(value, epsilon, Integer.MAX_VALUE, maxIterations);
|
---|
122 | }
|
---|
123 |
|
---|
124 | /**
|
---|
125 | * Create a fraction given the double value and maximum denominator.
|
---|
126 | * <p>
|
---|
127 | * References:
|
---|
128 | * <ul>
|
---|
129 | * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
|
---|
130 | * Continued Fraction</a> equations (11) and (22)-(26)</li>
|
---|
131 | * </ul>
|
---|
132 | * </p>
|
---|
133 | * @param value the double value to convert to a fraction.
|
---|
134 | * @param maxDenominator The maximum allowed value for denominator
|
---|
135 | * @throws FractionConversionException if the continued fraction failed to
|
---|
136 | * converge
|
---|
137 | */
|
---|
138 | public Fraction(double value, int maxDenominator)
|
---|
139 | throws FractionConversionException
|
---|
140 | {
|
---|
141 | this(value, 0, maxDenominator, 100);
|
---|
142 | }
|
---|
143 |
|
---|
144 | /**
|
---|
145 | * Create a fraction given the double value and either the maximum error
|
---|
146 | * allowed or the maximum number of denominator digits.
|
---|
147 | * <p>
|
---|
148 | *
|
---|
149 | * NOTE: This constructor is called with EITHER
|
---|
150 | * - a valid epsilon value and the maxDenominator set to Integer.MAX_VALUE
|
---|
151 | * (that way the maxDenominator has no effect).
|
---|
152 | * OR
|
---|
153 | * - a valid maxDenominator value and the epsilon value set to zero
|
---|
154 | * (that way epsilon only has effect if there is an exact match before
|
---|
155 | * the maxDenominator value is reached).
|
---|
156 | * </p><p>
|
---|
157 | *
|
---|
158 | * It has been done this way so that the same code can be (re)used for both
|
---|
159 | * scenarios. However this could be confusing to users if it were part of
|
---|
160 | * the public API and this constructor should therefore remain PRIVATE.
|
---|
161 | * </p>
|
---|
162 | *
|
---|
163 | * See JIRA issue ticket MATH-181 for more details:
|
---|
164 | *
|
---|
165 | * https://issues.apache.org/jira/browse/MATH-181
|
---|
166 | *
|
---|
167 | * @param value the double value to convert to a fraction.
|
---|
168 | * @param epsilon maximum error allowed. The resulting fraction is within
|
---|
169 | * <code>epsilon</code> of <code>value</code>, in absolute terms.
|
---|
170 | * @param maxDenominator maximum denominator value allowed.
|
---|
171 | * @param maxIterations maximum number of convergents
|
---|
172 | * @throws FractionConversionException if the continued fraction failed to
|
---|
173 | * converge.
|
---|
174 | */
|
---|
175 | private Fraction(double value, double epsilon, int maxDenominator, int maxIterations)
|
---|
176 | throws FractionConversionException
|
---|
177 | {
|
---|
178 | long overflow = Integer.MAX_VALUE;
|
---|
179 | double r0 = value;
|
---|
180 | long a0 = (long)FastMath.floor(r0);
|
---|
181 | if (a0 > overflow) {
|
---|
182 | throw new FractionConversionException(value, a0, 1l);
|
---|
183 | }
|
---|
184 |
|
---|
185 | // check for (almost) integer arguments, which should not go
|
---|
186 | // to iterations.
|
---|
187 | if (FastMath.abs(a0 - value) < epsilon) {
|
---|
188 | this.numerator = (int) a0;
|
---|
189 | this.denominator = 1;
|
---|
190 | return;
|
---|
191 | }
|
---|
192 |
|
---|
193 | long p0 = 1;
|
---|
194 | long q0 = 0;
|
---|
195 | long p1 = a0;
|
---|
196 | long q1 = 1;
|
---|
197 |
|
---|
198 | long p2 = 0;
|
---|
199 | long q2 = 1;
|
---|
200 |
|
---|
201 | int n = 0;
|
---|
202 | boolean stop = false;
|
---|
203 | do {
|
---|
204 | ++n;
|
---|
205 | double r1 = 1.0 / (r0 - a0);
|
---|
206 | long a1 = (long)FastMath.floor(r1);
|
---|
207 | p2 = (a1 * p1) + p0;
|
---|
208 | q2 = (a1 * q1) + q0;
|
---|
209 | if ((p2 > overflow) || (q2 > overflow)) {
|
---|
210 | throw new FractionConversionException(value, p2, q2);
|
---|
211 | }
|
---|
212 |
|
---|
213 | double convergent = (double)p2 / (double)q2;
|
---|
214 | if (n < maxIterations && FastMath.abs(convergent - value) > epsilon && q2 < maxDenominator) {
|
---|
215 | p0 = p1;
|
---|
216 | p1 = p2;
|
---|
217 | q0 = q1;
|
---|
218 | q1 = q2;
|
---|
219 | a0 = a1;
|
---|
220 | r0 = r1;
|
---|
221 | } else {
|
---|
222 | stop = true;
|
---|
223 | }
|
---|
224 | } while (!stop);
|
---|
225 |
|
---|
226 | if (n >= maxIterations) {
|
---|
227 | throw new FractionConversionException(value, maxIterations);
|
---|
228 | }
|
---|
229 |
|
---|
230 | if (q2 < maxDenominator) {
|
---|
231 | this.numerator = (int) p2;
|
---|
232 | this.denominator = (int) q2;
|
---|
233 | } else {
|
---|
234 | this.numerator = (int) p1;
|
---|
235 | this.denominator = (int) q1;
|
---|
236 | }
|
---|
237 |
|
---|
238 | }
|
---|
239 |
|
---|
240 | /**
|
---|
241 | * Create a fraction from an int.
|
---|
242 | * The fraction is num / 1.
|
---|
243 | * @param num the numerator.
|
---|
244 | */
|
---|
245 | public Fraction(int num) {
|
---|
246 | this(num, 1);
|
---|
247 | }
|
---|
248 |
|
---|
249 | /**
|
---|
250 | * Create a fraction given the numerator and denominator. The fraction is
|
---|
251 | * reduced to lowest terms.
|
---|
252 | * @param num the numerator.
|
---|
253 | * @param den the denominator.
|
---|
254 | * @throws ArithmeticException if the denominator is <code>zero</code>
|
---|
255 | */
|
---|
256 | public Fraction(int num, int den) {
|
---|
257 | if (den == 0) {
|
---|
258 | throw MathRuntimeException.createArithmeticException(
|
---|
259 | LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION, num, den);
|
---|
260 | }
|
---|
261 | if (den < 0) {
|
---|
262 | if (num == Integer.MIN_VALUE || den == Integer.MIN_VALUE) {
|
---|
263 | throw MathRuntimeException.createArithmeticException(
|
---|
264 | LocalizedFormats.OVERFLOW_IN_FRACTION, num, den);
|
---|
265 | }
|
---|
266 | num = -num;
|
---|
267 | den = -den;
|
---|
268 | }
|
---|
269 | // reduce numerator and denominator by greatest common denominator.
|
---|
270 | final int d = MathUtils.gcd(num, den);
|
---|
271 | if (d > 1) {
|
---|
272 | num /= d;
|
---|
273 | den /= d;
|
---|
274 | }
|
---|
275 |
|
---|
276 | // move sign to numerator.
|
---|
277 | if (den < 0) {
|
---|
278 | num = -num;
|
---|
279 | den = -den;
|
---|
280 | }
|
---|
281 | this.numerator = num;
|
---|
282 | this.denominator = den;
|
---|
283 | }
|
---|
284 |
|
---|
285 | /**
|
---|
286 | * Returns the absolute value of this fraction.
|
---|
287 | * @return the absolute value.
|
---|
288 | */
|
---|
289 | public Fraction abs() {
|
---|
290 | Fraction ret;
|
---|
291 | if (numerator >= 0) {
|
---|
292 | ret = this;
|
---|
293 | } else {
|
---|
294 | ret = negate();
|
---|
295 | }
|
---|
296 | return ret;
|
---|
297 | }
|
---|
298 |
|
---|
299 | /**
|
---|
300 | * Compares this object to another based on size.
|
---|
301 | * @param object the object to compare to
|
---|
302 | * @return -1 if this is less than <tt>object</tt>, +1 if this is greater
|
---|
303 | * than <tt>object</tt>, 0 if they are equal.
|
---|
304 | */
|
---|
305 | public int compareTo(Fraction object) {
|
---|
306 | long nOd = ((long) numerator) * object.denominator;
|
---|
307 | long dOn = ((long) denominator) * object.numerator;
|
---|
308 | return (nOd < dOn) ? -1 : ((nOd > dOn) ? +1 : 0);
|
---|
309 | }
|
---|
310 |
|
---|
311 | /**
|
---|
312 | * Gets the fraction as a <tt>double</tt>. This calculates the fraction as
|
---|
313 | * the numerator divided by denominator.
|
---|
314 | * @return the fraction as a <tt>double</tt>
|
---|
315 | */
|
---|
316 | @Override
|
---|
317 | public double doubleValue() {
|
---|
318 | return (double)numerator / (double)denominator;
|
---|
319 | }
|
---|
320 |
|
---|
321 | /**
|
---|
322 | * Test for the equality of two fractions. If the lowest term
|
---|
323 | * numerator and denominators are the same for both fractions, the two
|
---|
324 | * fractions are considered to be equal.
|
---|
325 | * @param other fraction to test for equality to this fraction
|
---|
326 | * @return true if two fractions are equal, false if object is
|
---|
327 | * <tt>null</tt>, not an instance of {@link Fraction}, or not equal
|
---|
328 | * to this fraction instance.
|
---|
329 | */
|
---|
330 | @Override
|
---|
331 | public boolean equals(Object other) {
|
---|
332 | if (this == other) {
|
---|
333 | return true;
|
---|
334 | }
|
---|
335 | if (other instanceof Fraction) {
|
---|
336 | // since fractions are always in lowest terms, numerators and
|
---|
337 | // denominators can be compared directly for equality.
|
---|
338 | Fraction rhs = (Fraction)other;
|
---|
339 | return (numerator == rhs.numerator) &&
|
---|
340 | (denominator == rhs.denominator);
|
---|
341 | }
|
---|
342 | return false;
|
---|
343 | }
|
---|
344 |
|
---|
345 | /**
|
---|
346 | * Gets the fraction as a <tt>float</tt>. This calculates the fraction as
|
---|
347 | * the numerator divided by denominator.
|
---|
348 | * @return the fraction as a <tt>float</tt>
|
---|
349 | */
|
---|
350 | @Override
|
---|
351 | public float floatValue() {
|
---|
352 | return (float)doubleValue();
|
---|
353 | }
|
---|
354 |
|
---|
355 | /**
|
---|
356 | * Access the denominator.
|
---|
357 | * @return the denominator.
|
---|
358 | */
|
---|
359 | public int getDenominator() {
|
---|
360 | return denominator;
|
---|
361 | }
|
---|
362 |
|
---|
363 | /**
|
---|
364 | * Access the numerator.
|
---|
365 | * @return the numerator.
|
---|
366 | */
|
---|
367 | public int getNumerator() {
|
---|
368 | return numerator;
|
---|
369 | }
|
---|
370 |
|
---|
371 | /**
|
---|
372 | * Gets a hashCode for the fraction.
|
---|
373 | * @return a hash code value for this object
|
---|
374 | */
|
---|
375 | @Override
|
---|
376 | public int hashCode() {
|
---|
377 | return 37 * (37 * 17 + numerator) + denominator;
|
---|
378 | }
|
---|
379 |
|
---|
380 | /**
|
---|
381 | * Gets the fraction as an <tt>int</tt>. This returns the whole number part
|
---|
382 | * of the fraction.
|
---|
383 | * @return the whole number fraction part
|
---|
384 | */
|
---|
385 | @Override
|
---|
386 | public int intValue() {
|
---|
387 | return (int)doubleValue();
|
---|
388 | }
|
---|
389 |
|
---|
390 | /**
|
---|
391 | * Gets the fraction as a <tt>long</tt>. This returns the whole number part
|
---|
392 | * of the fraction.
|
---|
393 | * @return the whole number fraction part
|
---|
394 | */
|
---|
395 | @Override
|
---|
396 | public long longValue() {
|
---|
397 | return (long)doubleValue();
|
---|
398 | }
|
---|
399 |
|
---|
400 | /**
|
---|
401 | * Return the additive inverse of this fraction.
|
---|
402 | * @return the negation of this fraction.
|
---|
403 | */
|
---|
404 | public Fraction negate() {
|
---|
405 | if (numerator==Integer.MIN_VALUE) {
|
---|
406 | throw MathRuntimeException.createArithmeticException(
|
---|
407 | LocalizedFormats.OVERFLOW_IN_FRACTION, numerator, denominator);
|
---|
408 | }
|
---|
409 | return new Fraction(-numerator, denominator);
|
---|
410 | }
|
---|
411 |
|
---|
412 | /**
|
---|
413 | * Return the multiplicative inverse of this fraction.
|
---|
414 | * @return the reciprocal fraction
|
---|
415 | */
|
---|
416 | public Fraction reciprocal() {
|
---|
417 | return new Fraction(denominator, numerator);
|
---|
418 | }
|
---|
419 |
|
---|
420 | /**
|
---|
421 | * <p>Adds the value of this fraction to another, returning the result in reduced form.
|
---|
422 | * The algorithm follows Knuth, 4.5.1.</p>
|
---|
423 | *
|
---|
424 | * @param fraction the fraction to add, must not be <code>null</code>
|
---|
425 | * @return a <code>Fraction</code> instance with the resulting values
|
---|
426 | * @throws IllegalArgumentException if the fraction is <code>null</code>
|
---|
427 | * @throws ArithmeticException if the resulting numerator or denominator exceeds
|
---|
428 | * <code>Integer.MAX_VALUE</code>
|
---|
429 | */
|
---|
430 | public Fraction add(Fraction fraction) {
|
---|
431 | return addSub(fraction, true /* add */);
|
---|
432 | }
|
---|
433 |
|
---|
434 | /**
|
---|
435 | * Add an integer to the fraction.
|
---|
436 | * @param i the <tt>integer</tt> to add.
|
---|
437 | * @return this + i
|
---|
438 | */
|
---|
439 | public Fraction add(final int i) {
|
---|
440 | return new Fraction(numerator + i * denominator, denominator);
|
---|
441 | }
|
---|
442 |
|
---|
443 | /**
|
---|
444 | * <p>Subtracts the value of another fraction from the value of this one,
|
---|
445 | * returning the result in reduced form.</p>
|
---|
446 | *
|
---|
447 | * @param fraction the fraction to subtract, must not be <code>null</code>
|
---|
448 | * @return a <code>Fraction</code> instance with the resulting values
|
---|
449 | * @throws IllegalArgumentException if the fraction is <code>null</code>
|
---|
450 | * @throws ArithmeticException if the resulting numerator or denominator
|
---|
451 | * cannot be represented in an <code>int</code>.
|
---|
452 | */
|
---|
453 | public Fraction subtract(Fraction fraction) {
|
---|
454 | return addSub(fraction, false /* subtract */);
|
---|
455 | }
|
---|
456 |
|
---|
457 | /**
|
---|
458 | * Subtract an integer from the fraction.
|
---|
459 | * @param i the <tt>integer</tt> to subtract.
|
---|
460 | * @return this - i
|
---|
461 | */
|
---|
462 | public Fraction subtract(final int i) {
|
---|
463 | return new Fraction(numerator - i * denominator, denominator);
|
---|
464 | }
|
---|
465 |
|
---|
466 | /**
|
---|
467 | * Implement add and subtract using algorithm described in Knuth 4.5.1.
|
---|
468 | *
|
---|
469 | * @param fraction the fraction to subtract, must not be <code>null</code>
|
---|
470 | * @param isAdd true to add, false to subtract
|
---|
471 | * @return a <code>Fraction</code> instance with the resulting values
|
---|
472 | * @throws IllegalArgumentException if the fraction is <code>null</code>
|
---|
473 | * @throws ArithmeticException if the resulting numerator or denominator
|
---|
474 | * cannot be represented in an <code>int</code>.
|
---|
475 | */
|
---|
476 | private Fraction addSub(Fraction fraction, boolean isAdd) {
|
---|
477 | if (fraction == null) {
|
---|
478 | throw new NullArgumentException(LocalizedFormats.FRACTION);
|
---|
479 | }
|
---|
480 | // zero is identity for addition.
|
---|
481 | if (numerator == 0) {
|
---|
482 | return isAdd ? fraction : fraction.negate();
|
---|
483 | }
|
---|
484 | if (fraction.numerator == 0) {
|
---|
485 | return this;
|
---|
486 | }
|
---|
487 | // if denominators are randomly distributed, d1 will be 1 about 61%
|
---|
488 | // of the time.
|
---|
489 | int d1 = MathUtils.gcd(denominator, fraction.denominator);
|
---|
490 | if (d1==1) {
|
---|
491 | // result is ( (u*v' +/- u'v) / u'v')
|
---|
492 | int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
|
---|
493 | int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
|
---|
494 | return new Fraction
|
---|
495 | (isAdd ? MathUtils.addAndCheck(uvp, upv) :
|
---|
496 | MathUtils.subAndCheck(uvp, upv),
|
---|
497 | MathUtils.mulAndCheck(denominator, fraction.denominator));
|
---|
498 | }
|
---|
499 | // the quantity 't' requires 65 bits of precision; see knuth 4.5.1
|
---|
500 | // exercise 7. we're going to use a BigInteger.
|
---|
501 | // t = u(v'/d1) +/- v(u'/d1)
|
---|
502 | BigInteger uvp = BigInteger.valueOf(numerator)
|
---|
503 | .multiply(BigInteger.valueOf(fraction.denominator/d1));
|
---|
504 | BigInteger upv = BigInteger.valueOf(fraction.numerator)
|
---|
505 | .multiply(BigInteger.valueOf(denominator/d1));
|
---|
506 | BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
|
---|
507 | // but d2 doesn't need extra precision because
|
---|
508 | // d2 = gcd(t,d1) = gcd(t mod d1, d1)
|
---|
509 | int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
|
---|
510 | int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1);
|
---|
511 |
|
---|
512 | // result is (t/d2) / (u'/d1)(v'/d2)
|
---|
513 | BigInteger w = t.divide(BigInteger.valueOf(d2));
|
---|
514 | if (w.bitLength() > 31) {
|
---|
515 | throw MathRuntimeException.createArithmeticException(LocalizedFormats.NUMERATOR_OVERFLOW_AFTER_MULTIPLY,
|
---|
516 | w);
|
---|
517 | }
|
---|
518 | return new Fraction (w.intValue(),
|
---|
519 | MathUtils.mulAndCheck(denominator/d1,
|
---|
520 | fraction.denominator/d2));
|
---|
521 | }
|
---|
522 |
|
---|
523 | /**
|
---|
524 | * <p>Multiplies the value of this fraction by another, returning the
|
---|
525 | * result in reduced form.</p>
|
---|
526 | *
|
---|
527 | * @param fraction the fraction to multiply by, must not be <code>null</code>
|
---|
528 | * @return a <code>Fraction</code> instance with the resulting values
|
---|
529 | * @throws IllegalArgumentException if the fraction is <code>null</code>
|
---|
530 | * @throws ArithmeticException if the resulting numerator or denominator exceeds
|
---|
531 | * <code>Integer.MAX_VALUE</code>
|
---|
532 | */
|
---|
533 | public Fraction multiply(Fraction fraction) {
|
---|
534 | if (fraction == null) {
|
---|
535 | throw new NullArgumentException(LocalizedFormats.FRACTION);
|
---|
536 | }
|
---|
537 | if (numerator == 0 || fraction.numerator == 0) {
|
---|
538 | return ZERO;
|
---|
539 | }
|
---|
540 | // knuth 4.5.1
|
---|
541 | // make sure we don't overflow unless the result *must* overflow.
|
---|
542 | int d1 = MathUtils.gcd(numerator, fraction.denominator);
|
---|
543 | int d2 = MathUtils.gcd(fraction.numerator, denominator);
|
---|
544 | return getReducedFraction
|
---|
545 | (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
|
---|
546 | MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
|
---|
547 | }
|
---|
548 |
|
---|
549 | /**
|
---|
550 | * Multiply the fraction by an integer.
|
---|
551 | * @param i the <tt>integer</tt> to multiply by.
|
---|
552 | * @return this * i
|
---|
553 | */
|
---|
554 | public Fraction multiply(final int i) {
|
---|
555 | return new Fraction(numerator * i, denominator);
|
---|
556 | }
|
---|
557 |
|
---|
558 | /**
|
---|
559 | * <p>Divide the value of this fraction by another.</p>
|
---|
560 | *
|
---|
561 | * @param fraction the fraction to divide by, must not be <code>null</code>
|
---|
562 | * @return a <code>Fraction</code> instance with the resulting values
|
---|
563 | * @throws IllegalArgumentException if the fraction is <code>null</code>
|
---|
564 | * @throws ArithmeticException if the fraction to divide by is zero
|
---|
565 | * @throws ArithmeticException if the resulting numerator or denominator exceeds
|
---|
566 | * <code>Integer.MAX_VALUE</code>
|
---|
567 | */
|
---|
568 | public Fraction divide(Fraction fraction) {
|
---|
569 | if (fraction == null) {
|
---|
570 | throw new NullArgumentException(LocalizedFormats.FRACTION);
|
---|
571 | }
|
---|
572 | if (fraction.numerator == 0) {
|
---|
573 | throw MathRuntimeException.createArithmeticException(
|
---|
574 | LocalizedFormats.ZERO_FRACTION_TO_DIVIDE_BY,
|
---|
575 | fraction.numerator, fraction.denominator);
|
---|
576 | }
|
---|
577 | return multiply(fraction.reciprocal());
|
---|
578 | }
|
---|
579 |
|
---|
580 | /**
|
---|
581 | * Divide the fraction by an integer.
|
---|
582 | * @param i the <tt>integer</tt> to divide by.
|
---|
583 | * @return this * i
|
---|
584 | */
|
---|
585 | public Fraction divide(final int i) {
|
---|
586 | return new Fraction(numerator, denominator * i);
|
---|
587 | }
|
---|
588 |
|
---|
589 | /**
|
---|
590 | * <p>Creates a <code>Fraction</code> instance with the 2 parts
|
---|
591 | * of a fraction Y/Z.</p>
|
---|
592 | *
|
---|
593 | * <p>Any negative signs are resolved to be on the numerator.</p>
|
---|
594 | *
|
---|
595 | * @param numerator the numerator, for example the three in 'three sevenths'
|
---|
596 | * @param denominator the denominator, for example the seven in 'three sevenths'
|
---|
597 | * @return a new fraction instance, with the numerator and denominator reduced
|
---|
598 | * @throws ArithmeticException if the denominator is <code>zero</code>
|
---|
599 | */
|
---|
600 | public static Fraction getReducedFraction(int numerator, int denominator) {
|
---|
601 | if (denominator == 0) {
|
---|
602 | throw MathRuntimeException.createArithmeticException(
|
---|
603 | LocalizedFormats.ZERO_DENOMINATOR_IN_FRACTION, numerator, denominator);
|
---|
604 | }
|
---|
605 | if (numerator==0) {
|
---|
606 | return ZERO; // normalize zero.
|
---|
607 | }
|
---|
608 | // allow 2^k/-2^31 as a valid fraction (where k>0)
|
---|
609 | if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
|
---|
610 | numerator/=2; denominator/=2;
|
---|
611 | }
|
---|
612 | if (denominator < 0) {
|
---|
613 | if (numerator==Integer.MIN_VALUE ||
|
---|
614 | denominator==Integer.MIN_VALUE) {
|
---|
615 | throw MathRuntimeException.createArithmeticException(
|
---|
616 | LocalizedFormats.OVERFLOW_IN_FRACTION, numerator, denominator);
|
---|
617 | }
|
---|
618 | numerator = -numerator;
|
---|
619 | denominator = -denominator;
|
---|
620 | }
|
---|
621 | // simplify fraction.
|
---|
622 | int gcd = MathUtils.gcd(numerator, denominator);
|
---|
623 | numerator /= gcd;
|
---|
624 | denominator /= gcd;
|
---|
625 | return new Fraction(numerator, denominator);
|
---|
626 | }
|
---|
627 |
|
---|
628 | /**
|
---|
629 | * <p>
|
---|
630 | * Returns the <code>String</code> representing this fraction, ie
|
---|
631 | * "num / dem" or just "num" if the denominator is one.
|
---|
632 | * </p>
|
---|
633 | *
|
---|
634 | * @return a string representation of the fraction.
|
---|
635 | * @see java.lang.Object#toString()
|
---|
636 | */
|
---|
637 | @Override
|
---|
638 | public String toString() {
|
---|
639 | String str = null;
|
---|
640 | if (denominator == 1) {
|
---|
641 | str = Integer.toString(numerator);
|
---|
642 | } else if (numerator == 0) {
|
---|
643 | str = "0";
|
---|
644 | } else {
|
---|
645 | str = numerator + " / " + denominator;
|
---|
646 | }
|
---|
647 | return str;
|
---|
648 | }
|
---|
649 |
|
---|
650 | /** {@inheritDoc} */
|
---|
651 | public FractionField getField() {
|
---|
652 | return FractionField.getInstance();
|
---|
653 | }
|
---|
654 |
|
---|
655 | }
|
---|