1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
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 //! ## Compatibility
14 //!
15 //! The `num-rational` crate is tested for rustc 1.15 and greater.
16
17 #![doc(html_root_url = "https://docs.rs/num-rational/0.2")]
18 #![no_std]
19
20 #[cfg(feature = "bigint")]
21 extern crate num_bigint as bigint;
22 #[cfg(feature = "serde")]
23 extern crate serde;
24
25 extern crate num_integer as integer;
26 extern crate num_traits as traits;
27
28 #[cfg(feature = "std")]
29 #[cfg_attr(test, macro_use)]
30 extern crate std;
31
32 use core::cmp;
33 use core::fmt;
34 use core::hash::{Hash, Hasher};
35 use core::ops::{Add, Div, Mul, Neg, Rem, Sub};
36 use core::str::FromStr;
37 #[cfg(feature = "std")]
38 use std::error::Error;
39
40 #[cfg(feature = "bigint")]
41 use bigint::{BigInt, BigUint, Sign};
42
43 use integer::Integer;
44 use traits::float::FloatCore;
45 use traits::{
46 Bounded, CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, FromPrimitive, Inv, Num, NumCast, One,
47 Pow, Signed, Zero,
48 };
49
50 /// Represents the ratio between two numbers.
51 #[derive(Copy, Clone, Debug)]
52 #[allow(missing_docs)]
53 pub struct Ratio<T> {
54 /// Numerator.
55 numer: T,
56 /// Denominator.
57 denom: T,
58 }
59
60 /// Alias for a `Ratio` of machine-sized integers.
61 pub type Rational = Ratio<isize>;
62 /// Alias for a `Ratio` of 32-bit-sized integers.
63 pub type Rational32 = Ratio<i32>;
64 /// Alias for a `Ratio` of 64-bit-sized integers.
65 pub type Rational64 = Ratio<i64>;
66
67 #[cfg(feature = "bigint")]
68 /// Alias for arbitrary precision rationals.
69 pub type BigRational = Ratio<BigInt>;
70
71 macro_rules! maybe_const {
72 ($( $(#[$attr:meta])* pub fn $name:ident $args:tt -> $ret:ty $body:block )*) => {$(
73 #[cfg(has_const_fn)]
74 $(#[$attr])* pub const fn $name $args -> $ret $body
75
76 #[cfg(not(has_const_fn))]
77 $(#[$attr])* pub fn $name $args -> $ret $body
78 )*}
79 }
80
81 /// These method are `const` for Rust 1.31 and later.
82 impl<T> Ratio<T> {
83 maybe_const! {
84 /// Creates a `Ratio` without checking for `denom == 0` or reducing.
85 #[inline]
86 pub fn new_raw(numer: T, denom: T) -> Ratio<T> {
87 Ratio {
88 numer: numer,
89 denom: denom,
90 }
91 }
92
93 /// Gets an immutable reference to the numerator.
94 #[inline]
95 pub fn numer(&self) -> &T {
96 &self.numer
97 }
98
99 /// Gets an immutable reference to the denominator.
100 #[inline]
101 pub fn denom(&self) -> &T {
102 &self.denom
103 }
104 }
105 }
106
107 impl<T: Clone + Integer> Ratio<T> {
108 /// Creates a new `Ratio`. Fails if `denom` is zero.
109 #[inline]
new(numer: T, denom: T) -> Ratio<T>110 pub fn new(numer: T, denom: T) -> Ratio<T> {
111 if denom.is_zero() {
112 panic!("denominator == 0");
113 }
114 let mut ret = Ratio::new_raw(numer, denom);
115 ret.reduce();
116 ret
117 }
118
119 /// Creates a `Ratio` representing the integer `t`.
120 #[inline]
from_integer(t: T) -> Ratio<T>121 pub fn from_integer(t: T) -> Ratio<T> {
122 Ratio::new_raw(t, One::one())
123 }
124
125 /// Converts to an integer, rounding towards zero.
126 #[inline]
to_integer(&self) -> T127 pub fn to_integer(&self) -> T {
128 self.trunc().numer
129 }
130
131 /// Returns true if the rational number is an integer (denominator is 1).
132 #[inline]
is_integer(&self) -> bool133 pub fn is_integer(&self) -> bool {
134 self.denom.is_one()
135 }
136
137 /// Puts self into lowest terms, with denom > 0.
reduce(&mut self)138 fn reduce(&mut self) {
139 let g: T = self.numer.gcd(&self.denom);
140
141 // FIXME(#5992): assignment operator overloads
142 // self.numer /= g;
143 // T: Clone + Integer != T: Clone + NumAssign
144 self.numer = self.numer.clone() / g.clone();
145 // FIXME(#5992): assignment operator overloads
146 // self.denom /= g;
147 // T: Clone + Integer != T: Clone + NumAssign
148 self.denom = self.denom.clone() / g;
149
150 // keep denom positive!
151 if self.denom < T::zero() {
152 self.numer = T::zero() - self.numer.clone();
153 self.denom = T::zero() - self.denom.clone();
154 }
155 }
156
157 /// Returns a reduced copy of self.
158 ///
159 /// In general, it is not necessary to use this method, as the only
160 /// method of procuring a non-reduced fraction is through `new_raw`.
reduced(&self) -> Ratio<T>161 pub fn reduced(&self) -> Ratio<T> {
162 let mut ret = self.clone();
163 ret.reduce();
164 ret
165 }
166
167 /// Returns the reciprocal.
168 ///
169 /// Fails if the `Ratio` is zero.
170 #[inline]
recip(&self) -> Ratio<T>171 pub fn recip(&self) -> Ratio<T> {
172 match self.numer.cmp(&T::zero()) {
173 cmp::Ordering::Equal => panic!("numerator == 0"),
174 cmp::Ordering::Greater => Ratio::new_raw(self.denom.clone(), self.numer.clone()),
175 cmp::Ordering::Less => Ratio::new_raw(
176 T::zero() - self.denom.clone(),
177 T::zero() - self.numer.clone(),
178 ),
179 }
180 }
181
182 /// Rounds towards minus infinity.
183 #[inline]
floor(&self) -> Ratio<T>184 pub fn floor(&self) -> Ratio<T> {
185 if *self < Zero::zero() {
186 let one: T = One::one();
187 Ratio::from_integer(
188 (self.numer.clone() - self.denom.clone() + one) / self.denom.clone(),
189 )
190 } else {
191 Ratio::from_integer(self.numer.clone() / self.denom.clone())
192 }
193 }
194
195 /// Rounds towards plus infinity.
196 #[inline]
ceil(&self) -> Ratio<T>197 pub fn ceil(&self) -> Ratio<T> {
198 if *self < Zero::zero() {
199 Ratio::from_integer(self.numer.clone() / self.denom.clone())
200 } else {
201 let one: T = One::one();
202 Ratio::from_integer(
203 (self.numer.clone() + self.denom.clone() - one) / self.denom.clone(),
204 )
205 }
206 }
207
208 /// Rounds to the nearest integer. Rounds half-way cases away from zero.
209 #[inline]
round(&self) -> Ratio<T>210 pub fn round(&self) -> Ratio<T> {
211 let zero: Ratio<T> = Zero::zero();
212 let one: T = One::one();
213 let two: T = one.clone() + one.clone();
214
215 // Find unsigned fractional part of rational number
216 let mut fractional = self.fract();
217 if fractional < zero {
218 fractional = zero - fractional
219 };
220
221 // The algorithm compares the unsigned fractional part with 1/2, that
222 // is, a/b >= 1/2, or a >= b/2. For odd denominators, we use
223 // a >= (b/2)+1. This avoids overflow issues.
224 let half_or_larger = if fractional.denom().is_even() {
225 *fractional.numer() >= fractional.denom().clone() / two.clone()
226 } else {
227 *fractional.numer() >= (fractional.denom().clone() / two.clone()) + one.clone()
228 };
229
230 if half_or_larger {
231 let one: Ratio<T> = One::one();
232 if *self >= Zero::zero() {
233 self.trunc() + one
234 } else {
235 self.trunc() - one
236 }
237 } else {
238 self.trunc()
239 }
240 }
241
242 /// Rounds towards zero.
243 #[inline]
trunc(&self) -> Ratio<T>244 pub fn trunc(&self) -> Ratio<T> {
245 Ratio::from_integer(self.numer.clone() / self.denom.clone())
246 }
247
248 /// Returns the fractional part of a number, with division rounded towards zero.
249 ///
250 /// Satisfies `self == self.trunc() + self.fract()`.
251 #[inline]
fract(&self) -> Ratio<T>252 pub fn fract(&self) -> Ratio<T> {
253 Ratio::new_raw(self.numer.clone() % self.denom.clone(), self.denom.clone())
254 }
255 }
256
257 impl<T: Clone + Integer + Pow<u32, Output = T>> Ratio<T> {
258 /// Raises the `Ratio` to the power of an exponent.
259 #[inline]
pow(&self, expon: i32) -> Ratio<T>260 pub fn pow(&self, expon: i32) -> Ratio<T> {
261 Pow::pow(self, expon)
262 }
263 }
264
265 macro_rules! pow_impl {
266 ($exp:ty) => {
267 pow_impl!($exp, $exp);
268 };
269 ($exp:ty, $unsigned:ty) => {
270 impl<T: Clone + Integer + Pow<$unsigned, Output = T>> Pow<$exp> for Ratio<T> {
271 type Output = Ratio<T>;
272 #[inline]
273 fn pow(self, expon: $exp) -> Ratio<T> {
274 match expon.cmp(&0) {
275 cmp::Ordering::Equal => One::one(),
276 cmp::Ordering::Less => {
277 let expon = expon.wrapping_abs() as $unsigned;
278 Ratio::new_raw(Pow::pow(self.denom, expon), Pow::pow(self.numer, expon))
279 }
280 cmp::Ordering::Greater => Ratio::new_raw(
281 Pow::pow(self.numer, expon as $unsigned),
282 Pow::pow(self.denom, expon as $unsigned),
283 ),
284 }
285 }
286 }
287 impl<'a, T: Clone + Integer + Pow<$unsigned, Output = T>> Pow<$exp> for &'a Ratio<T> {
288 type Output = Ratio<T>;
289 #[inline]
290 fn pow(self, expon: $exp) -> Ratio<T> {
291 Pow::pow(self.clone(), expon)
292 }
293 }
294 impl<'a, T: Clone + Integer + Pow<$unsigned, Output = T>> Pow<&'a $exp> for Ratio<T> {
295 type Output = Ratio<T>;
296 #[inline]
297 fn pow(self, expon: &'a $exp) -> Ratio<T> {
298 Pow::pow(self, *expon)
299 }
300 }
301 impl<'a, 'b, T: Clone + Integer + Pow<$unsigned, Output = T>> Pow<&'a $exp>
302 for &'b Ratio<T>
303 {
304 type Output = Ratio<T>;
305 #[inline]
306 fn pow(self, expon: &'a $exp) -> Ratio<T> {
307 Pow::pow(self.clone(), *expon)
308 }
309 }
310 };
311 }
312
313 // this is solely to make `pow_impl!` work
314 trait WrappingAbs: Sized {
wrapping_abs(self) -> Self315 fn wrapping_abs(self) -> Self {
316 self
317 }
318 }
319 impl WrappingAbs for u8 {}
320 impl WrappingAbs for u16 {}
321 impl WrappingAbs for u32 {}
322 impl WrappingAbs for u64 {}
323 impl WrappingAbs for usize {}
324
325 pow_impl!(i8, u8);
326 pow_impl!(i16, u16);
327 pow_impl!(i32, u32);
328 pow_impl!(i64, u64);
329 pow_impl!(isize, usize);
330 pow_impl!(u8);
331 pow_impl!(u16);
332 pow_impl!(u32);
333 pow_impl!(u64);
334 pow_impl!(usize);
335
336 // TODO: pow_impl!(BigUint) and pow_impl!(BigInt, BigUint)
337
338 #[cfg(feature = "bigint")]
339 impl Ratio<BigInt> {
340 /// Converts a float into a rational number.
from_float<T: FloatCore>(f: T) -> Option<BigRational>341 pub fn from_float<T: FloatCore>(f: T) -> Option<BigRational> {
342 if !f.is_finite() {
343 return None;
344 }
345 let (mantissa, exponent, sign) = f.integer_decode();
346 let bigint_sign = if sign == 1 { Sign::Plus } else { Sign::Minus };
347 if exponent < 0 {
348 let one: BigInt = One::one();
349 let denom: BigInt = one << ((-exponent) as usize);
350 let numer: BigUint = FromPrimitive::from_u64(mantissa).unwrap();
351 Some(Ratio::new(BigInt::from_biguint(bigint_sign, numer), denom))
352 } else {
353 let mut numer: BigUint = FromPrimitive::from_u64(mantissa).unwrap();
354 numer = numer << (exponent as usize);
355 Some(Ratio::from_integer(BigInt::from_biguint(
356 bigint_sign,
357 numer,
358 )))
359 }
360 }
361 }
362
363 // From integer
364 impl<T> From<T> for Ratio<T>
365 where
366 T: Clone + Integer,
367 {
from(x: T) -> Ratio<T>368 fn from(x: T) -> Ratio<T> {
369 Ratio::from_integer(x)
370 }
371 }
372
373 // From pair (through the `new` constructor)
374 impl<T> From<(T, T)> for Ratio<T>
375 where
376 T: Clone + Integer,
377 {
from(pair: (T, T)) -> Ratio<T>378 fn from(pair: (T, T)) -> Ratio<T> {
379 Ratio::new(pair.0, pair.1)
380 }
381 }
382
383 // Comparisons
384
385 // Mathematically, comparing a/b and c/d is the same as comparing a*d and b*c, but it's very easy
386 // for those multiplications to overflow fixed-size integers, so we need to take care.
387
388 impl<T: Clone + Integer> Ord for Ratio<T> {
389 #[inline]
cmp(&self, other: &Self) -> cmp::Ordering390 fn cmp(&self, other: &Self) -> cmp::Ordering {
391 // With equal denominators, the numerators can be directly compared
392 if self.denom == other.denom {
393 let ord = self.numer.cmp(&other.numer);
394 return if self.denom < T::zero() {
395 ord.reverse()
396 } else {
397 ord
398 };
399 }
400
401 // With equal numerators, the denominators can be inversely compared
402 if self.numer == other.numer {
403 if self.numer.is_zero() {
404 return cmp::Ordering::Equal;
405 }
406 let ord = self.denom.cmp(&other.denom);
407 return if self.numer < T::zero() {
408 ord
409 } else {
410 ord.reverse()
411 };
412 }
413
414 // Unfortunately, we don't have CheckedMul to try. That could sometimes avoid all the
415 // division below, or even always avoid it for BigInt and BigUint.
416 // FIXME- future breaking change to add Checked* to Integer?
417
418 // Compare as floored integers and remainders
419 let (self_int, self_rem) = self.numer.div_mod_floor(&self.denom);
420 let (other_int, other_rem) = other.numer.div_mod_floor(&other.denom);
421 match self_int.cmp(&other_int) {
422 cmp::Ordering::Greater => cmp::Ordering::Greater,
423 cmp::Ordering::Less => cmp::Ordering::Less,
424 cmp::Ordering::Equal => {
425 match (self_rem.is_zero(), other_rem.is_zero()) {
426 (true, true) => cmp::Ordering::Equal,
427 (true, false) => cmp::Ordering::Less,
428 (false, true) => cmp::Ordering::Greater,
429 (false, false) => {
430 // Compare the reciprocals of the remaining fractions in reverse
431 let self_recip = Ratio::new_raw(self.denom.clone(), self_rem);
432 let other_recip = Ratio::new_raw(other.denom.clone(), other_rem);
433 self_recip.cmp(&other_recip).reverse()
434 }
435 }
436 }
437 }
438 }
439 }
440
441 impl<T: Clone + Integer> PartialOrd for Ratio<T> {
442 #[inline]
partial_cmp(&self, other: &Self) -> Option<cmp::Ordering>443 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
444 Some(self.cmp(other))
445 }
446 }
447
448 impl<T: Clone + Integer> PartialEq for Ratio<T> {
449 #[inline]
eq(&self, other: &Self) -> bool450 fn eq(&self, other: &Self) -> bool {
451 self.cmp(other) == cmp::Ordering::Equal
452 }
453 }
454
455 impl<T: Clone + Integer> Eq for Ratio<T> {}
456
457 // NB: We can't just `#[derive(Hash)]`, because it needs to agree
458 // with `Eq` even for non-reduced ratios.
459 impl<T: Clone + Integer + Hash> Hash for Ratio<T> {
hash<H: Hasher>(&self, state: &mut H)460 fn hash<H: Hasher>(&self, state: &mut H) {
461 recurse(&self.numer, &self.denom, state);
462
463 fn recurse<T: Integer + Hash, H: Hasher>(numer: &T, denom: &T, state: &mut H) {
464 if !denom.is_zero() {
465 let (int, rem) = numer.div_mod_floor(denom);
466 int.hash(state);
467 recurse(denom, &rem, state);
468 } else {
469 denom.hash(state);
470 }
471 }
472 }
473 }
474
475 mod iter_sum_product {
476 use core::iter::{Product, Sum};
477 use integer::Integer;
478 use traits::{One, Zero};
479 use Ratio;
480
481 impl<T: Integer + Clone> Sum for Ratio<T> {
sum<I>(iter: I) -> Self where I: Iterator<Item = Ratio<T>>,482 fn sum<I>(iter: I) -> Self
483 where
484 I: Iterator<Item = Ratio<T>>,
485 {
486 iter.fold(Self::zero(), |sum, num| sum + num)
487 }
488 }
489
490 impl<'a, T: Integer + Clone> Sum<&'a Ratio<T>> for Ratio<T> {
sum<I>(iter: I) -> Self where I: Iterator<Item = &'a Ratio<T>>,491 fn sum<I>(iter: I) -> Self
492 where
493 I: Iterator<Item = &'a Ratio<T>>,
494 {
495 iter.fold(Self::zero(), |sum, num| sum + num)
496 }
497 }
498
499 impl<T: Integer + Clone> Product for Ratio<T> {
product<I>(iter: I) -> Self where I: Iterator<Item = Ratio<T>>,500 fn product<I>(iter: I) -> Self
501 where
502 I: Iterator<Item = Ratio<T>>,
503 {
504 iter.fold(Self::one(), |prod, num| prod * num)
505 }
506 }
507
508 impl<'a, T: Integer + Clone> Product<&'a Ratio<T>> for Ratio<T> {
product<I>(iter: I) -> Self where I: Iterator<Item = &'a Ratio<T>>,509 fn product<I>(iter: I) -> Self
510 where
511 I: Iterator<Item = &'a Ratio<T>>,
512 {
513 iter.fold(Self::one(), |prod, num| prod * num)
514 }
515 }
516 }
517
518 mod opassign {
519 use core::ops::{AddAssign, DivAssign, MulAssign, RemAssign, SubAssign};
520
521 use integer::Integer;
522 use traits::NumAssign;
523 use Ratio;
524
525 impl<T: Clone + Integer + NumAssign> AddAssign for Ratio<T> {
add_assign(&mut self, other: Ratio<T>)526 fn add_assign(&mut self, other: Ratio<T>) {
527 if self.denom == other.denom {
528 self.numer += other.numer
529 } else {
530 let lcm = self.denom.lcm(&other.denom);
531 let lhs_numer = self.numer.clone() * (lcm.clone() / self.denom.clone());
532 let rhs_numer = other.numer * (lcm.clone() / other.denom);
533 self.numer = lhs_numer + rhs_numer;
534 self.denom = lcm;
535 }
536 self.reduce();
537 }
538 }
539
540 // (a/b) / (c/d) = (a/gcd_ac)*(d/gcd_bd) / ((c/gcd_ac)*(b/gcd_bd))
541 impl<T: Clone + Integer + NumAssign> DivAssign for Ratio<T> {
div_assign(&mut self, other: Ratio<T>)542 fn div_assign(&mut self, other: Ratio<T>) {
543 let gcd_ac = self.numer.gcd(&other.numer);
544 let gcd_bd = self.denom.gcd(&other.denom);
545 self.numer /= gcd_ac.clone();
546 self.numer *= other.denom / gcd_bd.clone();
547 self.denom /= gcd_bd;
548 self.denom *= other.numer / gcd_ac;
549 self.reduce(); //TODO: remove this line. see #8.
550 }
551 }
552
553 // a/b * c/d = (a/gcd_ad)*(c/gcd_bc) / ((d/gcd_ad)*(b/gcd_bc))
554 impl<T: Clone + Integer + NumAssign> MulAssign for Ratio<T> {
mul_assign(&mut self, other: Ratio<T>)555 fn mul_assign(&mut self, other: Ratio<T>) {
556 let gcd_ad = self.numer.gcd(&other.denom);
557 let gcd_bc = self.denom.gcd(&other.numer);
558 self.numer /= gcd_ad.clone();
559 self.numer *= other.numer / gcd_bc.clone();
560 self.denom /= gcd_bc;
561 self.denom *= other.denom / gcd_ad;
562 self.reduce(); //TODO: remove this line. see #8.
563 }
564 }
565
566 impl<T: Clone + Integer + NumAssign> RemAssign for Ratio<T> {
rem_assign(&mut self, other: Ratio<T>)567 fn rem_assign(&mut self, other: Ratio<T>) {
568 if self.denom == other.denom {
569 self.numer %= other.numer
570 } else {
571 let lcm = self.denom.lcm(&other.denom);
572 let lhs_numer = self.numer.clone() * (lcm.clone() / self.denom.clone());
573 let rhs_numer = other.numer * (lcm.clone() / other.denom);
574 self.numer = lhs_numer % rhs_numer;
575 self.denom = lcm;
576 }
577 self.reduce();
578 }
579 }
580
581 impl<T: Clone + Integer + NumAssign> SubAssign for Ratio<T> {
sub_assign(&mut self, other: Ratio<T>)582 fn sub_assign(&mut self, other: Ratio<T>) {
583 if self.denom == other.denom {
584 self.numer -= other.numer
585 } else {
586 let lcm = self.denom.lcm(&other.denom);
587 let lhs_numer = self.numer.clone() * (lcm.clone() / self.denom.clone());
588 let rhs_numer = other.numer * (lcm.clone() / other.denom);
589 self.numer = lhs_numer - rhs_numer;
590 self.denom = lcm;
591 }
592 self.reduce();
593 }
594 }
595
596 // a/b + c/1 = (a*1 + b*c) / (b*1) = (a + b*c) / b
597 impl<T: Clone + Integer + NumAssign> AddAssign<T> for Ratio<T> {
add_assign(&mut self, other: T)598 fn add_assign(&mut self, other: T) {
599 self.numer += self.denom.clone() * other;
600 self.reduce();
601 }
602 }
603
604 impl<T: Clone + Integer + NumAssign> DivAssign<T> for Ratio<T> {
div_assign(&mut self, other: T)605 fn div_assign(&mut self, other: T) {
606 let gcd = self.numer.gcd(&other);
607 self.numer /= gcd.clone();
608 self.denom *= other / gcd;
609 self.reduce(); //TODO: remove this line. see #8.
610 }
611 }
612
613 impl<T: Clone + Integer + NumAssign> MulAssign<T> for Ratio<T> {
mul_assign(&mut self, other: T)614 fn mul_assign(&mut self, other: T) {
615 let gcd = self.denom.gcd(&other);
616 self.denom /= gcd.clone();
617 self.numer *= other / gcd;
618 self.reduce(); //TODO: remove this line. see #8.
619 }
620 }
621
622 // a/b % c/1 = (a*1 % b*c) / (b*1) = (a % b*c) / b
623 impl<T: Clone + Integer + NumAssign> RemAssign<T> for Ratio<T> {
rem_assign(&mut self, other: T)624 fn rem_assign(&mut self, other: T) {
625 self.numer %= self.denom.clone() * other;
626 self.reduce();
627 }
628 }
629
630 // a/b - c/1 = (a*1 - b*c) / (b*1) = (a - b*c) / b
631 impl<T: Clone + Integer + NumAssign> SubAssign<T> for Ratio<T> {
sub_assign(&mut self, other: T)632 fn sub_assign(&mut self, other: T) {
633 self.numer -= self.denom.clone() * other;
634 self.reduce();
635 }
636 }
637
638 macro_rules! forward_op_assign {
639 (impl $imp:ident, $method:ident) => {
640 impl<'a, T: Clone + Integer + NumAssign> $imp<&'a Ratio<T>> for Ratio<T> {
641 #[inline]
642 fn $method(&mut self, other: &Ratio<T>) {
643 self.$method(other.clone())
644 }
645 }
646 impl<'a, T: Clone + Integer + NumAssign> $imp<&'a T> for Ratio<T> {
647 #[inline]
648 fn $method(&mut self, other: &T) {
649 self.$method(other.clone())
650 }
651 }
652 };
653 }
654
655 forward_op_assign!(impl AddAssign, add_assign);
656 forward_op_assign!(impl DivAssign, div_assign);
657 forward_op_assign!(impl MulAssign, mul_assign);
658 forward_op_assign!(impl RemAssign, rem_assign);
659 forward_op_assign!(impl SubAssign, sub_assign);
660 }
661
662 macro_rules! forward_ref_ref_binop {
663 (impl $imp:ident, $method:ident) => {
664 impl<'a, 'b, T: Clone + Integer> $imp<&'b Ratio<T>> for &'a Ratio<T> {
665 type Output = Ratio<T>;
666
667 #[inline]
668 fn $method(self, other: &'b Ratio<T>) -> Ratio<T> {
669 self.clone().$method(other.clone())
670 }
671 }
672 impl<'a, 'b, T: Clone + Integer> $imp<&'b T> for &'a Ratio<T> {
673 type Output = Ratio<T>;
674
675 #[inline]
676 fn $method(self, other: &'b T) -> Ratio<T> {
677 self.clone().$method(other.clone())
678 }
679 }
680 };
681 }
682
683 macro_rules! forward_ref_val_binop {
684 (impl $imp:ident, $method:ident) => {
685 impl<'a, T> $imp<Ratio<T>> for &'a Ratio<T>
686 where
687 T: Clone + Integer,
688 {
689 type Output = Ratio<T>;
690
691 #[inline]
692 fn $method(self, other: Ratio<T>) -> Ratio<T> {
693 self.clone().$method(other)
694 }
695 }
696 impl<'a, T> $imp<T> for &'a Ratio<T>
697 where
698 T: Clone + Integer,
699 {
700 type Output = Ratio<T>;
701
702 #[inline]
703 fn $method(self, other: T) -> Ratio<T> {
704 self.clone().$method(other)
705 }
706 }
707 };
708 }
709
710 macro_rules! forward_val_ref_binop {
711 (impl $imp:ident, $method:ident) => {
712 impl<'a, T> $imp<&'a Ratio<T>> for Ratio<T>
713 where
714 T: Clone + Integer,
715 {
716 type Output = Ratio<T>;
717
718 #[inline]
719 fn $method(self, other: &Ratio<T>) -> Ratio<T> {
720 self.$method(other.clone())
721 }
722 }
723 impl<'a, T> $imp<&'a T> for Ratio<T>
724 where
725 T: Clone + Integer,
726 {
727 type Output = Ratio<T>;
728
729 #[inline]
730 fn $method(self, other: &T) -> Ratio<T> {
731 self.$method(other.clone())
732 }
733 }
734 };
735 }
736
737 macro_rules! forward_all_binop {
738 (impl $imp:ident, $method:ident) => {
739 forward_ref_ref_binop!(impl $imp, $method);
740 forward_ref_val_binop!(impl $imp, $method);
741 forward_val_ref_binop!(impl $imp, $method);
742 };
743 }
744
745 // Arithmetic
746 forward_all_binop!(impl Mul, mul);
747 // a/b * c/d = (a/gcd_ad)*(c/gcd_bc) / ((d/gcd_ad)*(b/gcd_bc))
748 impl<T> Mul<Ratio<T>> for Ratio<T>
749 where
750 T: Clone + Integer,
751 {
752 type Output = Ratio<T>;
753 #[inline]
mul(self, rhs: Ratio<T>) -> Ratio<T>754 fn mul(self, rhs: Ratio<T>) -> Ratio<T> {
755 let gcd_ad = self.numer.gcd(&rhs.denom);
756 let gcd_bc = self.denom.gcd(&rhs.numer);
757 Ratio::new(
758 self.numer / gcd_ad.clone() * (rhs.numer / gcd_bc.clone()),
759 self.denom / gcd_bc * (rhs.denom / gcd_ad),
760 )
761 }
762 }
763 // a/b * c/1 = (a*c) / (b*1) = (a*c) / b
764 impl<T> Mul<T> for Ratio<T>
765 where
766 T: Clone + Integer,
767 {
768 type Output = Ratio<T>;
769 #[inline]
mul(self, rhs: T) -> Ratio<T>770 fn mul(self, rhs: T) -> Ratio<T> {
771 let gcd = self.denom.gcd(&rhs);
772 Ratio::new(self.numer * (rhs / gcd.clone()), self.denom / gcd)
773 }
774 }
775
776 forward_all_binop!(impl Div, div);
777 // (a/b) / (c/d) = (a/gcd_ac)*(d/gcd_bd) / ((c/gcd_ac)*(b/gcd_bd))
778 impl<T> Div<Ratio<T>> for Ratio<T>
779 where
780 T: Clone + Integer,
781 {
782 type Output = Ratio<T>;
783
784 #[inline]
div(self, rhs: Ratio<T>) -> Ratio<T>785 fn div(self, rhs: Ratio<T>) -> Ratio<T> {
786 let gcd_ac = self.numer.gcd(&rhs.numer);
787 let gcd_bd = self.denom.gcd(&rhs.denom);
788 Ratio::new(
789 self.numer / gcd_ac.clone() * (rhs.denom / gcd_bd.clone()),
790 self.denom / gcd_bd * (rhs.numer / gcd_ac),
791 )
792 }
793 }
794 // (a/b) / (c/1) = (a*1) / (b*c) = a / (b*c)
795 impl<T> Div<T> for Ratio<T>
796 where
797 T: Clone + Integer,
798 {
799 type Output = Ratio<T>;
800
801 #[inline]
div(self, rhs: T) -> Ratio<T>802 fn div(self, rhs: T) -> Ratio<T> {
803 let gcd = self.numer.gcd(&rhs);
804 Ratio::new(self.numer / gcd.clone(), self.denom * (rhs / gcd))
805 }
806 }
807
808 macro_rules! arith_impl {
809 (impl $imp:ident, $method:ident) => {
810 forward_all_binop!(impl $imp, $method);
811 // Abstracts a/b `op` c/d = (a*lcm/b `op` c*lcm/d)/lcm where lcm = lcm(b,d)
812 impl<T: Clone + Integer> $imp<Ratio<T>> for Ratio<T> {
813 type Output = Ratio<T>;
814 #[inline]
815 fn $method(self, rhs: Ratio<T>) -> Ratio<T> {
816 if self.denom == rhs.denom {
817 return Ratio::new(self.numer.$method(rhs.numer), rhs.denom);
818 }
819 let lcm = self.denom.lcm(&rhs.denom);
820 let lhs_numer = self.numer * (lcm.clone() / self.denom);
821 let rhs_numer = rhs.numer * (lcm.clone() / rhs.denom);
822 Ratio::new(lhs_numer.$method(rhs_numer), lcm)
823 }
824 }
825 // Abstracts the a/b `op` c/1 = (a*1 `op` b*c) / (b*1) = (a `op` b*c) / b pattern
826 impl<T: Clone + Integer> $imp<T> for Ratio<T> {
827 type Output = Ratio<T>;
828 #[inline]
829 fn $method(self, rhs: T) -> Ratio<T> {
830 Ratio::new(self.numer.$method(self.denom.clone() * rhs), self.denom)
831 }
832 }
833 };
834 }
835
836 arith_impl!(impl Add, add);
837 arith_impl!(impl Sub, sub);
838 arith_impl!(impl Rem, rem);
839
840 // Like `std::try!` for Option<T>, unwrap the value or early-return None.
841 // Since Rust 1.22 this can be replaced by the `?` operator.
842 macro_rules! otry {
843 ($expr:expr) => {
844 match $expr {
845 Some(val) => val,
846 None => return None,
847 }
848 };
849 }
850
851 // a/b * c/d = (a*c)/(b*d)
852 impl<T> CheckedMul for Ratio<T>
853 where
854 T: Clone + Integer + CheckedMul,
855 {
856 #[inline]
checked_mul(&self, rhs: &Ratio<T>) -> Option<Ratio<T>>857 fn checked_mul(&self, rhs: &Ratio<T>) -> Option<Ratio<T>> {
858 let gcd_ad = self.numer.gcd(&rhs.denom);
859 let gcd_bc = self.denom.gcd(&rhs.numer);
860 Some(Ratio::new(
861 otry!((self.numer.clone() / gcd_ad.clone())
862 .checked_mul(&(rhs.numer.clone() / gcd_bc.clone()))),
863 otry!((self.denom.clone() / gcd_bc).checked_mul(&(rhs.denom.clone() / gcd_ad))),
864 ))
865 }
866 }
867
868 // (a/b) / (c/d) = (a*d)/(b*c)
869 impl<T> CheckedDiv for Ratio<T>
870 where
871 T: Clone + Integer + CheckedMul,
872 {
873 #[inline]
checked_div(&self, rhs: &Ratio<T>) -> Option<Ratio<T>>874 fn checked_div(&self, rhs: &Ratio<T>) -> Option<Ratio<T>> {
875 let gcd_ac = self.numer.gcd(&rhs.numer);
876 let gcd_bd = self.denom.gcd(&rhs.denom);
877 let denom = otry!((self.denom.clone() / gcd_bd.clone())
878 .checked_mul(&(rhs.numer.clone() / gcd_ac.clone())));
879 if denom.is_zero() {
880 return None;
881 }
882 Some(Ratio::new(
883 otry!((self.numer.clone() / gcd_ac).checked_mul(&(rhs.denom.clone() / gcd_bd))),
884 denom,
885 ))
886 }
887 }
888
889 // As arith_impl! but for Checked{Add,Sub} traits
890 macro_rules! checked_arith_impl {
891 (impl $imp:ident, $method:ident) => {
892 impl<T: Clone + Integer + CheckedMul + $imp> $imp for Ratio<T> {
893 #[inline]
894 fn $method(&self, rhs: &Ratio<T>) -> Option<Ratio<T>> {
895 let gcd = self.denom.clone().gcd(&rhs.denom);
896 let lcm = otry!((self.denom.clone() / gcd.clone()).checked_mul(&rhs.denom));
897 let lhs_numer = otry!((lcm.clone() / self.denom.clone()).checked_mul(&self.numer));
898 let rhs_numer = otry!((lcm.clone() / rhs.denom.clone()).checked_mul(&rhs.numer));
899 Some(Ratio::new(otry!(lhs_numer.$method(&rhs_numer)), lcm))
900 }
901 }
902 };
903 }
904
905 // a/b + c/d = (lcm/b*a + lcm/d*c)/lcm, where lcm = lcm(b,d)
906 checked_arith_impl!(impl CheckedAdd, checked_add);
907
908 // a/b - c/d = (lcm/b*a - lcm/d*c)/lcm, where lcm = lcm(b,d)
909 checked_arith_impl!(impl CheckedSub, checked_sub);
910
911 impl<T> Neg for Ratio<T>
912 where
913 T: Clone + Integer + Neg<Output = T>,
914 {
915 type Output = Ratio<T>;
916
917 #[inline]
neg(self) -> Ratio<T>918 fn neg(self) -> Ratio<T> {
919 Ratio::new_raw(-self.numer, self.denom)
920 }
921 }
922
923 impl<'a, T> Neg for &'a Ratio<T>
924 where
925 T: Clone + Integer + Neg<Output = T>,
926 {
927 type Output = Ratio<T>;
928
929 #[inline]
neg(self) -> Ratio<T>930 fn neg(self) -> Ratio<T> {
931 -self.clone()
932 }
933 }
934
935 impl<T> Inv for Ratio<T>
936 where
937 T: Clone + Integer,
938 {
939 type Output = Ratio<T>;
940
941 #[inline]
inv(self) -> Ratio<T>942 fn inv(self) -> Ratio<T> {
943 self.recip()
944 }
945 }
946
947 impl<'a, T> Inv for &'a Ratio<T>
948 where
949 T: Clone + Integer,
950 {
951 type Output = Ratio<T>;
952
953 #[inline]
inv(self) -> Ratio<T>954 fn inv(self) -> Ratio<T> {
955 self.recip()
956 }
957 }
958
959 // Constants
960 impl<T: Clone + Integer> Zero for Ratio<T> {
961 #[inline]
zero() -> Ratio<T>962 fn zero() -> Ratio<T> {
963 Ratio::new_raw(Zero::zero(), One::one())
964 }
965
966 #[inline]
is_zero(&self) -> bool967 fn is_zero(&self) -> bool {
968 self.numer.is_zero()
969 }
970
971 #[inline]
set_zero(&mut self)972 fn set_zero(&mut self) {
973 self.numer.set_zero();
974 self.denom.set_one();
975 }
976 }
977
978 impl<T: Clone + Integer> One for Ratio<T> {
979 #[inline]
one() -> Ratio<T>980 fn one() -> Ratio<T> {
981 Ratio::new_raw(One::one(), One::one())
982 }
983
984 #[inline]
is_one(&self) -> bool985 fn is_one(&self) -> bool {
986 self.numer == self.denom
987 }
988
989 #[inline]
set_one(&mut self)990 fn set_one(&mut self) {
991 self.numer.set_one();
992 self.denom.set_one();
993 }
994 }
995
996 impl<T: Clone + Integer> Num for Ratio<T> {
997 type FromStrRadixErr = ParseRatioError;
998
999 /// Parses `numer/denom` where the numbers are in base `radix`.
from_str_radix(s: &str, radix: u32) -> Result<Ratio<T>, ParseRatioError>1000 fn from_str_radix(s: &str, radix: u32) -> Result<Ratio<T>, ParseRatioError> {
1001 if s.splitn(2, '/').count() == 2 {
1002 let mut parts = s.splitn(2, '/').map(|ss| {
1003 T::from_str_radix(ss, radix).map_err(|_| ParseRatioError {
1004 kind: RatioErrorKind::ParseError,
1005 })
1006 });
1007 let numer: T = parts.next().unwrap()?;
1008 let denom: T = parts.next().unwrap()?;
1009 if denom.is_zero() {
1010 Err(ParseRatioError {
1011 kind: RatioErrorKind::ZeroDenominator,
1012 })
1013 } else {
1014 Ok(Ratio::new(numer, denom))
1015 }
1016 } else {
1017 Err(ParseRatioError {
1018 kind: RatioErrorKind::ParseError,
1019 })
1020 }
1021 }
1022 }
1023
1024 impl<T: Clone + Integer + Signed> Signed for Ratio<T> {
1025 #[inline]
abs(&self) -> Ratio<T>1026 fn abs(&self) -> Ratio<T> {
1027 if self.is_negative() {
1028 -self.clone()
1029 } else {
1030 self.clone()
1031 }
1032 }
1033
1034 #[inline]
abs_sub(&self, other: &Ratio<T>) -> Ratio<T>1035 fn abs_sub(&self, other: &Ratio<T>) -> Ratio<T> {
1036 if *self <= *other {
1037 Zero::zero()
1038 } else {
1039 self - other
1040 }
1041 }
1042
1043 #[inline]
signum(&self) -> Ratio<T>1044 fn signum(&self) -> Ratio<T> {
1045 if self.is_positive() {
1046 Self::one()
1047 } else if self.is_zero() {
1048 Self::zero()
1049 } else {
1050 -Self::one()
1051 }
1052 }
1053
1054 #[inline]
is_positive(&self) -> bool1055 fn is_positive(&self) -> bool {
1056 (self.numer.is_positive() && self.denom.is_positive())
1057 || (self.numer.is_negative() && self.denom.is_negative())
1058 }
1059
1060 #[inline]
is_negative(&self) -> bool1061 fn is_negative(&self) -> bool {
1062 (self.numer.is_negative() && self.denom.is_positive())
1063 || (self.numer.is_positive() && self.denom.is_negative())
1064 }
1065 }
1066
1067 // String conversions
1068 impl<T> fmt::Display for Ratio<T>
1069 where
1070 T: fmt::Display + Eq + One,
1071 {
1072 /// Renders as `numer/denom`. If denom=1, renders as numer.
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result1073 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1074 if self.denom.is_one() {
1075 write!(f, "{}", self.numer)
1076 } else {
1077 write!(f, "{}/{}", self.numer, self.denom)
1078 }
1079 }
1080 }
1081
1082 impl<T: FromStr + Clone + Integer> FromStr for Ratio<T> {
1083 type Err = ParseRatioError;
1084
1085 /// Parses `numer/denom` or just `numer`.
from_str(s: &str) -> Result<Ratio<T>, ParseRatioError>1086 fn from_str(s: &str) -> Result<Ratio<T>, ParseRatioError> {
1087 let mut split = s.splitn(2, '/');
1088
1089 let n = try!(split.next().ok_or(ParseRatioError {
1090 kind: RatioErrorKind::ParseError
1091 }));
1092 let num = try!(FromStr::from_str(n).map_err(|_| ParseRatioError {
1093 kind: RatioErrorKind::ParseError
1094 }));
1095
1096 let d = split.next().unwrap_or("1");
1097 let den = try!(FromStr::from_str(d).map_err(|_| ParseRatioError {
1098 kind: RatioErrorKind::ParseError
1099 }));
1100
1101 if Zero::is_zero(&den) {
1102 Err(ParseRatioError {
1103 kind: RatioErrorKind::ZeroDenominator,
1104 })
1105 } else {
1106 Ok(Ratio::new(num, den))
1107 }
1108 }
1109 }
1110
1111 impl<T> Into<(T, T)> for Ratio<T> {
into(self) -> (T, T)1112 fn into(self) -> (T, T) {
1113 (self.numer, self.denom)
1114 }
1115 }
1116
1117 #[cfg(feature = "serde")]
1118 impl<T> serde::Serialize for Ratio<T>
1119 where
1120 T: serde::Serialize + Clone + Integer + PartialOrd,
1121 {
serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: serde::Serializer,1122 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1123 where
1124 S: serde::Serializer,
1125 {
1126 (self.numer(), self.denom()).serialize(serializer)
1127 }
1128 }
1129
1130 #[cfg(feature = "serde")]
1131 impl<'de, T> serde::Deserialize<'de> for Ratio<T>
1132 where
1133 T: serde::Deserialize<'de> + Clone + Integer + PartialOrd,
1134 {
deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: serde::Deserializer<'de>,1135 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1136 where
1137 D: serde::Deserializer<'de>,
1138 {
1139 use serde::de::Error;
1140 use serde::de::Unexpected;
1141 let (numer, denom): (T, T) = try!(serde::Deserialize::deserialize(deserializer));
1142 if denom.is_zero() {
1143 Err(Error::invalid_value(
1144 Unexpected::Signed(0),
1145 &"a ratio with non-zero denominator",
1146 ))
1147 } else {
1148 Ok(Ratio::new_raw(numer, denom))
1149 }
1150 }
1151 }
1152
1153 // FIXME: Bubble up specific errors
1154 #[derive(Copy, Clone, Debug, PartialEq)]
1155 pub struct ParseRatioError {
1156 kind: RatioErrorKind,
1157 }
1158
1159 #[derive(Copy, Clone, Debug, PartialEq)]
1160 enum RatioErrorKind {
1161 ParseError,
1162 ZeroDenominator,
1163 }
1164
1165 impl fmt::Display for ParseRatioError {
fmt(&self, f: &mut fmt::Formatter) -> fmt::Result1166 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1167 self.kind.description().fmt(f)
1168 }
1169 }
1170
1171 #[cfg(feature = "std")]
1172 impl Error for ParseRatioError {
description(&self) -> &str1173 fn description(&self) -> &str {
1174 self.kind.description()
1175 }
1176 }
1177
1178 impl RatioErrorKind {
description(&self) -> &'static str1179 fn description(&self) -> &'static str {
1180 match *self {
1181 RatioErrorKind::ParseError => "failed to parse integer",
1182 RatioErrorKind::ZeroDenominator => "zero value denominator",
1183 }
1184 }
1185 }
1186
1187 #[cfg(feature = "bigint")]
1188 impl FromPrimitive for Ratio<BigInt> {
from_i64(n: i64) -> Option<Self>1189 fn from_i64(n: i64) -> Option<Self> {
1190 Some(Ratio::from_integer(n.into()))
1191 }
1192
1193 #[cfg(has_i128)]
from_i128(n: i128) -> Option<Self>1194 fn from_i128(n: i128) -> Option<Self> {
1195 Some(Ratio::from_integer(n.into()))
1196 }
1197
from_u64(n: u64) -> Option<Self>1198 fn from_u64(n: u64) -> Option<Self> {
1199 Some(Ratio::from_integer(n.into()))
1200 }
1201
1202 #[cfg(has_i128)]
from_u128(n: u128) -> Option<Self>1203 fn from_u128(n: u128) -> Option<Self> {
1204 Some(Ratio::from_integer(n.into()))
1205 }
1206
from_f32(n: f32) -> Option<Self>1207 fn from_f32(n: f32) -> Option<Self> {
1208 Ratio::from_float(n)
1209 }
1210
from_f64(n: f64) -> Option<Self>1211 fn from_f64(n: f64) -> Option<Self> {
1212 Ratio::from_float(n)
1213 }
1214 }
1215
1216 macro_rules! from_primitive_integer {
1217 ($typ:ty, $approx:ident) => {
1218 impl FromPrimitive for Ratio<$typ> {
1219 fn from_i64(n: i64) -> Option<Self> {
1220 <$typ as FromPrimitive>::from_i64(n).map(Ratio::from_integer)
1221 }
1222
1223 #[cfg(has_i128)]
1224 fn from_i128(n: i128) -> Option<Self> {
1225 <$typ as FromPrimitive>::from_i128(n).map(Ratio::from_integer)
1226 }
1227
1228 fn from_u64(n: u64) -> Option<Self> {
1229 <$typ as FromPrimitive>::from_u64(n).map(Ratio::from_integer)
1230 }
1231
1232 #[cfg(has_i128)]
1233 fn from_u128(n: u128) -> Option<Self> {
1234 <$typ as FromPrimitive>::from_u128(n).map(Ratio::from_integer)
1235 }
1236
1237 fn from_f32(n: f32) -> Option<Self> {
1238 $approx(n, 10e-20, 30)
1239 }
1240
1241 fn from_f64(n: f64) -> Option<Self> {
1242 $approx(n, 10e-20, 30)
1243 }
1244 }
1245 };
1246 }
1247
1248 from_primitive_integer!(i8, approximate_float);
1249 from_primitive_integer!(i16, approximate_float);
1250 from_primitive_integer!(i32, approximate_float);
1251 from_primitive_integer!(i64, approximate_float);
1252 #[cfg(has_i128)]
1253 from_primitive_integer!(i128, approximate_float);
1254 from_primitive_integer!(isize, approximate_float);
1255
1256 from_primitive_integer!(u8, approximate_float_unsigned);
1257 from_primitive_integer!(u16, approximate_float_unsigned);
1258 from_primitive_integer!(u32, approximate_float_unsigned);
1259 from_primitive_integer!(u64, approximate_float_unsigned);
1260 #[cfg(has_i128)]
1261 from_primitive_integer!(u128, approximate_float_unsigned);
1262 from_primitive_integer!(usize, approximate_float_unsigned);
1263
1264 impl<T: Integer + Signed + Bounded + NumCast + Clone> Ratio<T> {
approximate_float<F: FloatCore + NumCast>(f: F) -> Option<Ratio<T>>1265 pub fn approximate_float<F: FloatCore + NumCast>(f: F) -> Option<Ratio<T>> {
1266 // 1/10e-20 < 1/2**32 which seems like a good default, and 30 seems
1267 // to work well. Might want to choose something based on the types in the future, e.g.
1268 // T::max().recip() and T::bits() or something similar.
1269 let epsilon = <F as NumCast>::from(10e-20).expect("Can't convert 10e-20");
1270 approximate_float(f, epsilon, 30)
1271 }
1272 }
1273
approximate_float<T, F>(val: F, max_error: F, max_iterations: usize) -> Option<Ratio<T>> where T: Integer + Signed + Bounded + NumCast + Clone, F: FloatCore + NumCast,1274 fn approximate_float<T, F>(val: F, max_error: F, max_iterations: usize) -> Option<Ratio<T>>
1275 where
1276 T: Integer + Signed + Bounded + NumCast + Clone,
1277 F: FloatCore + NumCast,
1278 {
1279 let negative = val.is_sign_negative();
1280 let abs_val = val.abs();
1281
1282 let r = approximate_float_unsigned(abs_val, max_error, max_iterations);
1283
1284 // Make negative again if needed
1285 if negative {
1286 r.map(|r| r.neg())
1287 } else {
1288 r
1289 }
1290 }
1291
1292 // No Unsigned constraint because this also works on positive integers and is called
1293 // like that, see above
approximate_float_unsigned<T, F>(val: F, max_error: F, max_iterations: usize) -> Option<Ratio<T>> where T: Integer + Bounded + NumCast + Clone, F: FloatCore + NumCast,1294 fn approximate_float_unsigned<T, F>(val: F, max_error: F, max_iterations: usize) -> Option<Ratio<T>>
1295 where
1296 T: Integer + Bounded + NumCast + Clone,
1297 F: FloatCore + NumCast,
1298 {
1299 // Continued fractions algorithm
1300 // http://mathforum.org/dr.math/faq/faq.fractions.html#decfrac
1301
1302 if val < F::zero() || val.is_nan() {
1303 return None;
1304 }
1305
1306 let mut q = val;
1307 let mut n0 = T::zero();
1308 let mut d0 = T::one();
1309 let mut n1 = T::one();
1310 let mut d1 = T::zero();
1311
1312 let t_max = T::max_value();
1313 let t_max_f = match <F as NumCast>::from(t_max.clone()) {
1314 None => return None,
1315 Some(t_max_f) => t_max_f,
1316 };
1317
1318 // 1/epsilon > T::MAX
1319 let epsilon = t_max_f.recip();
1320
1321 // Overflow
1322 if q > t_max_f {
1323 return None;
1324 }
1325
1326 for _ in 0..max_iterations {
1327 let a = match <T as NumCast>::from(q) {
1328 None => break,
1329 Some(a) => a,
1330 };
1331
1332 let a_f = match <F as NumCast>::from(a.clone()) {
1333 None => break,
1334 Some(a_f) => a_f,
1335 };
1336 let f = q - a_f;
1337
1338 // Prevent overflow
1339 if !a.is_zero()
1340 && (n1 > t_max.clone() / a.clone()
1341 || d1 > t_max.clone() / a.clone()
1342 || a.clone() * n1.clone() > t_max.clone() - n0.clone()
1343 || a.clone() * d1.clone() > t_max.clone() - d0.clone())
1344 {
1345 break;
1346 }
1347
1348 let n = a.clone() * n1.clone() + n0.clone();
1349 let d = a.clone() * d1.clone() + d0.clone();
1350
1351 n0 = n1;
1352 d0 = d1;
1353 n1 = n.clone();
1354 d1 = d.clone();
1355
1356 // Simplify fraction. Doing so here instead of at the end
1357 // allows us to get closer to the target value without overflows
1358 let g = Integer::gcd(&n1, &d1);
1359 if !g.is_zero() {
1360 n1 = n1 / g.clone();
1361 d1 = d1 / g.clone();
1362 }
1363
1364 // Close enough?
1365 let (n_f, d_f) = match (<F as NumCast>::from(n), <F as NumCast>::from(d)) {
1366 (Some(n_f), Some(d_f)) => (n_f, d_f),
1367 _ => break,
1368 };
1369 if (n_f / d_f - val).abs() < max_error {
1370 break;
1371 }
1372
1373 // Prevent division by ~0
1374 if f < epsilon {
1375 break;
1376 }
1377 q = f.recip();
1378 }
1379
1380 // Overflow
1381 if d1.is_zero() {
1382 return None;
1383 }
1384
1385 Some(Ratio::new(n1, d1))
1386 }
1387
1388 #[cfg(test)]
1389 #[cfg(feature = "std")]
hash<T: Hash>(x: &T) -> u641390 fn hash<T: Hash>(x: &T) -> u64 {
1391 use std::collections::hash_map::RandomState;
1392 use std::hash::BuildHasher;
1393 let mut hasher = <RandomState as BuildHasher>::Hasher::new();
1394 x.hash(&mut hasher);
1395 hasher.finish()
1396 }
1397
1398 #[cfg(test)]
1399 mod test {
1400 #[cfg(feature = "bigint")]
1401 use super::BigRational;
1402 use super::{Ratio, Rational, Rational64};
1403
1404 use core::f64;
1405 use core::i32;
1406 use core::str::FromStr;
1407 use integer::Integer;
1408 use traits::{FromPrimitive, One, Pow, Signed, Zero};
1409
1410 pub const _0: Rational = Ratio { numer: 0, denom: 1 };
1411 pub const _1: Rational = Ratio { numer: 1, denom: 1 };
1412 pub const _2: Rational = Ratio { numer: 2, denom: 1 };
1413 pub const _NEG2: Rational = Ratio {
1414 numer: -2,
1415 denom: 1,
1416 };
1417 pub const _1_2: Rational = Ratio { numer: 1, denom: 2 };
1418 pub const _3_2: Rational = Ratio { numer: 3, denom: 2 };
1419 pub const _5_2: Rational = Ratio { numer: 5, denom: 2 };
1420 pub const _NEG1_2: Rational = Ratio {
1421 numer: -1,
1422 denom: 2,
1423 };
1424 pub const _1_NEG2: Rational = Ratio {
1425 numer: 1,
1426 denom: -2,
1427 };
1428 pub const _NEG1_NEG2: Rational = Ratio {
1429 numer: -1,
1430 denom: -2,
1431 };
1432 pub const _1_3: Rational = Ratio { numer: 1, denom: 3 };
1433 pub const _NEG1_3: Rational = Ratio {
1434 numer: -1,
1435 denom: 3,
1436 };
1437 pub const _2_3: Rational = Ratio { numer: 2, denom: 3 };
1438 pub const _NEG2_3: Rational = Ratio {
1439 numer: -2,
1440 denom: 3,
1441 };
1442
1443 #[cfg(feature = "bigint")]
to_big(n: Rational) -> BigRational1444 pub fn to_big(n: Rational) -> BigRational {
1445 Ratio::new(
1446 FromPrimitive::from_isize(n.numer).unwrap(),
1447 FromPrimitive::from_isize(n.denom).unwrap(),
1448 )
1449 }
1450 #[cfg(not(feature = "bigint"))]
to_big(n: Rational) -> Rational1451 pub fn to_big(n: Rational) -> Rational {
1452 Ratio::new(
1453 FromPrimitive::from_isize(n.numer).unwrap(),
1454 FromPrimitive::from_isize(n.denom).unwrap(),
1455 )
1456 }
1457
1458 #[test]
test_test_constants()1459 fn test_test_constants() {
1460 // check our constants are what Ratio::new etc. would make.
1461 assert_eq!(_0, Zero::zero());
1462 assert_eq!(_1, One::one());
1463 assert_eq!(_2, Ratio::from_integer(2));
1464 assert_eq!(_1_2, Ratio::new(1, 2));
1465 assert_eq!(_3_2, Ratio::new(3, 2));
1466 assert_eq!(_NEG1_2, Ratio::new(-1, 2));
1467 assert_eq!(_2, From::from(2));
1468 }
1469
1470 #[test]
test_new_reduce()1471 fn test_new_reduce() {
1472 let one22 = Ratio::new(2, 2);
1473
1474 assert_eq!(one22, One::one());
1475 }
1476 #[test]
1477 #[should_panic]
test_new_zero()1478 fn test_new_zero() {
1479 let _a = Ratio::new(1, 0);
1480 }
1481
1482 #[test]
test_approximate_float()1483 fn test_approximate_float() {
1484 assert_eq!(Ratio::from_f32(0.5f32), Some(Ratio::new(1i64, 2)));
1485 assert_eq!(Ratio::from_f64(0.5f64), Some(Ratio::new(1i32, 2)));
1486 assert_eq!(Ratio::from_f32(5f32), Some(Ratio::new(5i64, 1)));
1487 assert_eq!(Ratio::from_f64(5f64), Some(Ratio::new(5i32, 1)));
1488 assert_eq!(Ratio::from_f32(29.97f32), Some(Ratio::new(2997i64, 100)));
1489 assert_eq!(Ratio::from_f32(-29.97f32), Some(Ratio::new(-2997i64, 100)));
1490
1491 assert_eq!(Ratio::<i8>::from_f32(63.5f32), Some(Ratio::new(127i8, 2)));
1492 assert_eq!(Ratio::<i8>::from_f32(126.5f32), Some(Ratio::new(126i8, 1)));
1493 assert_eq!(Ratio::<i8>::from_f32(127.0f32), Some(Ratio::new(127i8, 1)));
1494 assert_eq!(Ratio::<i8>::from_f32(127.5f32), None);
1495 assert_eq!(Ratio::<i8>::from_f32(-63.5f32), Some(Ratio::new(-127i8, 2)));
1496 assert_eq!(
1497 Ratio::<i8>::from_f32(-126.5f32),
1498 Some(Ratio::new(-126i8, 1))
1499 );
1500 assert_eq!(
1501 Ratio::<i8>::from_f32(-127.0f32),
1502 Some(Ratio::new(-127i8, 1))
1503 );
1504 assert_eq!(Ratio::<i8>::from_f32(-127.5f32), None);
1505
1506 assert_eq!(Ratio::<u8>::from_f32(-127f32), None);
1507 assert_eq!(Ratio::<u8>::from_f32(127f32), Some(Ratio::new(127u8, 1)));
1508 assert_eq!(Ratio::<u8>::from_f32(127.5f32), Some(Ratio::new(255u8, 2)));
1509 assert_eq!(Ratio::<u8>::from_f32(256f32), None);
1510
1511 assert_eq!(Ratio::<i64>::from_f64(-10e200), None);
1512 assert_eq!(Ratio::<i64>::from_f64(10e200), None);
1513 assert_eq!(Ratio::<i64>::from_f64(f64::INFINITY), None);
1514 assert_eq!(Ratio::<i64>::from_f64(f64::NEG_INFINITY), None);
1515 assert_eq!(Ratio::<i64>::from_f64(f64::NAN), None);
1516 assert_eq!(
1517 Ratio::<i64>::from_f64(f64::EPSILON),
1518 Some(Ratio::new(1, 4503599627370496))
1519 );
1520 assert_eq!(Ratio::<i64>::from_f64(0.0), Some(Ratio::new(0, 1)));
1521 assert_eq!(Ratio::<i64>::from_f64(-0.0), Some(Ratio::new(0, 1)));
1522 }
1523
1524 #[test]
test_cmp()1525 fn test_cmp() {
1526 assert!(_0 == _0 && _1 == _1);
1527 assert!(_0 != _1 && _1 != _0);
1528 assert!(_0 < _1 && !(_1 < _0));
1529 assert!(_1 > _0 && !(_0 > _1));
1530
1531 assert!(_0 <= _0 && _1 <= _1);
1532 assert!(_0 <= _1 && !(_1 <= _0));
1533
1534 assert!(_0 >= _0 && _1 >= _1);
1535 assert!(_1 >= _0 && !(_0 >= _1));
1536
1537 let _0_2: Rational = Ratio::new_raw(0, 2);
1538 assert_eq!(_0, _0_2);
1539 }
1540
1541 #[test]
test_cmp_overflow()1542 fn test_cmp_overflow() {
1543 use core::cmp::Ordering;
1544
1545 // issue #7 example:
1546 let big = Ratio::new(128u8, 1);
1547 let small = big.recip();
1548 assert!(big > small);
1549
1550 // try a few that are closer together
1551 // (some matching numer, some matching denom, some neither)
1552 let ratios = [
1553 Ratio::new(125_i8, 127_i8),
1554 Ratio::new(63_i8, 64_i8),
1555 Ratio::new(124_i8, 125_i8),
1556 Ratio::new(125_i8, 126_i8),
1557 Ratio::new(126_i8, 127_i8),
1558 Ratio::new(127_i8, 126_i8),
1559 ];
1560
1561 fn check_cmp(a: Ratio<i8>, b: Ratio<i8>, ord: Ordering) {
1562 #[cfg(feature = "std")]
1563 println!("comparing {} and {}", a, b);
1564 assert_eq!(a.cmp(&b), ord);
1565 assert_eq!(b.cmp(&a), ord.reverse());
1566 }
1567
1568 for (i, &a) in ratios.iter().enumerate() {
1569 check_cmp(a, a, Ordering::Equal);
1570 check_cmp(-a, a, Ordering::Less);
1571 for &b in &ratios[i + 1..] {
1572 check_cmp(a, b, Ordering::Less);
1573 check_cmp(-a, -b, Ordering::Greater);
1574 check_cmp(a.recip(), b.recip(), Ordering::Greater);
1575 check_cmp(-a.recip(), -b.recip(), Ordering::Less);
1576 }
1577 }
1578 }
1579
1580 #[test]
test_to_integer()1581 fn test_to_integer() {
1582 assert_eq!(_0.to_integer(), 0);
1583 assert_eq!(_1.to_integer(), 1);
1584 assert_eq!(_2.to_integer(), 2);
1585 assert_eq!(_1_2.to_integer(), 0);
1586 assert_eq!(_3_2.to_integer(), 1);
1587 assert_eq!(_NEG1_2.to_integer(), 0);
1588 }
1589
1590 #[test]
test_numer()1591 fn test_numer() {
1592 assert_eq!(_0.numer(), &0);
1593 assert_eq!(_1.numer(), &1);
1594 assert_eq!(_2.numer(), &2);
1595 assert_eq!(_1_2.numer(), &1);
1596 assert_eq!(_3_2.numer(), &3);
1597 assert_eq!(_NEG1_2.numer(), &(-1));
1598 }
1599 #[test]
test_denom()1600 fn test_denom() {
1601 assert_eq!(_0.denom(), &1);
1602 assert_eq!(_1.denom(), &1);
1603 assert_eq!(_2.denom(), &1);
1604 assert_eq!(_1_2.denom(), &2);
1605 assert_eq!(_3_2.denom(), &2);
1606 assert_eq!(_NEG1_2.denom(), &2);
1607 }
1608
1609 #[test]
test_is_integer()1610 fn test_is_integer() {
1611 assert!(_0.is_integer());
1612 assert!(_1.is_integer());
1613 assert!(_2.is_integer());
1614 assert!(!_1_2.is_integer());
1615 assert!(!_3_2.is_integer());
1616 assert!(!_NEG1_2.is_integer());
1617 }
1618
1619 #[test]
1620 #[cfg(feature = "std")]
test_show()1621 fn test_show() {
1622 use std::string::ToString;
1623 assert_eq!(format!("{}", _2), "2".to_string());
1624 assert_eq!(format!("{}", _1_2), "1/2".to_string());
1625 assert_eq!(format!("{}", _0), "0".to_string());
1626 assert_eq!(format!("{}", Ratio::from_integer(-2)), "-2".to_string());
1627 }
1628
1629 mod arith {
1630 use super::super::{Ratio, Rational};
1631 use super::{to_big, _0, _1, _1_2, _2, _3_2, _5_2, _NEG1_2};
1632 use core::fmt::Debug;
1633 use integer::Integer;
1634 use traits::{Bounded, CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, NumAssign};
1635
1636 #[test]
test_add()1637 fn test_add() {
1638 fn test(a: Rational, b: Rational, c: Rational) {
1639 assert_eq!(a + b, c);
1640 assert_eq!(
1641 {
1642 let mut x = a;
1643 x += b;
1644 x
1645 },
1646 c
1647 );
1648 assert_eq!(to_big(a) + to_big(b), to_big(c));
1649 assert_eq!(a.checked_add(&b), Some(c));
1650 assert_eq!(to_big(a).checked_add(&to_big(b)), Some(to_big(c)));
1651 }
1652 fn test_assign(a: Rational, b: isize, c: Rational) {
1653 assert_eq!(a + b, c);
1654 assert_eq!(
1655 {
1656 let mut x = a;
1657 x += b;
1658 x
1659 },
1660 c
1661 );
1662 }
1663
1664 test(_1, _1_2, _3_2);
1665 test(_1, _1, _2);
1666 test(_1_2, _3_2, _2);
1667 test(_1_2, _NEG1_2, _0);
1668 test_assign(_1_2, 1, _3_2);
1669 }
1670
1671 #[test]
test_add_overflow()1672 fn test_add_overflow() {
1673 // compares Ratio(1, T::max_value()) + Ratio(1, T::max_value())
1674 // to Ratio(1+1, T::max_value()) for each integer type.
1675 // Previously, this calculation would overflow.
1676 fn test_add_typed_overflow<T>()
1677 where
1678 T: Integer + Bounded + Clone + Debug + NumAssign,
1679 {
1680 let _1_max = Ratio::new(T::one(), T::max_value());
1681 let _2_max = Ratio::new(T::one() + T::one(), T::max_value());
1682 assert_eq!(_1_max.clone() + _1_max.clone(), _2_max);
1683 assert_eq!(
1684 {
1685 let mut tmp = _1_max.clone();
1686 tmp += _1_max.clone();
1687 tmp
1688 },
1689 _2_max.clone()
1690 );
1691 }
1692 test_add_typed_overflow::<u8>();
1693 test_add_typed_overflow::<u16>();
1694 test_add_typed_overflow::<u32>();
1695 test_add_typed_overflow::<u64>();
1696 test_add_typed_overflow::<usize>();
1697 #[cfg(has_u128)]
1698 test_add_typed_overflow::<u128>();
1699
1700 test_add_typed_overflow::<i8>();
1701 test_add_typed_overflow::<i16>();
1702 test_add_typed_overflow::<i32>();
1703 test_add_typed_overflow::<i64>();
1704 test_add_typed_overflow::<isize>();
1705 #[cfg(has_i128)]
1706 test_add_typed_overflow::<i128>();
1707 }
1708
1709 #[test]
test_sub()1710 fn test_sub() {
1711 fn test(a: Rational, b: Rational, c: Rational) {
1712 assert_eq!(a - b, c);
1713 assert_eq!(
1714 {
1715 let mut x = a;
1716 x -= b;
1717 x
1718 },
1719 c
1720 );
1721 assert_eq!(to_big(a) - to_big(b), to_big(c));
1722 assert_eq!(a.checked_sub(&b), Some(c));
1723 assert_eq!(to_big(a).checked_sub(&to_big(b)), Some(to_big(c)));
1724 }
1725 fn test_assign(a: Rational, b: isize, c: Rational) {
1726 assert_eq!(a - b, c);
1727 assert_eq!(
1728 {
1729 let mut x = a;
1730 x -= b;
1731 x
1732 },
1733 c
1734 );
1735 }
1736
1737 test(_1, _1_2, _1_2);
1738 test(_3_2, _1_2, _1);
1739 test(_1, _NEG1_2, _3_2);
1740 test_assign(_1_2, 1, _NEG1_2);
1741 }
1742
1743 #[test]
test_sub_overflow()1744 fn test_sub_overflow() {
1745 // compares Ratio(1, T::max_value()) - Ratio(1, T::max_value()) to T::zero()
1746 // for each integer type. Previously, this calculation would overflow.
1747 fn test_sub_typed_overflow<T>()
1748 where
1749 T: Integer + Bounded + Clone + Debug + NumAssign,
1750 {
1751 let _1_max: Ratio<T> = Ratio::new(T::one(), T::max_value());
1752 assert!(T::is_zero(&(_1_max.clone() - _1_max.clone()).numer));
1753 {
1754 let mut tmp: Ratio<T> = _1_max.clone();
1755 tmp -= _1_max.clone();
1756 assert!(T::is_zero(&tmp.numer));
1757 }
1758 }
1759 test_sub_typed_overflow::<u8>();
1760 test_sub_typed_overflow::<u16>();
1761 test_sub_typed_overflow::<u32>();
1762 test_sub_typed_overflow::<u64>();
1763 test_sub_typed_overflow::<usize>();
1764 #[cfg(has_u128)]
1765 test_sub_typed_overflow::<u128>();
1766
1767 test_sub_typed_overflow::<i8>();
1768 test_sub_typed_overflow::<i16>();
1769 test_sub_typed_overflow::<i32>();
1770 test_sub_typed_overflow::<i64>();
1771 test_sub_typed_overflow::<isize>();
1772 #[cfg(has_i128)]
1773 test_sub_typed_overflow::<i128>();
1774 }
1775
1776 #[test]
test_mul()1777 fn test_mul() {
1778 fn test(a: Rational, b: Rational, c: Rational) {
1779 assert_eq!(a * b, c);
1780 assert_eq!(
1781 {
1782 let mut x = a;
1783 x *= b;
1784 x
1785 },
1786 c
1787 );
1788 assert_eq!(to_big(a) * to_big(b), to_big(c));
1789 assert_eq!(a.checked_mul(&b), Some(c));
1790 assert_eq!(to_big(a).checked_mul(&to_big(b)), Some(to_big(c)));
1791 }
1792 fn test_assign(a: Rational, b: isize, c: Rational) {
1793 assert_eq!(a * b, c);
1794 assert_eq!(
1795 {
1796 let mut x = a;
1797 x *= b;
1798 x
1799 },
1800 c
1801 );
1802 }
1803
1804 test(_1, _1_2, _1_2);
1805 test(_1_2, _3_2, Ratio::new(3, 4));
1806 test(_1_2, _NEG1_2, Ratio::new(-1, 4));
1807 test_assign(_1_2, 2, _1);
1808 }
1809
1810 #[test]
test_mul_overflow()1811 fn test_mul_overflow() {
1812 fn test_mul_typed_overflow<T>()
1813 where
1814 T: Integer + Bounded + Clone + Debug + NumAssign + CheckedMul,
1815 {
1816 let two = T::one() + T::one();
1817 let _3 = T::one() + T::one() + T::one();
1818
1819 // 1/big * 2/3 = 1/(max/4*3), where big is max/2
1820 // make big = max/2, but also divisible by 2
1821 let big = T::max_value() / two.clone() / two.clone() * two.clone();
1822 let _1_big: Ratio<T> = Ratio::new(T::one(), big.clone());
1823 let _2_3: Ratio<T> = Ratio::new(two.clone(), _3.clone());
1824 assert_eq!(None, big.clone().checked_mul(&_3.clone()));
1825 let expected = Ratio::new(T::one(), big / two.clone() * _3.clone());
1826 assert_eq!(expected.clone(), _1_big.clone() * _2_3.clone());
1827 assert_eq!(
1828 Some(expected.clone()),
1829 _1_big.clone().checked_mul(&_2_3.clone())
1830 );
1831 assert_eq!(expected, {
1832 let mut tmp = _1_big.clone();
1833 tmp *= _2_3;
1834 tmp
1835 });
1836
1837 // big/3 * 3 = big/1
1838 // make big = max/2, but make it indivisible by 3
1839 let big = T::max_value() / two.clone() / _3.clone() * _3.clone() + T::one();
1840 assert_eq!(None, big.clone().checked_mul(&_3.clone()));
1841 let big_3 = Ratio::new(big.clone(), _3.clone());
1842 let expected = Ratio::new(big.clone(), T::one());
1843 assert_eq!(expected, big_3.clone() * _3.clone());
1844 assert_eq!(expected, {
1845 let mut tmp = big_3.clone();
1846 tmp *= _3.clone();
1847 tmp
1848 });
1849 }
1850 test_mul_typed_overflow::<u16>();
1851 test_mul_typed_overflow::<u8>();
1852 test_mul_typed_overflow::<u32>();
1853 test_mul_typed_overflow::<u64>();
1854 test_mul_typed_overflow::<usize>();
1855 #[cfg(has_u128)]
1856 test_mul_typed_overflow::<u128>();
1857
1858 test_mul_typed_overflow::<i8>();
1859 test_mul_typed_overflow::<i16>();
1860 test_mul_typed_overflow::<i32>();
1861 test_mul_typed_overflow::<i64>();
1862 test_mul_typed_overflow::<isize>();
1863 #[cfg(has_i128)]
1864 test_mul_typed_overflow::<i128>();
1865 }
1866
1867 #[test]
test_div()1868 fn test_div() {
1869 fn test(a: Rational, b: Rational, c: Rational) {
1870 assert_eq!(a / b, c);
1871 assert_eq!(
1872 {
1873 let mut x = a;
1874 x /= b;
1875 x
1876 },
1877 c
1878 );
1879 assert_eq!(to_big(a) / to_big(b), to_big(c));
1880 assert_eq!(a.checked_div(&b), Some(c));
1881 assert_eq!(to_big(a).checked_div(&to_big(b)), Some(to_big(c)));
1882 }
1883 fn test_assign(a: Rational, b: isize, c: Rational) {
1884 assert_eq!(a / b, c);
1885 assert_eq!(
1886 {
1887 let mut x = a;
1888 x /= b;
1889 x
1890 },
1891 c
1892 );
1893 }
1894
1895 test(_1, _1_2, _2);
1896 test(_3_2, _1_2, _1 + _2);
1897 test(_1, _NEG1_2, _NEG1_2 + _NEG1_2 + _NEG1_2 + _NEG1_2);
1898 test_assign(_1, 2, _1_2);
1899 }
1900
1901 #[test]
test_div_overflow()1902 fn test_div_overflow() {
1903 fn test_div_typed_overflow<T>()
1904 where
1905 T: Integer + Bounded + Clone + Debug + NumAssign + CheckedMul,
1906 {
1907 let two = T::one() + T::one();
1908 let _3 = T::one() + T::one() + T::one();
1909
1910 // 1/big / 3/2 = 1/(max/4*3), where big is max/2
1911 // big ~ max/2, and big is divisible by 2
1912 let big = T::max_value() / two.clone() / two.clone() * two.clone();
1913 assert_eq!(None, big.clone().checked_mul(&_3.clone()));
1914 let _1_big: Ratio<T> = Ratio::new(T::one(), big.clone());
1915 let _3_two: Ratio<T> = Ratio::new(_3.clone(), two.clone());
1916 let expected = Ratio::new(T::one(), big.clone() / two.clone() * _3.clone());
1917 assert_eq!(expected.clone(), _1_big.clone() / _3_two.clone());
1918 assert_eq!(
1919 Some(expected.clone()),
1920 _1_big.clone().checked_div(&_3_two.clone())
1921 );
1922 assert_eq!(expected, {
1923 let mut tmp = _1_big.clone();
1924 tmp /= _3_two;
1925 tmp
1926 });
1927
1928 // 3/big / 3 = 1/big where big is max/2
1929 // big ~ max/2, and big is not divisible by 3
1930 let big = T::max_value() / two.clone() / _3.clone() * _3.clone() + T::one();
1931 assert_eq!(None, big.clone().checked_mul(&_3.clone()));
1932 let _3_big = Ratio::new(_3.clone(), big.clone());
1933 let expected = Ratio::new(T::one(), big.clone());
1934 assert_eq!(expected, _3_big.clone() / _3.clone());
1935 assert_eq!(expected, {
1936 let mut tmp = _3_big.clone();
1937 tmp /= _3.clone();
1938 tmp
1939 });
1940 }
1941 test_div_typed_overflow::<u8>();
1942 test_div_typed_overflow::<u16>();
1943 test_div_typed_overflow::<u32>();
1944 test_div_typed_overflow::<u64>();
1945 test_div_typed_overflow::<usize>();
1946 #[cfg(has_u128)]
1947 test_div_typed_overflow::<u128>();
1948
1949 test_div_typed_overflow::<i8>();
1950 test_div_typed_overflow::<i16>();
1951 test_div_typed_overflow::<i32>();
1952 test_div_typed_overflow::<i64>();
1953 test_div_typed_overflow::<isize>();
1954 #[cfg(has_i128)]
1955 test_div_typed_overflow::<i128>();
1956 }
1957
1958 #[test]
test_rem()1959 fn test_rem() {
1960 fn test(a: Rational, b: Rational, c: Rational) {
1961 assert_eq!(a % b, c);
1962 assert_eq!(
1963 {
1964 let mut x = a;
1965 x %= b;
1966 x
1967 },
1968 c
1969 );
1970 assert_eq!(to_big(a) % to_big(b), to_big(c))
1971 }
1972 fn test_assign(a: Rational, b: isize, c: Rational) {
1973 assert_eq!(a % b, c);
1974 assert_eq!(
1975 {
1976 let mut x = a;
1977 x %= b;
1978 x
1979 },
1980 c
1981 );
1982 }
1983
1984 test(_3_2, _1, _1_2);
1985 test(_3_2, _1_2, _0);
1986 test(_5_2, _3_2, _1);
1987 test(_2, _NEG1_2, _0);
1988 test(_1_2, _2, _1_2);
1989 test_assign(_3_2, 1, _1_2);
1990 }
1991
1992 #[test]
test_rem_overflow()1993 fn test_rem_overflow() {
1994 // tests that Ratio(1,2) % Ratio(1, T::max_value()) equals 0
1995 // for each integer type. Previously, this calculation would overflow.
1996 fn test_rem_typed_overflow<T>()
1997 where
1998 T: Integer + Bounded + Clone + Debug + NumAssign,
1999 {
2000 let two = T::one() + T::one();
2001 //value near to maximum, but divisible by two
2002 let max_div2 = T::max_value() / two.clone() * two.clone();
2003 let _1_max: Ratio<T> = Ratio::new(T::one(), max_div2.clone());
2004 let _1_two: Ratio<T> = Ratio::new(T::one(), two);
2005 assert!(T::is_zero(&(_1_two.clone() % _1_max.clone()).numer));
2006 {
2007 let mut tmp: Ratio<T> = _1_two.clone();
2008 tmp %= _1_max.clone();
2009 assert!(T::is_zero(&tmp.numer));
2010 }
2011 }
2012 test_rem_typed_overflow::<u8>();
2013 test_rem_typed_overflow::<u16>();
2014 test_rem_typed_overflow::<u32>();
2015 test_rem_typed_overflow::<u64>();
2016 test_rem_typed_overflow::<usize>();
2017 #[cfg(has_u128)]
2018 test_rem_typed_overflow::<u128>();
2019
2020 test_rem_typed_overflow::<i8>();
2021 test_rem_typed_overflow::<i16>();
2022 test_rem_typed_overflow::<i32>();
2023 test_rem_typed_overflow::<i64>();
2024 test_rem_typed_overflow::<isize>();
2025 #[cfg(has_i128)]
2026 test_rem_typed_overflow::<i128>();
2027 }
2028
2029 #[test]
test_neg()2030 fn test_neg() {
2031 fn test(a: Rational, b: Rational) {
2032 assert_eq!(-a, b);
2033 assert_eq!(-to_big(a), to_big(b))
2034 }
2035
2036 test(_0, _0);
2037 test(_1_2, _NEG1_2);
2038 test(-_1, _1);
2039 }
2040 #[test]
test_zero()2041 fn test_zero() {
2042 assert_eq!(_0 + _0, _0);
2043 assert_eq!(_0 * _0, _0);
2044 assert_eq!(_0 * _1, _0);
2045 assert_eq!(_0 / _NEG1_2, _0);
2046 assert_eq!(_0 - _0, _0);
2047 }
2048 #[test]
2049 #[should_panic]
test_div_0()2050 fn test_div_0() {
2051 let _a = _1 / _0;
2052 }
2053
2054 #[test]
test_checked_failures()2055 fn test_checked_failures() {
2056 let big = Ratio::new(128u8, 1);
2057 let small = Ratio::new(1, 128u8);
2058 assert_eq!(big.checked_add(&big), None);
2059 assert_eq!(small.checked_sub(&big), None);
2060 assert_eq!(big.checked_mul(&big), None);
2061 assert_eq!(small.checked_div(&big), None);
2062 assert_eq!(_1.checked_div(&_0), None);
2063 }
2064 }
2065
2066 #[test]
test_round()2067 fn test_round() {
2068 assert_eq!(_1_3.ceil(), _1);
2069 assert_eq!(_1_3.floor(), _0);
2070 assert_eq!(_1_3.round(), _0);
2071 assert_eq!(_1_3.trunc(), _0);
2072
2073 assert_eq!(_NEG1_3.ceil(), _0);
2074 assert_eq!(_NEG1_3.floor(), -_1);
2075 assert_eq!(_NEG1_3.round(), _0);
2076 assert_eq!(_NEG1_3.trunc(), _0);
2077
2078 assert_eq!(_2_3.ceil(), _1);
2079 assert_eq!(_2_3.floor(), _0);
2080 assert_eq!(_2_3.round(), _1);
2081 assert_eq!(_2_3.trunc(), _0);
2082
2083 assert_eq!(_NEG2_3.ceil(), _0);
2084 assert_eq!(_NEG2_3.floor(), -_1);
2085 assert_eq!(_NEG2_3.round(), -_1);
2086 assert_eq!(_NEG2_3.trunc(), _0);
2087
2088 assert_eq!(_1_2.ceil(), _1);
2089 assert_eq!(_1_2.floor(), _0);
2090 assert_eq!(_1_2.round(), _1);
2091 assert_eq!(_1_2.trunc(), _0);
2092
2093 assert_eq!(_NEG1_2.ceil(), _0);
2094 assert_eq!(_NEG1_2.floor(), -_1);
2095 assert_eq!(_NEG1_2.round(), -_1);
2096 assert_eq!(_NEG1_2.trunc(), _0);
2097
2098 assert_eq!(_1.ceil(), _1);
2099 assert_eq!(_1.floor(), _1);
2100 assert_eq!(_1.round(), _1);
2101 assert_eq!(_1.trunc(), _1);
2102
2103 // Overflow checks
2104
2105 let _neg1 = Ratio::from_integer(-1);
2106 let _large_rat1 = Ratio::new(i32::MAX, i32::MAX - 1);
2107 let _large_rat2 = Ratio::new(i32::MAX - 1, i32::MAX);
2108 let _large_rat3 = Ratio::new(i32::MIN + 2, i32::MIN + 1);
2109 let _large_rat4 = Ratio::new(i32::MIN + 1, i32::MIN + 2);
2110 let _large_rat5 = Ratio::new(i32::MIN + 2, i32::MAX);
2111 let _large_rat6 = Ratio::new(i32::MAX, i32::MIN + 2);
2112 let _large_rat7 = Ratio::new(1, i32::MIN + 1);
2113 let _large_rat8 = Ratio::new(1, i32::MAX);
2114
2115 assert_eq!(_large_rat1.round(), One::one());
2116 assert_eq!(_large_rat2.round(), One::one());
2117 assert_eq!(_large_rat3.round(), One::one());
2118 assert_eq!(_large_rat4.round(), One::one());
2119 assert_eq!(_large_rat5.round(), _neg1);
2120 assert_eq!(_large_rat6.round(), _neg1);
2121 assert_eq!(_large_rat7.round(), Zero::zero());
2122 assert_eq!(_large_rat8.round(), Zero::zero());
2123 }
2124
2125 #[test]
test_fract()2126 fn test_fract() {
2127 assert_eq!(_1.fract(), _0);
2128 assert_eq!(_NEG1_2.fract(), _NEG1_2);
2129 assert_eq!(_1_2.fract(), _1_2);
2130 assert_eq!(_3_2.fract(), _1_2);
2131 }
2132
2133 #[test]
test_recip()2134 fn test_recip() {
2135 assert_eq!(_1 * _1.recip(), _1);
2136 assert_eq!(_2 * _2.recip(), _1);
2137 assert_eq!(_1_2 * _1_2.recip(), _1);
2138 assert_eq!(_3_2 * _3_2.recip(), _1);
2139 assert_eq!(_NEG1_2 * _NEG1_2.recip(), _1);
2140
2141 assert_eq!(_3_2.recip(), _2_3);
2142 assert_eq!(_NEG1_2.recip(), _NEG2);
2143 assert_eq!(_NEG1_2.recip().denom(), &1);
2144 }
2145
2146 #[test]
2147 #[should_panic(expected = "== 0")]
test_recip_fail()2148 fn test_recip_fail() {
2149 let _a = Ratio::new(0, 1).recip();
2150 }
2151
2152 #[test]
test_pow()2153 fn test_pow() {
2154 fn test(r: Rational, e: i32, expected: Rational) {
2155 assert_eq!(r.pow(e), expected);
2156 assert_eq!(Pow::pow(r, e), expected);
2157 assert_eq!(Pow::pow(r, &e), expected);
2158 assert_eq!(Pow::pow(&r, e), expected);
2159 assert_eq!(Pow::pow(&r, &e), expected);
2160 }
2161
2162 test(_1_2, 2, Ratio::new(1, 4));
2163 test(_1_2, -2, Ratio::new(4, 1));
2164 test(_1, 1, _1);
2165 test(_1, i32::MAX, _1);
2166 test(_1, i32::MIN, _1);
2167 test(_NEG1_2, 2, _1_2.pow(2i32));
2168 test(_NEG1_2, 3, -_1_2.pow(3i32));
2169 test(_3_2, 0, _1);
2170 test(_3_2, -1, _3_2.recip());
2171 test(_3_2, 3, Ratio::new(27, 8));
2172 }
2173
2174 #[test]
2175 #[cfg(feature = "std")]
test_to_from_str()2176 fn test_to_from_str() {
2177 use std::string::{String, ToString};
2178 fn test(r: Rational, s: String) {
2179 assert_eq!(FromStr::from_str(&s), Ok(r));
2180 assert_eq!(r.to_string(), s);
2181 }
2182 test(_1, "1".to_string());
2183 test(_0, "0".to_string());
2184 test(_1_2, "1/2".to_string());
2185 test(_3_2, "3/2".to_string());
2186 test(_2, "2".to_string());
2187 test(_NEG1_2, "-1/2".to_string());
2188 }
2189 #[test]
test_from_str_fail()2190 fn test_from_str_fail() {
2191 fn test(s: &str) {
2192 let rational: Result<Rational, _> = FromStr::from_str(s);
2193 assert!(rational.is_err());
2194 }
2195
2196 let xs = ["0 /1", "abc", "", "1/", "--1/2", "3/2/1", "1/0"];
2197 for &s in xs.iter() {
2198 test(s);
2199 }
2200 }
2201
2202 #[cfg(feature = "bigint")]
2203 #[test]
test_from_float()2204 fn test_from_float() {
2205 use traits::float::FloatCore;
2206 fn test<T: FloatCore>(given: T, (numer, denom): (&str, &str)) {
2207 let ratio: BigRational = Ratio::from_float(given).unwrap();
2208 assert_eq!(
2209 ratio,
2210 Ratio::new(
2211 FromStr::from_str(numer).unwrap(),
2212 FromStr::from_str(denom).unwrap()
2213 )
2214 );
2215 }
2216
2217 // f32
2218 test(3.14159265359f32, ("13176795", "4194304"));
2219 test(2f32.powf(100.), ("1267650600228229401496703205376", "1"));
2220 test(-2f32.powf(100.), ("-1267650600228229401496703205376", "1"));
2221 test(
2222 1.0 / 2f32.powf(100.),
2223 ("1", "1267650600228229401496703205376"),
2224 );
2225 test(684729.48391f32, ("1369459", "2"));
2226 test(-8573.5918555f32, ("-4389679", "512"));
2227
2228 // f64
2229 test(3.14159265359f64, ("3537118876014453", "1125899906842624"));
2230 test(2f64.powf(100.), ("1267650600228229401496703205376", "1"));
2231 test(-2f64.powf(100.), ("-1267650600228229401496703205376", "1"));
2232 test(684729.48391f64, ("367611342500051", "536870912"));
2233 test(-8573.5918555f64, ("-4713381968463931", "549755813888"));
2234 test(
2235 1.0 / 2f64.powf(100.),
2236 ("1", "1267650600228229401496703205376"),
2237 );
2238 }
2239
2240 #[cfg(feature = "bigint")]
2241 #[test]
test_from_float_fail()2242 fn test_from_float_fail() {
2243 use core::{f32, f64};
2244
2245 assert_eq!(Ratio::from_float(f32::NAN), None);
2246 assert_eq!(Ratio::from_float(f32::INFINITY), None);
2247 assert_eq!(Ratio::from_float(f32::NEG_INFINITY), None);
2248 assert_eq!(Ratio::from_float(f64::NAN), None);
2249 assert_eq!(Ratio::from_float(f64::INFINITY), None);
2250 assert_eq!(Ratio::from_float(f64::NEG_INFINITY), None);
2251 }
2252
2253 #[test]
test_signed()2254 fn test_signed() {
2255 assert_eq!(_NEG1_2.abs(), _1_2);
2256 assert_eq!(_3_2.abs_sub(&_1_2), _1);
2257 assert_eq!(_1_2.abs_sub(&_3_2), Zero::zero());
2258 assert_eq!(_1_2.signum(), One::one());
2259 assert_eq!(_NEG1_2.signum(), -<Ratio<isize>>::one());
2260 assert_eq!(_0.signum(), Zero::zero());
2261 assert!(_NEG1_2.is_negative());
2262 assert!(_1_NEG2.is_negative());
2263 assert!(!_NEG1_2.is_positive());
2264 assert!(!_1_NEG2.is_positive());
2265 assert!(_1_2.is_positive());
2266 assert!(_NEG1_NEG2.is_positive());
2267 assert!(!_1_2.is_negative());
2268 assert!(!_NEG1_NEG2.is_negative());
2269 assert!(!_0.is_positive());
2270 assert!(!_0.is_negative());
2271 }
2272
2273 #[test]
2274 #[cfg(feature = "std")]
test_hash()2275 fn test_hash() {
2276 assert!(::hash(&_0) != ::hash(&_1));
2277 assert!(::hash(&_0) != ::hash(&_3_2));
2278
2279 // a == b -> hash(a) == hash(b)
2280 let a = Rational::new_raw(4, 2);
2281 let b = Rational::new_raw(6, 3);
2282 assert_eq!(a, b);
2283 assert_eq!(::hash(&a), ::hash(&b));
2284
2285 let a = Rational::new_raw(123456789, 1000);
2286 let b = Rational::new_raw(123456789 * 5, 5000);
2287 assert_eq!(a, b);
2288 assert_eq!(::hash(&a), ::hash(&b));
2289 }
2290
2291 #[test]
test_into_pair()2292 fn test_into_pair() {
2293 assert_eq!((0, 1), _0.into());
2294 assert_eq!((-2, 1), _NEG2.into());
2295 assert_eq!((1, -2), _1_NEG2.into());
2296 }
2297
2298 #[test]
test_from_pair()2299 fn test_from_pair() {
2300 assert_eq!(_0, Ratio::from((0, 1)));
2301 assert_eq!(_1, Ratio::from((1, 1)));
2302 assert_eq!(_NEG2, Ratio::from((-2, 1)));
2303 assert_eq!(_1_NEG2, Ratio::from((1, -2)));
2304 }
2305
2306 #[test]
ratio_iter_sum()2307 fn ratio_iter_sum() {
2308 // generic function to assure the iter method can be called
2309 // for any Iterator with Item = Ratio<impl Integer> or Ratio<&impl Integer>
2310 fn iter_sums<T: Integer + Clone>(slice: &[Ratio<T>]) -> [Ratio<T>; 3] {
2311 let mut manual_sum = Ratio::new(T::zero(), T::one());
2312 for ratio in slice {
2313 manual_sum = manual_sum + ratio;
2314 }
2315 [manual_sum, slice.iter().sum(), slice.iter().cloned().sum()]
2316 }
2317 // collect into array so test works on no_std
2318 let mut nums = [Ratio::new(0, 1); 1000];
2319 for (i, r) in (0..1000).map(|n| Ratio::new(n, 500)).enumerate() {
2320 nums[i] = r;
2321 }
2322 let sums = iter_sums(&nums[..]);
2323 assert_eq!(sums[0], sums[1]);
2324 assert_eq!(sums[0], sums[2]);
2325 }
2326
2327 #[test]
ratio_iter_product()2328 fn ratio_iter_product() {
2329 // generic function to assure the iter method can be called
2330 // for any Iterator with Item = Ratio<impl Integer> or Ratio<&impl Integer>
2331 fn iter_products<T: Integer + Clone>(slice: &[Ratio<T>]) -> [Ratio<T>; 3] {
2332 let mut manual_prod = Ratio::new(T::one(), T::one());
2333 for ratio in slice {
2334 manual_prod = manual_prod * ratio;
2335 }
2336 [
2337 manual_prod,
2338 slice.iter().product(),
2339 slice.iter().cloned().product(),
2340 ]
2341 }
2342
2343 // collect into array so test works on no_std
2344 let mut nums = [Ratio::new(0, 1); 1000];
2345 for (i, r) in (0..1000).map(|n| Ratio::new(n, 500)).enumerate() {
2346 nums[i] = r;
2347 }
2348 let products = iter_products(&nums[..]);
2349 assert_eq!(products[0], products[1]);
2350 assert_eq!(products[0], products[2]);
2351 }
2352
2353 #[test]
test_num_zero()2354 fn test_num_zero() {
2355 let zero = Rational64::zero();
2356 assert!(zero.is_zero());
2357
2358 let mut r = Rational64::new(123, 456);
2359 assert!(!r.is_zero());
2360 assert_eq!(&r + &zero, r);
2361
2362 r.set_zero();
2363 assert!(r.is_zero());
2364 }
2365
2366 #[test]
test_num_one()2367 fn test_num_one() {
2368 let one = Rational64::one();
2369 assert!(one.is_one());
2370
2371 let mut r = Rational64::new(123, 456);
2372 assert!(!r.is_one());
2373 assert_eq!(&r * &one, r);
2374
2375 r.set_one();
2376 assert!(r.is_one());
2377 }
2378
2379 #[cfg(has_const_fn)]
2380 #[test]
test_const()2381 fn test_const() {
2382 const N: Ratio<i32> = Ratio::new_raw(123, 456);
2383 const N_NUMER: &i32 = N.numer();
2384 const N_DENOM: &i32 = N.denom();
2385
2386 assert_eq!(N_NUMER, &123);
2387 assert_eq!(N_DENOM, &456);
2388
2389 let r = N.reduced();
2390 assert_eq!(r.numer(), &(123 / 3));
2391 assert_eq!(r.denom(), &(456 / 3));
2392 }
2393 }
2394