1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.math.fraction;
18
19 import java.io.Serializable;
20 import java.math.BigInteger;
21
22 import org.apache.commons.math.FieldElement;
23 import org.apache.commons.math.MathRuntimeException;
24 import org.apache.commons.math.util.MathUtils;
25
26
27
28
29
30
31
32
33
34 public class Fraction
35 extends Number
36 implements FieldElement<Fraction>, Comparable<Fraction>, Serializable {
37
38
39 public static final Fraction TWO = new Fraction(2, 1);
40
41
42 public static final Fraction ONE = new Fraction(1, 1);
43
44
45 public static final Fraction ZERO = new Fraction(0, 1);
46
47
48 public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
49
50
51 public static final Fraction ONE_FIFTH = new Fraction(1, 5);
52
53
54 public static final Fraction ONE_HALF = new Fraction(1, 2);
55
56
57 public static final Fraction ONE_QUARTER = new Fraction(1, 4);
58
59
60 public static final Fraction ONE_THIRD = new Fraction(1, 3);
61
62
63 public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
64
65
66 public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
67
68
69 public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
70
71
72 public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
73
74
75 public static final Fraction TWO_THIRDS = new Fraction(2, 3);
76
77
78 public static final Fraction MINUS_ONE = new Fraction(-1, 1);
79
80
81 private static final long serialVersionUID = 3698073679419233275L;
82
83
84 private final int denominator;
85
86
87 private final int numerator;
88
89
90
91
92
93
94
95 public Fraction(double value) throws FractionConversionException {
96 this(value, 1.0e-5, 100);
97 }
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115 public Fraction(double value, double epsilon, int maxIterations)
116 throws FractionConversionException
117 {
118 this(value, epsilon, Integer.MAX_VALUE, maxIterations);
119 }
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135 public Fraction(double value, int maxDenominator)
136 throws FractionConversionException
137 {
138 this(value, 0, maxDenominator, 100);
139 }
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172 private Fraction(double value, double epsilon, int maxDenominator, int maxIterations)
173 throws FractionConversionException
174 {
175 long overflow = Integer.MAX_VALUE;
176 double r0 = value;
177 long a0 = (long)Math.floor(r0);
178 if (a0 > overflow) {
179 throw new FractionConversionException(value, a0, 1l);
180 }
181
182
183
184 if (Math.abs(a0 - value) < epsilon) {
185 this.numerator = (int) a0;
186 this.denominator = 1;
187 return;
188 }
189
190 long p0 = 1;
191 long q0 = 0;
192 long p1 = a0;
193 long q1 = 1;
194
195 long p2 = 0;
196 long q2 = 1;
197
198 int n = 0;
199 boolean stop = false;
200 do {
201 ++n;
202 double r1 = 1.0 / (r0 - a0);
203 long a1 = (long)Math.floor(r1);
204 p2 = (a1 * p1) + p0;
205 q2 = (a1 * q1) + q0;
206 if ((p2 > overflow) || (q2 > overflow)) {
207 throw new FractionConversionException(value, p2, q2);
208 }
209
210 double convergent = (double)p2 / (double)q2;
211 if (n < maxIterations && Math.abs(convergent - value) > epsilon && q2 < maxDenominator) {
212 p0 = p1;
213 p1 = p2;
214 q0 = q1;
215 q1 = q2;
216 a0 = a1;
217 r0 = r1;
218 } else {
219 stop = true;
220 }
221 } while (!stop);
222
223 if (n >= maxIterations) {
224 throw new FractionConversionException(value, maxIterations);
225 }
226
227 if (q2 < maxDenominator) {
228 this.numerator = (int) p2;
229 this.denominator = (int) q2;
230 } else {
231 this.numerator = (int) p1;
232 this.denominator = (int) q1;
233 }
234
235 }
236
237
238
239
240
241
242 public Fraction(int num) {
243 this(num, 1);
244 }
245
246
247
248
249
250
251
252
253 public Fraction(int num, int den) {
254 if (den == 0) {
255 throw MathRuntimeException.createArithmeticException("zero denominator in fraction {0}/{1}",
256 num, den);
257 }
258 if (den < 0) {
259 if (num == Integer.MIN_VALUE || den == Integer.MIN_VALUE) {
260 throw MathRuntimeException.createArithmeticException("overflow in fraction {0}/{1}, cannot negate",
261 num, den);
262 }
263 num = -num;
264 den = -den;
265 }
266
267 final int d = MathUtils.gcd(num, den);
268 if (d > 1) {
269 num /= d;
270 den /= d;
271 }
272
273
274 if (den < 0) {
275 num = -num;
276 den = -den;
277 }
278 this.numerator = num;
279 this.denominator = den;
280 }
281
282
283
284
285
286 public Fraction abs() {
287 Fraction ret;
288 if (numerator >= 0) {
289 ret = this;
290 } else {
291 ret = negate();
292 }
293 return ret;
294 }
295
296
297
298
299
300
301
302 public int compareTo(Fraction object) {
303 long nOd = ((long) numerator) * object.denominator;
304 long dOn = ((long) denominator) * object.numerator;
305 return (nOd < dOn) ? -1 : ((nOd > dOn) ? +1 : 0);
306 }
307
308
309
310
311
312
313 @Override
314 public double doubleValue() {
315 return (double)numerator / (double)denominator;
316 }
317
318
319
320
321
322
323
324
325
326
327 @Override
328 public boolean equals(Object other) {
329 boolean ret;
330
331 if (this == other) {
332 ret = true;
333 } else if (other == null) {
334 ret = false;
335 } else {
336 try {
337
338
339 Fraction rhs = (Fraction)other;
340 ret = (numerator == rhs.numerator) &&
341 (denominator == rhs.denominator);
342 } catch (ClassCastException ex) {
343
344 ret = false;
345 }
346 }
347
348 return ret;
349 }
350
351
352
353
354
355
356 @Override
357 public float floatValue() {
358 return (float)doubleValue();
359 }
360
361
362
363
364
365 public int getDenominator() {
366 return denominator;
367 }
368
369
370
371
372
373 public int getNumerator() {
374 return numerator;
375 }
376
377
378
379
380
381 @Override
382 public int hashCode() {
383 return 37 * (37 * 17 + getNumerator()) + getDenominator();
384 }
385
386
387
388
389
390
391 @Override
392 public int intValue() {
393 return (int)doubleValue();
394 }
395
396
397
398
399
400
401 @Override
402 public long longValue() {
403 return (long)doubleValue();
404 }
405
406
407
408
409
410 public Fraction negate() {
411 if (numerator==Integer.MIN_VALUE) {
412 throw MathRuntimeException.createArithmeticException("overflow in fraction {0}/{1}, cannot negate",
413 numerator, denominator);
414 }
415 return new Fraction(-numerator, denominator);
416 }
417
418
419
420
421
422 public Fraction reciprocal() {
423 return new Fraction(denominator, numerator);
424 }
425
426
427
428
429
430
431
432
433
434
435
436 public Fraction add(Fraction fraction) {
437 return addSub(fraction, true
438 }
439
440
441
442
443
444
445 public Fraction add(final int i) {
446 return new Fraction(numerator + i * denominator, denominator);
447 }
448
449
450
451
452
453
454
455
456
457
458
459 public Fraction subtract(Fraction fraction) {
460 return addSub(fraction, false
461 }
462
463
464
465
466
467
468 public Fraction subtract(final int i) {
469 return new Fraction(numerator - i * denominator, denominator);
470 }
471
472
473
474
475
476
477
478
479
480
481
482 private Fraction addSub(Fraction fraction, boolean isAdd) {
483 if (fraction == null) {
484 throw MathRuntimeException.createIllegalArgumentException("null fraction");
485 }
486
487 if (numerator == 0) {
488 return isAdd ? fraction : fraction.negate();
489 }
490 if (fraction.numerator == 0) {
491 return this;
492 }
493
494
495 int d1 = MathUtils.gcd(denominator, fraction.denominator);
496 if (d1==1) {
497
498 int uvp = MathUtils.mulAndCheck(numerator, fraction.denominator);
499 int upv = MathUtils.mulAndCheck(fraction.numerator, denominator);
500 return new Fraction
501 (isAdd ? MathUtils.addAndCheck(uvp, upv) :
502 MathUtils.subAndCheck(uvp, upv),
503 MathUtils.mulAndCheck(denominator, fraction.denominator));
504 }
505
506
507
508 BigInteger uvp = BigInteger.valueOf(numerator)
509 .multiply(BigInteger.valueOf(fraction.denominator/d1));
510 BigInteger upv = BigInteger.valueOf(fraction.numerator)
511 .multiply(BigInteger.valueOf(denominator/d1));
512 BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
513
514
515 int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
516 int d2 = (tmodd1==0)?d1:MathUtils.gcd(tmodd1, d1);
517
518
519 BigInteger w = t.divide(BigInteger.valueOf(d2));
520 if (w.bitLength() > 31) {
521 throw MathRuntimeException.createArithmeticException("overflow, numerator too large after multiply: {0}",
522 w);
523 }
524 return new Fraction (w.intValue(),
525 MathUtils.mulAndCheck(denominator/d1,
526 fraction.denominator/d2));
527 }
528
529
530
531
532
533
534
535
536
537
538
539 public Fraction multiply(Fraction fraction) {
540 if (fraction == null) {
541 throw MathRuntimeException.createIllegalArgumentException("null fraction");
542 }
543 if (numerator == 0 || fraction.numerator == 0) {
544 return ZERO;
545 }
546
547
548 int d1 = MathUtils.gcd(numerator, fraction.denominator);
549 int d2 = MathUtils.gcd(fraction.numerator, denominator);
550 return getReducedFraction
551 (MathUtils.mulAndCheck(numerator/d1, fraction.numerator/d2),
552 MathUtils.mulAndCheck(denominator/d2, fraction.denominator/d1));
553 }
554
555
556
557
558
559
560 public Fraction multiply(final int i) {
561 return new Fraction(numerator * i, denominator);
562 }
563
564
565
566
567
568
569
570
571
572
573
574 public Fraction divide(Fraction fraction) {
575 if (fraction == null) {
576 throw MathRuntimeException.createIllegalArgumentException("null fraction");
577 }
578 if (fraction.numerator == 0) {
579 throw MathRuntimeException.createArithmeticException(
580 "the fraction to divide by must not be zero: {0}/{1}",
581 fraction.numerator, fraction.denominator);
582 }
583 return multiply(fraction.reciprocal());
584 }
585
586
587
588
589
590
591 public Fraction divide(final int i) {
592 return new Fraction(numerator, denominator * i);
593 }
594
595
596
597
598
599
600
601
602
603
604
605
606 public static Fraction getReducedFraction(int numerator, int denominator) {
607 if (denominator == 0) {
608 throw MathRuntimeException.createArithmeticException(
609 "zero denominator in fraction {0}/{1}",
610 numerator, denominator);
611 }
612 if (numerator==0) {
613 return ZERO;
614 }
615
616 if (denominator==Integer.MIN_VALUE && (numerator&1)==0) {
617 numerator/=2; denominator/=2;
618 }
619 if (denominator < 0) {
620 if (numerator==Integer.MIN_VALUE ||
621 denominator==Integer.MIN_VALUE) {
622 throw MathRuntimeException.createArithmeticException(
623 "overflow in fraction {0}/{1}, cannot negate",
624 numerator, denominator);
625 }
626 numerator = -numerator;
627 denominator = -denominator;
628 }
629
630 int gcd = MathUtils.gcd(numerator, denominator);
631 numerator /= gcd;
632 denominator /= gcd;
633 return new Fraction(numerator, denominator);
634 }
635
636
637
638
639
640
641
642
643
644
645 @Override
646 public String toString() {
647 String str = null;
648 if (denominator == 1) {
649 str = Integer.toString(numerator);
650 } else if (numerator == 0) {
651 str = "0";
652 } else {
653 str = numerator + " / " + denominator;
654 }
655 return str;
656 }
657
658
659 public FractionField getField() {
660 return FractionField.getInstance();
661 }
662
663 }