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
24
25
26
27
28 public class Fraction extends Number implements Comparable {
29
30
31 public static final Fraction ONE = new Fraction(1, 1);
32
33
34 public static final Fraction ZERO = new Fraction(0, 1);
35
36
37 private static final long serialVersionUID = 65382027393090L;
38
39
40 private int denominator;
41
42
43 private int numerator;
44
45
46
47
48
49
50
51 public Fraction(double value) throws ConvergenceException {
52 this(value, 1.0e-5, 100);
53 }
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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
127
128
129
130
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
152
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
166
167
168
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
190
191
192
193 public double doubleValue() {
194 return (double)numerator / (double)denominator;
195 }
196
197
198
199
200
201
202
203
204
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
231
232
233
234 public float floatValue() {
235 return (float)doubleValue();
236 }
237
238
239
240
241
242 public int getDenominator() {
243 return denominator;
244 }
245
246
247
248
249
250 public int getNumerator() {
251 return numerator;
252 }
253
254
255
256
257
258 public int hashCode() {
259 return 37 * (37 * 17 + getNumerator()) + getDenominator();
260 }
261
262
263
264
265
266
267 public int intValue() {
268 return (int)doubleValue();
269 }
270
271
272
273
274
275
276 public long longValue() {
277 return (long)doubleValue();
278 }
279
280
281
282
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
293
294
295 public Fraction reciprocal() {
296 return new Fraction(denominator, numerator);
297 }
298
299
300
301
302
303
304
305
306
307
308
309 public Fraction add(Fraction fraction) {
310 return addSub(fraction, true
311 }
312
313
314
315
316
317
318
319
320
321
322
323 public Fraction subtract(Fraction fraction) {
324 return addSub(fraction, false
325 }
326
327
328
329
330
331
332
333
334
335
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
386
387
388
389
390
391
392
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
412
413
414
415
416
417
418
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
432
433
434
435
436
437
438
439
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
469
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 }