(index<- ) ./libnum/rational.rs
git branch: * master 5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
modified: Fri Apr 25 22:40:04 2014
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! Rational numbers
12
13 use Integer;
14
15 use std::cmp;
16 use std::fmt;
17 use std::from_str::FromStr;
18 use std::num::{Zero, One, ToStrRadix, FromStrRadix};
19 use bigint::{BigInt, BigUint, Sign, Plus, Minus};
20
21 /// Represents the ratio between 2 numbers.
22 #[deriving(Clone)]
23 #[allow(missing_doc)]
24 pub struct Ratio<T> {
25 numer: T,
26 denom: T
27 }
28
29 /// Alias for a `Ratio` of machine-sized integers.
30 pub type Rational = Ratio<int>;
31 pub type Rational32 = Ratio<i32>;
32 pub type Rational64 = Ratio<i64>;
33
34 /// Alias for arbitrary precision rationals.
35 pub type BigRational = Ratio<BigInt>;
36
37 impl<T: Clone + Integer + Ord>
38 Ratio<T> {
39 /// Create a ratio representing the integer `t`.
40 #[inline]
41 pub fn from_integer(t: T) -> Ratio<T> {
42 Ratio::new_raw(t, One::one())
43 }
44
45 /// Create a ratio without checking for `denom == 0` or reducing.
46 #[inline]
47 pub fn new_raw(numer: T, denom: T) -> Ratio<T> {
48 Ratio { numer: numer, denom: denom }
49 }
50
51 /// Create a new Ratio. Fails if `denom == 0`.
52 #[inline]
53 pub fn new(numer: T, denom: T) -> Ratio<T> {
54 if denom == Zero::zero() {
55 fail!("denominator == 0");
56 }
57 let mut ret = Ratio::new_raw(numer, denom);
58 ret.reduce();
59 ret
60 }
61
62 /// Convert to an integer.
63 #[inline]
64 pub fn to_integer(&self) -> T {
65 self.trunc().numer
66 }
67
68 /// Gets an immutable reference to the numerator.
69 #[inline]
70 pub fn numer<'a>(&'a self) -> &'a T {
71 &self.numer
72 }
73
74 /// Gets an immutable reference to the denominator.
75 #[inline]
76 pub fn denom<'a>(&'a self) -> &'a T {
77 &self.denom
78 }
79
80 /// Return true if the rational number is an integer (denominator is 1).
81 #[inline]
82 pub fn is_integer(&self) -> bool {
83 self.denom == One::one()
84 }
85
86 /// Put self into lowest terms, with denom > 0.
87 fn reduce(&mut self) {
88 let g : T = self.numer.gcd(&self.denom);
89
90 // FIXME(#5992): assignment operator overloads
91 // self.numer /= g;
92 self.numer = self.numer / g;
93 // FIXME(#5992): assignment operator overloads
94 // self.denom /= g;
95 self.denom = self.denom / g;
96
97 // keep denom positive!
98 if self.denom < Zero::zero() {
99 self.numer = -self.numer;
100 self.denom = -self.denom;
101 }
102 }
103
104 /// Return a `reduce`d copy of self.
105 pub fn reduced(&self) -> Ratio<T> {
106 let mut ret = self.clone();
107 ret.reduce();
108 ret
109 }
110
111 /// Return the reciprocal
112 #[inline]
113 pub fn recip(&self) -> Ratio<T> {
114 Ratio::new_raw(self.denom.clone(), self.numer.clone())
115 }
116
117 pub fn floor(&self) -> Ratio<T> {
118 if *self < Zero::zero() {
119 Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
120 } else {
121 Ratio::from_integer(self.numer / self.denom)
122 }
123 }
124
125 pub fn ceil(&self) -> Ratio<T> {
126 if *self < Zero::zero() {
127 Ratio::from_integer(self.numer / self.denom)
128 } else {
129 Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
130 }
131 }
132
133 #[inline]
134 pub fn round(&self) -> Ratio<T> {
135 if *self < Zero::zero() {
136 Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
137 } else {
138 Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
139 }
140 }
141
142 #[inline]
143 pub fn trunc(&self) -> Ratio<T> {
144 Ratio::from_integer(self.numer / self.denom)
145 }
146
147 pub fn fract(&self) -> Ratio<T> {
148 Ratio::new_raw(self.numer % self.denom, self.denom.clone())
149 }
150 }
151
152 impl Ratio<BigInt> {
153 /// Converts a float into a rational number
154 pub fn from_float<T: Float>(f: T) -> Option<BigRational> {
155 if !f.is_finite() {
156 return None;
157 }
158 let (mantissa, exponent, sign) = f.integer_decode();
159 let bigint_sign: Sign = if sign == 1 { Plus } else { Minus };
160 if exponent < 0 {
161 let one: BigInt = One::one();
162 let denom: BigInt = one << ((-exponent) as uint);
163 let numer: BigUint = FromPrimitive::from_u64(mantissa).unwrap();
164 Some(Ratio::new(BigInt::from_biguint(bigint_sign, numer), denom))
165 } else {
166 let mut numer: BigUint = FromPrimitive::from_u64(mantissa).unwrap();
167 numer = numer << (exponent as uint);
168 Some(Ratio::from_integer(BigInt::from_biguint(bigint_sign, numer)))
169 }
170 }
171 }
172
173 /* Comparisons */
174
175 // comparing a/b and c/d is the same as comparing a*d and b*c, so we
176 // abstract that pattern. The following macro takes a trait and either
177 // a comma-separated list of "method name -> return value" or just
178 // "method name" (return value is bool in that case)
179 macro_rules! cmp_impl {
180 (impl $imp:ident, $($method:ident),+) => {
181 cmp_impl!(impl $imp, $($method -> bool),+)
182 };
183 // return something other than a Ratio<T>
184 (impl $imp:ident, $($method:ident -> $res:ty),*) => {
185 impl<T: Mul<T,T> + $imp> $imp for Ratio<T> {
186 $(
187 #[inline]
188 fn $method(&self, other: &Ratio<T>) -> $res {
189 (self.numer * other.denom). $method (&(self.denom*other.numer))
190 }
191 )*
192 }
193 };
194 }
195 cmp_impl!(impl Eq, eq, ne)
196 cmp_impl!(impl Ord, lt, gt, le, ge)
197 cmp_impl!(impl TotalEq, )
198 cmp_impl!(impl TotalOrd, cmp -> cmp::Ordering)
199
200 /* Arithmetic */
201 // a/b * c/d = (a*c)/(b*d)
202 impl<T: Clone + Integer + Ord>
203 Mul<Ratio<T>,Ratio<T>> for Ratio<T> {
204 #[inline]
205 fn mul(&self, rhs: &Ratio<T>) -> Ratio<T> {
206 Ratio::new(self.numer * rhs.numer, self.denom * rhs.denom)
207 }
208 }
209
210 // (a/b) / (c/d) = (a*d)/(b*c)
211 impl<T: Clone + Integer + Ord>
212 Div<Ratio<T>,Ratio<T>> for Ratio<T> {
213 #[inline]
214 fn div(&self, rhs: &Ratio<T>) -> Ratio<T> {
215 Ratio::new(self.numer * rhs.denom, self.denom * rhs.numer)
216 }
217 }
218
219 // Abstracts the a/b `op` c/d = (a*d `op` b*d) / (b*d) pattern
220 macro_rules! arith_impl {
221 (impl $imp:ident, $method:ident) => {
222 impl<T: Clone + Integer + Ord>
223 $imp<Ratio<T>,Ratio<T>> for Ratio<T> {
224 #[inline]
225 fn $method(&self, rhs: &Ratio<T>) -> Ratio<T> {
226 Ratio::new((self.numer * rhs.denom).$method(&(self.denom * rhs.numer)),
227 self.denom * rhs.denom)
228 }
229 }
230 }
231 }
232
233 // a/b + c/d = (a*d + b*c)/(b*d
234 arith_impl!(impl Add, add)
235
236 // a/b - c/d = (a*d - b*c)/(b*d)
237 arith_impl!(impl Sub, sub)
238
239 // a/b % c/d = (a*d % b*c)/(b*d)
240 arith_impl!(impl Rem, rem)
241
242 impl<T: Clone + Integer + Ord>
243 Neg<Ratio<T>> for Ratio<T> {
244 #[inline]
245 fn neg(&self) -> Ratio<T> {
246 Ratio::new_raw(-self.numer, self.denom.clone())
247 }
248 }
249
250 /* Constants */
251 impl<T: Clone + Integer + Ord>
252 Zero for Ratio<T> {
253 #[inline]
254 fn zero() -> Ratio<T> {
255 Ratio::new_raw(Zero::zero(), One::one())
256 }
257
258 #[inline]
259 fn is_zero(&self) -> bool {
260 *self == Zero::zero()
261 }
262 }
263
264 impl<T: Clone + Integer + Ord>
265 One for Ratio<T> {
266 #[inline]
267 fn one() -> Ratio<T> {
268 Ratio::new_raw(One::one(), One::one())
269 }
270 }
271
272 impl<T: Clone + Integer + Ord>
273 Num for Ratio<T> {}
274
275 /* String conversions */
276 impl<T: fmt::Show> fmt::Show for Ratio<T> {
277 /// Renders as `numer/denom`.
278 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
279 write!(f.buf, "{}/{}", self.numer, self.denom)
280 }
281 }
282 impl<T: ToStrRadix> ToStrRadix for Ratio<T> {
283 /// Renders as `numer/denom` where the numbers are in base `radix`.
284 fn to_str_radix(&self, radix: uint) -> ~str {
285 format!("{}/{}", self.numer.to_str_radix(radix), self.denom.to_str_radix(radix))
286 }
287 }
288
289 impl<T: FromStr + Clone + Integer + Ord>
290 FromStr for Ratio<T> {
291 /// Parses `numer/denom`.
292 fn from_str(s: &str) -> Option<Ratio<T>> {
293 let split: Vec<&str> = s.splitn('/', 1).collect();
294 if split.len() < 2 {
295 return None
296 }
297 let a_option: Option<T> = FromStr::from_str(*split.get(0));
298 a_option.and_then(|a| {
299 let b_option: Option<T> = FromStr::from_str(*split.get(1));
300 b_option.and_then(|b| {
301 Some(Ratio::new(a.clone(), b.clone()))
302 })
303 })
304 }
305 }
306 impl<T: FromStrRadix + Clone + Integer + Ord>
307 FromStrRadix for Ratio<T> {
308 /// Parses `numer/denom` where the numbers are in base `radix`.
309 fn from_str_radix(s: &str, radix: uint) -> Option<Ratio<T>> {
310 let split: Vec<&str> = s.splitn('/', 1).collect();
311 if split.len() < 2 {
312 None
313 } else {
314 let a_option: Option<T> = FromStrRadix::from_str_radix(
315 *split.get(0),
316 radix);
317 a_option.and_then(|a| {
318 let b_option: Option<T> =
319 FromStrRadix::from_str_radix(*split.get(1), radix);
320 b_option.and_then(|b| {
321 Some(Ratio::new(a.clone(), b.clone()))
322 })
323 })
324 }
325 }
326 }
327
328 #[cfg(test)]
329 mod test {
330
331 use super::{Ratio, Rational, BigRational};
332 use std::num::{Zero, One, FromStrRadix, FromPrimitive, ToStrRadix};
333 use std::from_str::FromStr;
334
335 pub static _0 : Rational = Ratio { numer: 0, denom: 1};
336 pub static _1 : Rational = Ratio { numer: 1, denom: 1};
337 pub static _2: Rational = Ratio { numer: 2, denom: 1};
338 pub static _1_2: Rational = Ratio { numer: 1, denom: 2};
339 pub static _3_2: Rational = Ratio { numer: 3, denom: 2};
340 pub static _neg1_2: Rational = Ratio { numer: -1, denom: 2};
341
342 pub fn to_big(n: Rational) -> BigRational {
343 Ratio::new(
344 FromPrimitive::from_int(n.numer).unwrap(),
345 FromPrimitive::from_int(n.denom).unwrap()
346 )
347 }
348
349 #[test]
350 fn test_test_constants() {
351 // check our constants are what Ratio::new etc. would make.
352 assert_eq!(_0, Zero::zero());
353 assert_eq!(_1, One::one());
354 assert_eq!(_2, Ratio::from_integer(2));
355 assert_eq!(_1_2, Ratio::new(1,2));
356 assert_eq!(_3_2, Ratio::new(3,2));
357 assert_eq!(_neg1_2, Ratio::new(-1,2));
358 }
359
360 #[test]
361 fn test_new_reduce() {
362 let one22 = Ratio::new(2i,2);
363
364 assert_eq!(one22, One::one());
365 }
366 #[test]
367 #[should_fail]
368 fn test_new_zero() {
369 let _a = Ratio::new(1,0);
370 }
371
372
373 #[test]
374 fn test_cmp() {
375 assert!(_0 == _0 && _1 == _1);
376 assert!(_0 != _1 && _1 != _0);
377 assert!(_0 < _1 && !(_1 < _0));
378 assert!(_1 > _0 && !(_0 > _1));
379
380 assert!(_0 <= _0 && _1 <= _1);
381 assert!(_0 <= _1 && !(_1 <= _0));
382
383 assert!(_0 >= _0 && _1 >= _1);
384 assert!(_1 >= _0 && !(_0 >= _1));
385 }
386
387
388 #[test]
389 fn test_to_integer() {
390 assert_eq!(_0.to_integer(), 0);
391 assert_eq!(_1.to_integer(), 1);
392 assert_eq!(_2.to_integer(), 2);
393 assert_eq!(_1_2.to_integer(), 0);
394 assert_eq!(_3_2.to_integer(), 1);
395 assert_eq!(_neg1_2.to_integer(), 0);
396 }
397
398
399 #[test]
400 fn test_numer() {
401 assert_eq!(_0.numer(), &0);
402 assert_eq!(_1.numer(), &1);
403 assert_eq!(_2.numer(), &2);
404 assert_eq!(_1_2.numer(), &1);
405 assert_eq!(_3_2.numer(), &3);
406 assert_eq!(_neg1_2.numer(), &(-1));
407 }
408 #[test]
409 fn test_denom() {
410 assert_eq!(_0.denom(), &1);
411 assert_eq!(_1.denom(), &1);
412 assert_eq!(_2.denom(), &1);
413 assert_eq!(_1_2.denom(), &2);
414 assert_eq!(_3_2.denom(), &2);
415 assert_eq!(_neg1_2.denom(), &2);
416 }
417
418
419 #[test]
420 fn test_is_integer() {
421 assert!(_0.is_integer());
422 assert!(_1.is_integer());
423 assert!(_2.is_integer());
424 assert!(!_1_2.is_integer());
425 assert!(!_3_2.is_integer());
426 assert!(!_neg1_2.is_integer());
427 }
428
429
430 mod arith {
431 use super::{_0, _1, _2, _1_2, _3_2, _neg1_2, to_big};
432 use super::super::{Ratio, Rational};
433
434 #[test]
435 fn test_add() {
436 fn test(a: Rational, b: Rational, c: Rational) {
437 assert_eq!(a + b, c);
438 assert_eq!(to_big(a) + to_big(b), to_big(c));
439 }
440
441 test(_1, _1_2, _3_2);
442 test(_1, _1, _2);
443 test(_1_2, _3_2, _2);
444 test(_1_2, _neg1_2, _0);
445 }
446
447 #[test]
448 fn test_sub() {
449 fn test(a: Rational, b: Rational, c: Rational) {
450 assert_eq!(a - b, c);
451 assert_eq!(to_big(a) - to_big(b), to_big(c))
452 }
453
454 test(_1, _1_2, _1_2);
455 test(_3_2, _1_2, _1);
456 test(_1, _neg1_2, _3_2);
457 }
458
459 #[test]
460 fn test_mul() {
461 fn test(a: Rational, b: Rational, c: Rational) {
462 assert_eq!(a * b, c);
463 assert_eq!(to_big(a) * to_big(b), to_big(c))
464 }
465
466 test(_1, _1_2, _1_2);
467 test(_1_2, _3_2, Ratio::new(3,4));
468 test(_1_2, _neg1_2, Ratio::new(-1, 4));
469 }
470
471 #[test]
472 fn test_div() {
473 fn test(a: Rational, b: Rational, c: Rational) {
474 assert_eq!(a / b, c);
475 assert_eq!(to_big(a) / to_big(b), to_big(c))
476 }
477
478 test(_1, _1_2, _2);
479 test(_3_2, _1_2, _1 + _2);
480 test(_1, _neg1_2, _neg1_2 + _neg1_2 + _neg1_2 + _neg1_2);
481 }
482
483 #[test]
484 fn test_rem() {
485 fn test(a: Rational, b: Rational, c: Rational) {
486 assert_eq!(a % b, c);
487 assert_eq!(to_big(a) % to_big(b), to_big(c))
488 }
489
490 test(_3_2, _1, _1_2);
491 test(_2, _neg1_2, _0);
492 test(_1_2, _2, _1_2);
493 }
494
495 #[test]
496 fn test_neg() {
497 fn test(a: Rational, b: Rational) {
498 assert_eq!(-a, b);
499 assert_eq!(-to_big(a), to_big(b))
500 }
501
502 test(_0, _0);
503 test(_1_2, _neg1_2);
504 test(-_1, _1);
505 }
506 #[test]
507 fn test_zero() {
508 assert_eq!(_0 + _0, _0);
509 assert_eq!(_0 * _0, _0);
510 assert_eq!(_0 * _1, _0);
511 assert_eq!(_0 / _neg1_2, _0);
512 assert_eq!(_0 - _0, _0);
513 }
514 #[test]
515 #[should_fail]
516 fn test_div_0() {
517 let _a = _1 / _0;
518 }
519 }
520
521 #[test]
522 fn test_round() {
523 assert_eq!(_1_2.ceil(), _1);
524 assert_eq!(_1_2.floor(), _0);
525 assert_eq!(_1_2.round(), _1);
526 assert_eq!(_1_2.trunc(), _0);
527
528 assert_eq!(_neg1_2.ceil(), _0);
529 assert_eq!(_neg1_2.floor(), -_1);
530 assert_eq!(_neg1_2.round(), -_1);
531 assert_eq!(_neg1_2.trunc(), _0);
532
533 assert_eq!(_1.ceil(), _1);
534 assert_eq!(_1.floor(), _1);
535 assert_eq!(_1.round(), _1);
536 assert_eq!(_1.trunc(), _1);
537 }
538
539 #[test]
540 fn test_fract() {
541 assert_eq!(_1.fract(), _0);
542 assert_eq!(_neg1_2.fract(), _neg1_2);
543 assert_eq!(_1_2.fract(), _1_2);
544 assert_eq!(_3_2.fract(), _1_2);
545 }
546
547 #[test]
548 fn test_recip() {
549 assert_eq!(_1 * _1.recip(), _1);
550 assert_eq!(_2 * _2.recip(), _1);
551 assert_eq!(_1_2 * _1_2.recip(), _1);
552 assert_eq!(_3_2 * _3_2.recip(), _1);
553 assert_eq!(_neg1_2 * _neg1_2.recip(), _1);
554 }
555
556 #[test]
557 fn test_to_from_str() {
558 fn test(r: Rational, s: ~str) {
559 assert_eq!(FromStr::from_str(s), Some(r));
560 assert_eq!(r.to_str(), s);
561 }
562 test(_1, "1/1".to_owned());
563 test(_0, "0/1".to_owned());
564 test(_1_2, "1/2".to_owned());
565 test(_3_2, "3/2".to_owned());
566 test(_2, "2/1".to_owned());
567 test(_neg1_2, "-1/2".to_owned());
568 }
569 #[test]
570 fn test_from_str_fail() {
571 fn test(s: &str) {
572 let rational: Option<Rational> = FromStr::from_str(s);
573 assert_eq!(rational, None);
574 }
575
576 let xs = ["0 /1", "abc", "", "1/", "--1/2","3/2/1"];
577 for &s in xs.iter() {
578 test(s);
579 }
580 }
581
582 #[test]
583 fn test_to_from_str_radix() {
584 fn test(r: Rational, s: ~str, n: uint) {
585 assert_eq!(FromStrRadix::from_str_radix(s, n), Some(r));
586 assert_eq!(r.to_str_radix(n), s);
587 }
588 fn test3(r: Rational, s: ~str) { test(r, s, 3) }
589 fn test16(r: Rational, s: ~str) { test(r, s, 16) }
590
591 test3(_1, "1/1".to_owned());
592 test3(_0, "0/1".to_owned());
593 test3(_1_2, "1/2".to_owned());
594 test3(_3_2, "10/2".to_owned());
595 test3(_2, "2/1".to_owned());
596 test3(_neg1_2, "-1/2".to_owned());
597 test3(_neg1_2 / _2, "-1/11".to_owned());
598
599 test16(_1, "1/1".to_owned());
600 test16(_0, "0/1".to_owned());
601 test16(_1_2, "1/2".to_owned());
602 test16(_3_2, "3/2".to_owned());
603 test16(_2, "2/1".to_owned());
604 test16(_neg1_2, "-1/2".to_owned());
605 test16(_neg1_2 / _2, "-1/4".to_owned());
606 test16(Ratio::new(13,15), "d/f".to_owned());
607 test16(_1_2*_1_2*_1_2*_1_2, "1/10".to_owned());
608 }
609
610 #[test]
611 fn test_from_str_radix_fail() {
612 fn test(s: &str) {
613 let radix: Option<Rational> = FromStrRadix::from_str_radix(s, 3);
614 assert_eq!(radix, None);
615 }
616
617 let xs = ["0 /1", "abc", "", "1/", "--1/2","3/2/1", "3/2"];
618 for &s in xs.iter() {
619 test(s);
620 }
621 }
622
623 #[test]
624 fn test_from_float() {
625 fn test<T: Float>(given: T, (numer, denom): (&str, &str)) {
626 let ratio: BigRational = Ratio::from_float(given).unwrap();
627 assert_eq!(ratio, Ratio::new(
628 FromStr::from_str(numer).unwrap(),
629 FromStr::from_str(denom).unwrap()));
630 }
631
632 // f32
633 test(3.14159265359f32, ("13176795", "4194304"));
634 test(2f32.powf(100.), ("1267650600228229401496703205376", "1"));
635 test(-2f32.powf(100.), ("-1267650600228229401496703205376", "1"));
636 test(1.0 / 2f32.powf(100.), ("1", "1267650600228229401496703205376"));
637 test(684729.48391f32, ("1369459", "2"));
638 test(-8573.5918555f32, ("-4389679", "512"));
639
640 // f64
641 test(3.14159265359f64, ("3537118876014453", "1125899906842624"));
642 test(2f64.powf(100.), ("1267650600228229401496703205376", "1"));
643 test(-2f64.powf(100.), ("-1267650600228229401496703205376", "1"));
644 test(684729.48391f64, ("367611342500051", "536870912"));
645 test(-8573.5918555, ("-4713381968463931", "549755813888"));
646 test(1.0 / 2f64.powf(100.), ("1", "1267650600228229401496703205376"));
647 }
648
649 #[test]
650 fn test_from_float_fail() {
651 use std::{f32, f64};
652
653 assert_eq!(Ratio::from_float(f32::NAN), None);
654 assert_eq!(Ratio::from_float(f32::INFINITY), None);
655 assert_eq!(Ratio::from_float(f32::NEG_INFINITY), None);
656 assert_eq!(Ratio::from_float(f64::NAN), None);
657 assert_eq!(Ratio::from_float(f64::INFINITY), None);
658 assert_eq!(Ratio::from_float(f64::NEG_INFINITY), None);
659 }
660 }