//! The `num-integer` crate is tested for rustc 1.8 and greater.
#![doc(html_root_url = "https://docs.rs/num-integer/0.1")]
-
#![no_std]
#[cfg(feature = "std")]
extern crate std;
extern crate num_traits as traits;
-use core::ops::Add;
use core::mem;
+use core::ops::Add;
-use traits::{Num, Signed};
+use traits::{Num, Signed, Zero};
mod roots;
pub use roots::Roots;
-pub use roots::{sqrt, cbrt, nth_root};
+pub use roots::{cbrt, nth_root, sqrt};
pub trait Integer: Sized + Num + PartialOrd + Ord + Eq {
/// Floored integer division.
/// ~~~
fn mod_floor(&self, other: &Self) -> Self;
+ /// Ceiled integer division.
+ ///
+ /// # Examples
+ ///
+ /// ~~~
+ /// # use num_integer::Integer;
+ /// assert_eq!(( 8).div_ceil( &3), 3);
+ /// assert_eq!(( 8).div_ceil(&-3), -2);
+ /// assert_eq!((-8).div_ceil( &3), -2);
+ /// assert_eq!((-8).div_ceil(&-3), 3);
+ ///
+ /// assert_eq!(( 1).div_ceil( &2), 1);
+ /// assert_eq!(( 1).div_ceil(&-2), 0);
+ /// assert_eq!((-1).div_ceil( &2), 0);
+ /// assert_eq!((-1).div_ceil(&-2), 1);
+ /// ~~~
+ fn div_ceil(&self, other: &Self) -> Self {
+ let (q, r) = self.div_mod_floor(other);
+ if r.is_zero() {
+ q
+ } else {
+ q + Self::one()
+ }
+ }
+
/// Greatest Common Divisor (GCD).
///
/// # Examples
/// # use num_integer::Integer;
/// assert_eq!(7.lcm(&3), 21);
/// assert_eq!(2.lcm(&4), 4);
+ /// assert_eq!(0.lcm(&0), 0);
/// ~~~
fn lcm(&self, other: &Self) -> Self;
+ /// Greatest Common Divisor (GCD) and
+ /// Lowest Common Multiple (LCM) together.
+ ///
+ /// Potentially more efficient than calling `gcd` and `lcm`
+ /// individually for identical inputs.
+ ///
+ /// # Examples
+ ///
+ /// ~~~
+ /// # use num_integer::Integer;
+ /// assert_eq!(10.gcd_lcm(&4), (2, 20));
+ /// assert_eq!(8.gcd_lcm(&9), (1, 72));
+ /// ~~~
+ #[inline]
+ fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
+ (self.gcd(other), self.lcm(other))
+ }
+
+ /// Greatest common divisor and Bézout coefficients.
+ ///
+ /// # Examples
+ ///
+ /// ~~~
+ /// # extern crate num_integer;
+ /// # extern crate num_traits;
+ /// # fn main() {
+ /// # use num_integer::{ExtendedGcd, Integer};
+ /// # use num_traits::NumAssign;
+ /// fn check<A: Copy + Integer + NumAssign>(a: A, b: A) -> bool {
+ /// let ExtendedGcd { gcd, x, y, .. } = a.extended_gcd(&b);
+ /// gcd == x * a + y * b
+ /// }
+ /// assert!(check(10isize, 4isize));
+ /// assert!(check(8isize, 9isize));
+ /// # }
+ /// ~~~
+ #[inline]
+ fn extended_gcd(&self, other: &Self) -> ExtendedGcd<Self>
+ where
+ Self: Clone,
+ {
+ let mut s = (Self::zero(), Self::one());
+ let mut t = (Self::one(), Self::zero());
+ let mut r = (other.clone(), self.clone());
+
+ while !r.0.is_zero() {
+ let q = r.1.clone() / r.0.clone();
+ let f = |mut r: (Self, Self)| {
+ mem::swap(&mut r.0, &mut r.1);
+ r.0 = r.0 - q.clone() * r.1.clone();
+ r
+ };
+ r = f(r);
+ s = f(s);
+ t = f(t);
+ }
+
+ if r.1 >= Self::zero() {
+ ExtendedGcd {
+ gcd: r.1,
+ x: s.1,
+ y: t.1,
+ _hidden: (),
+ }
+ } else {
+ ExtendedGcd {
+ gcd: Self::zero() - r.1,
+ x: Self::zero() - s.1,
+ y: Self::zero() - t.1,
+ _hidden: (),
+ }
+ }
+ }
+
+ /// Greatest common divisor, least common multiple, and Bézout coefficients.
+ #[inline]
+ fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self)
+ where
+ Self: Clone + Signed,
+ {
+ (self.extended_gcd(other), self.lcm(other))
+ }
+
/// Deprecated, use `is_multiple_of` instead.
fn divides(&self, other: &Self) -> bool;
fn div_mod_floor(&self, other: &Self) -> (Self, Self) {
(self.div_floor(other), self.mod_floor(other))
}
+
+ /// Rounds up to nearest multiple of argument.
+ ///
+ /// # Notes
+ ///
+ /// For signed types, `a.next_multiple_of(b) = a.prev_multiple_of(b.neg())`.
+ ///
+ /// # Examples
+ ///
+ /// ~~~
+ /// # use num_integer::Integer;
+ /// assert_eq!(( 16).next_multiple_of(& 8), 16);
+ /// assert_eq!(( 23).next_multiple_of(& 8), 24);
+ /// assert_eq!(( 16).next_multiple_of(&-8), 16);
+ /// assert_eq!(( 23).next_multiple_of(&-8), 16);
+ /// assert_eq!((-16).next_multiple_of(& 8), -16);
+ /// assert_eq!((-23).next_multiple_of(& 8), -16);
+ /// assert_eq!((-16).next_multiple_of(&-8), -16);
+ /// assert_eq!((-23).next_multiple_of(&-8), -24);
+ /// ~~~
+ #[inline]
+ fn next_multiple_of(&self, other: &Self) -> Self
+ where
+ Self: Clone,
+ {
+ let m = self.mod_floor(other);
+ self.clone()
+ + if m.is_zero() {
+ Self::zero()
+ } else {
+ other.clone() - m
+ }
+ }
+
+ /// Rounds down to nearest multiple of argument.
+ ///
+ /// # Notes
+ ///
+ /// For signed types, `a.prev_multiple_of(b) = a.next_multiple_of(b.neg())`.
+ ///
+ /// # Examples
+ ///
+ /// ~~~
+ /// # use num_integer::Integer;
+ /// assert_eq!(( 16).prev_multiple_of(& 8), 16);
+ /// assert_eq!(( 23).prev_multiple_of(& 8), 16);
+ /// assert_eq!(( 16).prev_multiple_of(&-8), 16);
+ /// assert_eq!(( 23).prev_multiple_of(&-8), 24);
+ /// assert_eq!((-16).prev_multiple_of(& 8), -16);
+ /// assert_eq!((-23).prev_multiple_of(& 8), -24);
+ /// assert_eq!((-16).prev_multiple_of(&-8), -16);
+ /// assert_eq!((-23).prev_multiple_of(&-8), -16);
+ /// ~~~
+ #[inline]
+ fn prev_multiple_of(&self, other: &Self) -> Self
+ where
+ Self: Clone,
+ {
+ self.clone() - self.mod_floor(other)
+ }
+}
+
+/// Greatest common divisor and Bézout coefficients
+///
+/// ```no_build
+/// let e = isize::extended_gcd(a, b);
+/// assert_eq!(e.gcd, e.x*a + e.y*b);
+/// ```
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub struct ExtendedGcd<A> {
+ pub gcd: A,
+ pub x: A,
+ pub y: A,
+ _hidden: (),
}
/// Simultaneous integer division and modulus
pub fn div_mod_floor<T: Integer>(x: T, y: T) -> (T, T) {
x.div_mod_floor(&y)
}
+/// Ceiled integer division
+#[inline]
+pub fn div_ceil<T: Integer>(x: T, y: T) -> T {
+ x.div_ceil(&y)
+}
/// Calculates the Greatest Common Divisor (GCD) of the number and `other`. The
/// result is always positive.
x.lcm(&y)
}
+/// Calculates the Greatest Common Divisor (GCD) and
+/// Lowest Common Multiple (LCM) of the number and `other`.
+#[inline(always)]
+pub fn gcd_lcm<T: Integer>(x: T, y: T) -> (T, T) {
+ x.gcd_lcm(&y)
+}
+
macro_rules! impl_integer_for_isize {
- ($T:ty, $test_mod:ident) => (
+ ($T:ty, $test_mod:ident) => {
impl Integer for $T {
/// Floored integer division
#[inline]
fn div_floor(&self, other: &Self) -> Self {
// Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
// December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
- match self.div_rem(other) {
- (d, r) if (r > 0 && *other < 0)
- || (r < 0 && *other > 0) => d - 1,
- (d, _) => d,
+ let (d, r) = self.div_rem(other);
+ if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
+ d - 1
+ } else {
+ d
}
}
fn mod_floor(&self, other: &Self) -> Self {
// Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
// December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
- match *self % *other {
- r if (r > 0 && *other < 0)
- || (r < 0 && *other > 0) => r + *other,
- r => r,
+ let r = *self % *other;
+ if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
+ r + *other
+ } else {
+ r
}
}
fn div_mod_floor(&self, other: &Self) -> (Self, Self) {
// Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
// December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
- match self.div_rem(other) {
- (d, r) if (r > 0 && *other < 0)
- || (r < 0 && *other > 0) => (d - 1, r + *other),
- (d, r) => (d, r),
+ let (d, r) = self.div_rem(other);
+ if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
+ (d - 1, r + *other)
+ } else {
+ (d, r)
+ }
+ }
+
+ #[inline]
+ fn div_ceil(&self, other: &Self) -> Self {
+ let (d, r) = self.div_rem(other);
+ if (r > 0 && *other > 0) || (r < 0 && *other < 0) {
+ d + 1
+ } else {
+ d
}
}
// Use Stein's algorithm
let mut m = *self;
let mut n = *other;
- if m == 0 || n == 0 { return (m | n).abs() }
+ if m == 0 || n == 0 {
+ return (m | n).abs();
+ }
// find common factors of 2
let shift = (m | n).trailing_zeros();
// is positive for all numbers except gcd = abs(min value)
// The call to .abs() causes a panic in debug mode
if m == Self::min_value() || n == Self::min_value() {
- return (1 << shift).abs()
+ return (1 << shift).abs();
}
// guaranteed to be positive now, rest like unsigned algorithm
n = n.abs();
// divide n and m by 2 until odd
- // m inside loop
+ m >>= m.trailing_zeros();
n >>= n.trailing_zeros();
- while m != 0 {
- m >>= m.trailing_zeros();
- if n > m { mem::swap(&mut n, &mut m) }
- m -= n;
+ while m != n {
+ if m > n {
+ m -= n;
+ m >>= m.trailing_zeros();
+ } else {
+ n -= m;
+ n >>= n.trailing_zeros();
+ }
}
+ m << shift
+ }
- n << shift
+ #[inline]
+ fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self) {
+ let egcd = self.extended_gcd(other);
+ // should not have to recalculate abs
+ let lcm = if egcd.gcd.is_zero() {
+ Self::zero()
+ } else {
+ (*self * (*other / egcd.gcd)).abs()
+ };
+ (egcd, lcm)
}
/// Calculates the Lowest Common Multiple (LCM) of the number and
/// `other`.
#[inline]
fn lcm(&self, other: &Self) -> Self {
+ self.gcd_lcm(other).1
+ }
+
+ /// Calculates the Greatest Common Divisor (GCD) and
+ /// Lowest Common Multiple (LCM) of the number and `other`.
+ #[inline]
+ fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
+ if self.is_zero() && other.is_zero() {
+ return (Self::zero(), Self::zero());
+ }
+ let gcd = self.gcd(other);
// should not have to recalculate abs
- (*self * (*other / self.gcd(other))).abs()
+ let lcm = (*self * (*other / gcd)).abs();
+ (gcd, lcm)
}
/// Deprecated, use `is_multiple_of` instead.
/// Returns `true` if the number is divisible by `2`
#[inline]
- fn is_even(&self) -> bool { (*self) & 1 == 0 }
+ fn is_even(&self) -> bool {
+ (*self) & 1 == 0
+ }
/// Returns `true` if the number is not divisible by `2`
#[inline]
- fn is_odd(&self) -> bool { !self.is_even() }
+ fn is_odd(&self) -> bool {
+ !self.is_even()
+ }
/// Simultaneous truncated integer division and modulus.
#[inline]
#[cfg(test)]
mod $test_mod {
- use Integer;
use core::mem;
+ use Integer;
/// Checks that the division rule holds for:
///
/// - `d`: denominator (divisor)
/// - `qr`: quotient and remainder
#[cfg(test)]
- fn test_division_rule((n,d): ($T, $T), (q,r): ($T, $T)) {
+ fn test_division_rule((n, d): ($T, $T), (q, r): ($T, $T)) {
assert_eq!(d * q + r, n);
}
#[test]
fn test_div_rem() {
- fn test_nd_dr(nd: ($T,$T), qr: ($T,$T)) {
- let (n,d) = nd;
+ fn test_nd_dr(nd: ($T, $T), qr: ($T, $T)) {
+ let (n, d) = nd;
let separate_div_rem = (n / d, n % d);
let combined_div_rem = n.div_rem(&d);
test_division_rule(nd, combined_div_rem);
}
- test_nd_dr(( 8, 3), ( 2, 2));
- test_nd_dr(( 8, -3), (-2, 2));
- test_nd_dr((-8, 3), (-2, -2));
- test_nd_dr((-8, -3), ( 2, -2));
+ test_nd_dr((8, 3), (2, 2));
+ test_nd_dr((8, -3), (-2, 2));
+ test_nd_dr((-8, 3), (-2, -2));
+ test_nd_dr((-8, -3), (2, -2));
- test_nd_dr(( 1, 2), ( 0, 1));
- test_nd_dr(( 1, -2), ( 0, 1));
- test_nd_dr((-1, 2), ( 0, -1));
- test_nd_dr((-1, -2), ( 0, -1));
+ test_nd_dr((1, 2), (0, 1));
+ test_nd_dr((1, -2), (0, 1));
+ test_nd_dr((-1, 2), (0, -1));
+ test_nd_dr((-1, -2), (0, -1));
}
#[test]
fn test_div_mod_floor() {
- fn test_nd_dm(nd: ($T,$T), dm: ($T,$T)) {
- let (n,d) = nd;
+ fn test_nd_dm(nd: ($T, $T), dm: ($T, $T)) {
+ let (n, d) = nd;
let separate_div_mod_floor = (n.div_floor(&d), n.mod_floor(&d));
let combined_div_mod_floor = n.div_mod_floor(&d);
test_division_rule(nd, combined_div_mod_floor);
}
- test_nd_dm(( 8, 3), ( 2, 2));
- test_nd_dm(( 8, -3), (-3, -1));
- test_nd_dm((-8, 3), (-3, 1));
- test_nd_dm((-8, -3), ( 2, -2));
+ test_nd_dm((8, 3), (2, 2));
+ test_nd_dm((8, -3), (-3, -1));
+ test_nd_dm((-8, 3), (-3, 1));
+ test_nd_dm((-8, -3), (2, -2));
- test_nd_dm(( 1, 2), ( 0, 1));
- test_nd_dm(( 1, -2), (-1, -1));
- test_nd_dm((-1, 2), (-1, 1));
- test_nd_dm((-1, -2), ( 0, -1));
+ test_nd_dm((1, 2), (0, 1));
+ test_nd_dm((1, -2), (-1, -1));
+ test_nd_dm((-1, 2), (-1, 1));
+ test_nd_dm((-1, -2), (0, -1));
}
#[test]
// for i8
for i in -127..127 {
for j in -127..127 {
- assert_eq!(euclidean_gcd(i,j), i.gcd(&j));
+ assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
}
}
// FIXME: Use inclusive ranges for above loop when implemented
let i = 127;
for j in -127..127 {
- assert_eq!(euclidean_gcd(i,j), i.gcd(&j));
+ assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
}
assert_eq!(127.gcd(&127), 127);
}
assert_eq!((11 as $T).lcm(&5), 55 as $T);
}
+ #[test]
+ fn test_gcd_lcm() {
+ use core::iter::once;
+ for i in once(0)
+ .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
+ .chain(once(-128))
+ {
+ for j in once(0)
+ .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
+ .chain(once(-128))
+ {
+ assert_eq!(i.gcd_lcm(&j), (i.gcd(&j), i.lcm(&j)));
+ }
+ }
+ }
+
+ #[test]
+ fn test_extended_gcd_lcm() {
+ use core::fmt::Debug;
+ use traits::NumAssign;
+ use ExtendedGcd;
+
+ fn check<A: Copy + Debug + Integer + NumAssign>(a: A, b: A) {
+ let ExtendedGcd { gcd, x, y, .. } = a.extended_gcd(&b);
+ assert_eq!(gcd, x * a + y * b);
+ }
+
+ use core::iter::once;
+ for i in once(0)
+ .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
+ .chain(once(-128))
+ {
+ for j in once(0)
+ .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
+ .chain(once(-128))
+ {
+ check(i, j);
+ let (ExtendedGcd { gcd, .. }, lcm) = i.extended_gcd_lcm(&j);
+ assert_eq!((gcd, lcm), (i.gcd(&j), i.lcm(&j)));
+ }
+ }
+ }
+
#[test]
fn test_even() {
assert_eq!((-4 as $T).is_even(), true);
assert_eq!((4 as $T).is_odd(), false);
}
}
- )
+ };
}
impl_integer_for_isize!(i8, test_integer_i8);
impl_integer_for_isize!(i128, test_integer_i128);
macro_rules! impl_integer_for_usize {
- ($T:ty, $test_mod:ident) => (
+ ($T:ty, $test_mod:ident) => {
impl Integer for $T {
/// Unsigned integer division. Returns the same result as `div` (`/`).
#[inline]
*self % *other
}
+ #[inline]
+ fn div_ceil(&self, other: &Self) -> Self {
+ *self / *other + (0 != *self % *other) as Self
+ }
+
/// Calculates the Greatest Common Divisor (GCD) of the number and `other`
#[inline]
fn gcd(&self, other: &Self) -> Self {
// Use Stein's algorithm
let mut m = *self;
let mut n = *other;
- if m == 0 || n == 0 { return m | n }
+ if m == 0 || n == 0 {
+ return m | n;
+ }
// find common factors of 2
let shift = (m | n).trailing_zeros();
// divide n and m by 2 until odd
- // m inside loop
+ m >>= m.trailing_zeros();
n >>= n.trailing_zeros();
- while m != 0 {
- m >>= m.trailing_zeros();
- if n > m { mem::swap(&mut n, &mut m) }
- m -= n;
+ while m != n {
+ if m > n {
+ m -= n;
+ m >>= m.trailing_zeros();
+ } else {
+ n -= m;
+ n >>= n.trailing_zeros();
+ }
}
+ m << shift
+ }
- n << shift
+ #[inline]
+ fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self) {
+ let egcd = self.extended_gcd(other);
+ // should not have to recalculate abs
+ let lcm = if egcd.gcd.is_zero() {
+ Self::zero()
+ } else {
+ *self * (*other / egcd.gcd)
+ };
+ (egcd, lcm)
}
/// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
#[inline]
fn lcm(&self, other: &Self) -> Self {
- *self * (*other / self.gcd(other))
+ self.gcd_lcm(other).1
+ }
+
+ /// Calculates the Greatest Common Divisor (GCD) and
+ /// Lowest Common Multiple (LCM) of the number and `other`.
+ #[inline]
+ fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
+ if self.is_zero() && other.is_zero() {
+ return (Self::zero(), Self::zero());
+ }
+ let gcd = self.gcd(other);
+ let lcm = *self * (*other / gcd);
+ (gcd, lcm)
}
/// Deprecated, use `is_multiple_of` instead.
#[cfg(test)]
mod $test_mod {
- use Integer;
use core::mem;
+ use Integer;
#[test]
fn test_div_mod_floor() {
for i in 0..255 {
for j in 0..255 {
- assert_eq!(euclidean_gcd(i,j), i.gcd(&j));
+ assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
}
}
// FIXME: Use inclusive ranges for above loop when implemented
let i = 255;
for j in 0..255 {
- assert_eq!(euclidean_gcd(i,j), i.gcd(&j));
+ assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
}
assert_eq!(255.gcd(&255), 255);
}
assert_eq!((15 as $T).lcm(&17), 255 as $T);
}
+ #[test]
+ fn test_gcd_lcm() {
+ for i in (0..).take(256) {
+ for j in (0..).take(256) {
+ assert_eq!(i.gcd_lcm(&j), (i.gcd(&j), i.lcm(&j)));
+ }
+ }
+ }
+
#[test]
fn test_is_multiple_of() {
assert!((6 as $T).is_multiple_of(&(6 as $T)));
assert_eq!((4 as $T).is_odd(), false);
}
}
- )
+ };
}
impl_integer_for_usize!(u8, test_integer_u8);
}
impl<T> IterBinomial<T>
- where T: Integer,
+where
+ T: Integer,
{
/// For a given n, iterate over all binomial coefficients binomial(n, k), for k=0...n.
///
/// For larger n, `T` should be a bigint type.
pub fn new(n: T) -> IterBinomial<T> {
IterBinomial {
- k: T::zero(), a: T::one(), n: n
+ k: T::zero(),
+ a: T::one(),
+ n: n,
}
}
}
impl<T> Iterator for IterBinomial<T>
- where T: Integer + Clone
+where
+ T: Integer + Clone,
{
type Item = T;
multiply_and_divide(
self.a.clone(),
self.n.clone() - self.k.clone() + T::one(),
- self.k.clone()
+ self.k.clone(),
)
} else {
T::one()
fn multiply_and_divide<T: Integer + Clone>(r: T, a: T, b: T) -> T {
// See http://blog.plover.com/math/choose-2.html for the idea.
let g = gcd(r.clone(), b.clone());
- r/g.clone() * (a / (b/g))
+ r / g.clone() * (a / (b / g))
}
/// Calculate the binomial coefficient.
/// Calculate the multinomial coefficient.
pub fn multinomial<T: Integer + Clone>(k: &[T]) -> T
- where for<'a> T: Add<&'a T, Output = T>
+where
+ for<'a> T: Add<&'a T, Output = T>,
{
let mut r = T::one();
let mut p = T::zero();
#[test]
fn test_lcm_overflow() {
macro_rules! check {
- ($t:ty, $x:expr, $y:expr, $r:expr) => { {
+ ($t:ty, $x:expr, $y:expr, $r:expr) => {{
let x: $t = $x;
let y: $t = $y;
let o = x.checked_mul(y);
- assert!(o.is_none(),
- "sanity checking that {} input {} * {} overflows",
- stringify!($t), x, y);
+ assert!(
+ o.is_none(),
+ "sanity checking that {} input {} * {} overflows",
+ stringify!($t),
+ x,
+ y
+ );
assert_eq!(x.lcm(&y), $r);
assert_eq!(y.lcm(&x), $r);
- } }
+ }};
}
// Original bug (Issue #166)
#[test]
fn test_iter_binomial() {
macro_rules! check_simple {
- ($t:ty) => { {
+ ($t:ty) => {{
let n: $t = 3;
let expected = [1, 3, 3, 1];
for (b, &e) in IterBinomial::new(n).zip(&expected) {
assert_eq!(b, e);
}
- } }
+ }};
}
check_simple!(u8);
check_simple!(i64);
macro_rules! check_binomial {
- ($t:ty, $n:expr) => { {
+ ($t:ty, $n:expr) => {{
let n: $t = $n;
let mut k: $t = 0;
for b in IterBinomial::new(n) {
assert_eq!(b, binomial(n, k));
k += 1;
}
- } }
+ }};
}
// Check the largest n for which there is no overflow.
#[test]
fn test_binomial() {
macro_rules! check {
- ($t:ty, $x:expr, $y:expr, $r:expr) => { {
+ ($t:ty, $x:expr, $y:expr, $r:expr) => {{
let x: $t = $x;
let y: $t = $y;
let expected: $t = $r;
if y <= x {
assert_eq!(binomial(x, x - y), expected);
}
- } }
+ }};
}
check!(u8, 9, 4, 126);
check!(u8, 0, 0, 1);
#[test]
fn test_multinomial() {
macro_rules! check_binomial {
- ($t:ty, $k:expr) => { {
+ ($t:ty, $k:expr) => {{
let n: $t = $k.iter().fold(0, |acc, &x| acc + x);
let k: &[$t] = $k;
assert_eq!(k.len(), 2);
assert_eq!(multinomial(k), binomial(n, k[0]));
- } }
+ }};
}
check_binomial!(u8, &[4, 5]);
check_binomial!(i64, &[4, 10]);
macro_rules! check_multinomial {
- ($t:ty, $k:expr, $r:expr) => { {
+ ($t:ty, $k:expr, $r:expr) => {{
let k: &[$t] = $k;
let expected: $t = $r;
assert_eq!(multinomial(k), expected);
- } }
+ }};
}
check_multinomial!(u8, &[2, 1, 2], 30);
projects / cargo.git / blobdiff