1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.lang3.math;
18
19 import java.math.BigInteger;
20 import java.util.Objects;
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 public final class Fraction extends Number implements Comparable<Fraction> {
36
37
38
39
40
41
42 private static final long serialVersionUID = 65382027393090L;
43
44
45
46
47 public static final Fraction ZERO = new Fraction(0, 1);
48
49
50
51 public static final Fraction ONE = new Fraction(1, 1);
52
53
54
55 public static final Fraction ONE_HALF = new Fraction(1, 2);
56
57
58
59 public static final Fraction ONE_THIRD = new Fraction(1, 3);
60
61
62
63 public static final Fraction TWO_THIRDS = new Fraction(2, 3);
64
65
66
67 public static final Fraction ONE_QUARTER = new Fraction(1, 4);
68
69
70
71 public static final Fraction TWO_QUARTERS = new Fraction(2, 4);
72
73
74
75 public static final Fraction THREE_QUARTERS = new Fraction(3, 4);
76
77
78
79 public static final Fraction ONE_FIFTH = new Fraction(1, 5);
80
81
82
83 public static final Fraction TWO_FIFTHS = new Fraction(2, 5);
84
85
86
87 public static final Fraction THREE_FIFTHS = new Fraction(3, 5);
88
89
90
91 public static final Fraction FOUR_FIFTHS = new Fraction(4, 5);
92
93
94
95
96
97
98
99
100
101
102
103 private static int addAndCheck(final int x, final int y) {
104 final long s = (long) x + (long) y;
105 if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
106 throw new ArithmeticException("overflow: add");
107 }
108 return (int) s;
109 }
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124 public static Fraction getFraction(double value) {
125 final int sign = value < 0 ? -1 : 1;
126 value = Math.abs(value);
127 if (value > Integer.MAX_VALUE || Double.isNaN(value)) {
128 throw new ArithmeticException("The value must not be greater than Integer.MAX_VALUE or NaN");
129 }
130 final int wholeNumber = (int) value;
131 value -= wholeNumber;
132
133 int numer0 = 0;
134 int denom0 = 1;
135 int numer1 = 1;
136 int denom1 = 0;
137 int numer2;
138 int denom2;
139 int a1 = (int) value;
140 int a2;
141 double x1 = 1;
142 double x2;
143 double y1 = value - a1;
144 double y2;
145 double delta1, delta2 = Double.MAX_VALUE;
146 double fraction;
147 int i = 1;
148 do {
149 delta1 = delta2;
150 a2 = (int) (x1 / y1);
151 x2 = y1;
152 y2 = x1 - a2 * y1;
153 numer2 = a1 * numer1 + numer0;
154 denom2 = a1 * denom1 + denom0;
155 fraction = (double) numer2 / (double) denom2;
156 delta2 = Math.abs(value - fraction);
157 a1 = a2;
158 x1 = x2;
159 y1 = y2;
160 numer0 = numer1;
161 denom0 = denom1;
162 numer1 = numer2;
163 denom1 = denom2;
164 i++;
165 } while (delta1 > delta2 && denom2 <= 10000 && denom2 > 0 && i < 25);
166 if (i == 25) {
167 throw new ArithmeticException("Unable to convert double to fraction");
168 }
169 return getReducedFraction((numer0 + wholeNumber * denom0) * sign, denom0);
170 }
171
172
173
174
175
176
177
178
179
180
181
182
183
184 public static Fraction getFraction(int numerator, int denominator) {
185 if (denominator == 0) {
186 throw new ArithmeticException("The denominator must not be zero");
187 }
188 if (denominator < 0) {
189 if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) {
190 throw new ArithmeticException("overflow: can't negate");
191 }
192 numerator = -numerator;
193 denominator = -denominator;
194 }
195 return new Fraction(numerator, denominator);
196 }
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213 public static Fraction getFraction(final int whole, final int numerator, final int denominator) {
214 if (denominator == 0) {
215 throw new ArithmeticException("The denominator must not be zero");
216 }
217 if (denominator < 0) {
218 throw new ArithmeticException("The denominator must not be negative");
219 }
220 if (numerator < 0) {
221 throw new ArithmeticException("The numerator must not be negative");
222 }
223 final long numeratorValue;
224 if (whole < 0) {
225 numeratorValue = whole * (long) denominator - numerator;
226 } else {
227 numeratorValue = whole * (long) denominator + numerator;
228 }
229 if (numeratorValue < Integer.MIN_VALUE || numeratorValue > Integer.MAX_VALUE) {
230 throw new ArithmeticException("Numerator too large to represent as an Integer.");
231 }
232 return new Fraction((int) numeratorValue, denominator);
233 }
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252 public static Fraction getFraction(String str) {
253 Objects.requireNonNull(str, "str");
254
255 int pos = str.indexOf('.');
256 if (pos >= 0) {
257 return getFraction(Double.parseDouble(str));
258 }
259
260
261 pos = str.indexOf(' ');
262 if (pos > 0) {
263 final int whole = Integer.parseInt(str.substring(0, pos));
264 str = str.substring(pos + 1);
265 pos = str.indexOf('/');
266 if (pos < 0) {
267 throw new NumberFormatException("The fraction could not be parsed as the format X Y/Z");
268 }
269 final int numer = Integer.parseInt(str.substring(0, pos));
270 final int denom = Integer.parseInt(str.substring(pos + 1));
271 return getFraction(whole, numer, denom);
272 }
273
274
275 pos = str.indexOf('/');
276 if (pos < 0) {
277
278 return getFraction(Integer.parseInt(str), 1);
279 }
280 final int numer = Integer.parseInt(str.substring(0, pos));
281 final int denom = Integer.parseInt(str.substring(pos + 1));
282 return getFraction(numer, denom);
283 }
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299 public static Fraction getReducedFraction(int numerator, int denominator) {
300 if (denominator == 0) {
301 throw new ArithmeticException("The denominator must not be zero");
302 }
303 if (numerator == 0) {
304 return ZERO;
305 }
306
307 if (denominator == Integer.MIN_VALUE && (numerator & 1) == 0) {
308 numerator /= 2;
309 denominator /= 2;
310 }
311 if (denominator < 0) {
312 if (numerator == Integer.MIN_VALUE || denominator == Integer.MIN_VALUE) {
313 throw new ArithmeticException("overflow: can't negate");
314 }
315 numerator = -numerator;
316 denominator = -denominator;
317 }
318
319 final int gcd = greatestCommonDivisor(numerator, denominator);
320 numerator /= gcd;
321 denominator /= gcd;
322 return new Fraction(numerator, denominator);
323 }
324
325
326
327
328
329
330
331
332
333
334
335 private static int greatestCommonDivisor(int u, int v) {
336
337 if (u == 0 || v == 0) {
338 if (u == Integer.MIN_VALUE || v == Integer.MIN_VALUE) {
339 throw new ArithmeticException("overflow: gcd is 2^31");
340 }
341 return Math.abs(u) + Math.abs(v);
342 }
343
344 if (Math.abs(u) == 1 || Math.abs(v) == 1) {
345 return 1;
346 }
347
348
349
350
351 if (u > 0) {
352 u = -u;
353 }
354 if (v > 0) {
355 v = -v;
356 }
357
358 int k = 0;
359 while ((u & 1) == 0 && (v & 1) == 0 && k < 31) {
360 u /= 2;
361 v /= 2;
362 k++;
363 }
364 if (k == 31) {
365 throw new ArithmeticException("overflow: gcd is 2^31");
366 }
367
368
369 int t = (u & 1) == 1 ? v : -(u / 2);
370
371
372 do {
373
374
375 while ((t & 1) == 0) {
376 t /= 2;
377 }
378
379 if (t > 0) {
380 u = -t;
381 } else {
382 v = t;
383 }
384
385 t = (v - u) / 2;
386
387
388 } while (t != 0);
389 return -u * (1 << k);
390 }
391
392
393
394
395
396
397
398
399
400
401 private static int mulAndCheck(final int x, final int y) {
402 final long m = (long) x * (long) y;
403 if (m < Integer.MIN_VALUE || m > Integer.MAX_VALUE) {
404 throw new ArithmeticException("overflow: mul");
405 }
406 return (int) m;
407 }
408
409
410
411
412
413
414
415
416
417
418 private static int mulPosAndCheck(final int x, final int y) {
419
420 final long m = (long) x * (long) y;
421 if (m > Integer.MAX_VALUE) {
422 throw new ArithmeticException("overflow: mulPos");
423 }
424 return (int) m;
425 }
426
427
428
429
430
431
432
433
434
435
436 private static int subAndCheck(final int x, final int y) {
437 final long s = (long) x - (long) y;
438 if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
439 throw new ArithmeticException("overflow: add");
440 }
441 return (int) s;
442 }
443
444
445
446
447 private final int numerator;
448
449
450
451
452 private final int denominator;
453
454
455
456
457 private transient int hashCode;
458
459
460
461
462 private transient String toString;
463
464
465
466
467 private transient String toProperString;
468
469
470
471
472
473
474
475
476 private Fraction(final int numerator, final int denominator) {
477 this.numerator = numerator;
478 this.denominator = denominator;
479 }
480
481
482
483
484
485
486
487
488
489
490 public Fraction abs() {
491 if (numerator >= 0) {
492 return this;
493 }
494 return negate();
495 }
496
497
498
499
500
501
502
503
504
505
506
507 public Fraction add(final Fraction fraction) {
508 return addSub(fraction, true );
509 }
510
511
512
513
514
515
516
517
518
519
520
521 private Fraction addSub(final Fraction fraction, final boolean isAdd) {
522 Objects.requireNonNull(fraction, "fraction");
523
524 if (numerator == 0) {
525 return isAdd ? fraction : fraction.negate();
526 }
527 if (fraction.numerator == 0) {
528 return this;
529 }
530
531
532 final int d1 = greatestCommonDivisor(denominator, fraction.denominator);
533 if (d1 == 1) {
534
535 final int uvp = mulAndCheck(numerator, fraction.denominator);
536 final int upv = mulAndCheck(fraction.numerator, denominator);
537 return new Fraction(isAdd ? addAndCheck(uvp, upv) : subAndCheck(uvp, upv), mulPosAndCheck(denominator,
538 fraction.denominator));
539 }
540
541
542
543 final BigInteger uvp = BigInteger.valueOf(numerator).multiply(BigInteger.valueOf(fraction.denominator / d1));
544 final BigInteger upv = BigInteger.valueOf(fraction.numerator).multiply(BigInteger.valueOf(denominator / d1));
545 final BigInteger t = isAdd ? uvp.add(upv) : uvp.subtract(upv);
546
547
548 final int tmodd1 = t.mod(BigInteger.valueOf(d1)).intValue();
549 final int d2 = tmodd1 == 0 ? d1 : greatestCommonDivisor(tmodd1, d1);
550
551
552 final BigInteger w = t.divide(BigInteger.valueOf(d2));
553 if (w.bitLength() > 31) {
554 throw new ArithmeticException("overflow: numerator too large after multiply");
555 }
556 return new Fraction(w.intValue(), mulPosAndCheck(denominator / d1, fraction.denominator / d2));
557 }
558
559
560
561
562
563
564
565
566
567
568
569
570
571 @Override
572 public int compareTo(final Fraction other) {
573 if (this == other) {
574 return 0;
575 }
576 if (numerator == other.numerator && denominator == other.denominator) {
577 return 0;
578 }
579
580
581 final long first = (long) numerator * (long) other.denominator;
582 final long second = (long) other.numerator * (long) denominator;
583 return Long.compare(first, second);
584 }
585
586
587
588
589
590
591
592
593
594
595
596 public Fraction divideBy(final Fraction fraction) {
597 Objects.requireNonNull(fraction, "fraction");
598 if (fraction.numerator == 0) {
599 throw new ArithmeticException("The fraction to divide by must not be zero");
600 }
601 return multiplyBy(fraction.invert());
602 }
603
604
605
606
607
608
609
610 @Override
611 public double doubleValue() {
612 return (double) numerator / (double) denominator;
613 }
614
615
616
617
618
619
620
621
622
623 @Override
624 public boolean equals(final Object obj) {
625 if (obj == this) {
626 return true;
627 }
628 if (!(obj instanceof Fraction)) {
629 return false;
630 }
631 final Fraction other = (Fraction) obj;
632 return getNumerator() == other.getNumerator() && getDenominator() == other.getDenominator();
633 }
634
635
636
637
638
639
640
641 @Override
642 public float floatValue() {
643 return (float) numerator / (float) denominator;
644 }
645
646
647
648
649
650
651 public int getDenominator() {
652 return denominator;
653 }
654
655
656
657
658
659
660
661
662
663 public int getNumerator() {
664 return numerator;
665 }
666
667
668
669
670
671
672
673
674
675
676
677
678 public int getProperNumerator() {
679 return Math.abs(numerator % denominator);
680 }
681
682
683
684
685
686
687
688
689
690
691
692
693 public int getProperWhole() {
694 return numerator / denominator;
695 }
696
697
698
699
700
701
702 @Override
703 public int hashCode() {
704 if (hashCode == 0) {
705
706 hashCode = 37 * (37 * 17 + getNumerator()) + getDenominator();
707 }
708 return hashCode;
709 }
710
711
712
713
714
715
716
717 @Override
718 public int intValue() {
719 return numerator / denominator;
720 }
721
722
723
724
725
726
727
728
729
730
731 public Fraction invert() {
732 if (numerator == 0) {
733 throw new ArithmeticException("Unable to invert zero.");
734 }
735 if (numerator==Integer.MIN_VALUE) {
736 throw new ArithmeticException("overflow: can't negate numerator");
737 }
738 if (numerator<0) {
739 return new Fraction(-denominator, -numerator);
740 }
741 return new Fraction(denominator, numerator);
742 }
743
744
745
746
747
748
749
750 @Override
751 public long longValue() {
752 return (long) numerator / denominator;
753 }
754
755
756
757
758
759
760
761
762
763
764
765 public Fraction multiplyBy(final Fraction fraction) {
766 Objects.requireNonNull(fraction, "fraction");
767 if (numerator == 0 || fraction.numerator == 0) {
768 return ZERO;
769 }
770
771
772 final int d1 = greatestCommonDivisor(numerator, fraction.denominator);
773 final int d2 = greatestCommonDivisor(fraction.numerator, denominator);
774 return getReducedFraction(mulAndCheck(numerator / d1, fraction.numerator / d2),
775 mulPosAndCheck(denominator / d2, fraction.denominator / d1));
776 }
777
778
779
780
781
782
783
784
785 public Fraction negate() {
786
787 if (numerator==Integer.MIN_VALUE) {
788 throw new ArithmeticException("overflow: too large to negate");
789 }
790 return new Fraction(-numerator, denominator);
791 }
792
793
794
795
796
797
798
799
800
801
802
803
804
805 public Fraction pow(final int power) {
806 if (power == 1) {
807 return this;
808 }
809 if (power == 0) {
810 return ONE;
811 }
812 if (power < 0) {
813 if (power == Integer.MIN_VALUE) {
814 return this.invert().pow(2).pow(-(power / 2));
815 }
816 return this.invert().pow(-power);
817 }
818 final Fraction f = this.multiplyBy(this);
819 if (power % 2 == 0) {
820 return f.pow(power / 2);
821 }
822 return f.pow(power / 2).multiplyBy(this);
823 }
824
825
826
827
828
829
830
831
832
833
834 public Fraction reduce() {
835 if (numerator == 0) {
836 return equals(ZERO) ? this : ZERO;
837 }
838 final int gcd = greatestCommonDivisor(Math.abs(numerator), denominator);
839 if (gcd == 1) {
840 return this;
841 }
842 return getFraction(numerator / gcd, denominator / gcd);
843 }
844
845
846
847
848
849
850
851
852
853
854
855 public Fraction subtract(final Fraction fraction) {
856 return addSub(fraction, false );
857 }
858
859
860
861
862
863
864
865
866
867
868 public String toProperString() {
869 if (toProperString == null) {
870 if (numerator == 0) {
871 toProperString = "0";
872 } else if (numerator == denominator) {
873 toProperString = "1";
874 } else if (numerator == -1 * denominator) {
875 toProperString = "-1";
876 } else if ((numerator > 0 ? -numerator : numerator) < -denominator) {
877
878
879
880
881 final int properNumerator = getProperNumerator();
882 if (properNumerator == 0) {
883 toProperString = Integer.toString(getProperWhole());
884 } else {
885 toProperString = getProperWhole() + " " + properNumerator + "/" + getDenominator();
886 }
887 } else {
888 toProperString = getNumerator() + "/" + getDenominator();
889 }
890 }
891 return toProperString;
892 }
893
894
895
896
897
898
899
900
901 @Override
902 public String toString() {
903 if (toString == null) {
904 toString = getNumerator() + "/" + getDenominator();
905 }
906 return toString;
907 }
908 }