Merging upstream version 1.72.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 0 insertions, 1812 deletions

diff --git a/vendor/num-integer/src/average.rs b/vendor/num-integer/src/average.rs
deleted file mode 100644
index 29cd11e3f..000000000
--- a/vendor/num-integer/src/average.rs
+++ /dev/null
@@ -1,78 +0,0 @@
-use core::ops::{BitAnd, BitOr, BitXor, Shr};
-use Integer;
-
-/// Provides methods to compute the average of two integers, without overflows.
-pub trait Average: Integer {
-    /// Returns the ceiling value of the average of `self` and `other`.
-    /// -- `⌈(self + other)/2⌉`
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use num_integer::Average;
-    ///
-    /// assert_eq!(( 3).average_ceil(&10),  7);
-    /// assert_eq!((-2).average_ceil(&-5), -3);
-    /// assert_eq!(( 4).average_ceil(& 4),  4);
-    ///
-    /// assert_eq!(u8::max_value().average_ceil(&2), 129);
-    /// assert_eq!(i8::min_value().average_ceil(&-1), -64);
-    /// assert_eq!(i8::min_value().average_ceil(&i8::max_value()), 0);
-    /// ```
-    ///
-    fn average_ceil(&self, other: &Self) -> Self;
-
-    /// Returns the floor value of the average of `self` and `other`.
-    /// -- `⌊(self + other)/2⌋`
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use num_integer::Average;
-    ///
-    /// assert_eq!(( 3).average_floor(&10),  6);
-    /// assert_eq!((-2).average_floor(&-5), -4);
-    /// assert_eq!(( 4).average_floor(& 4),  4);
-    ///
-    /// assert_eq!(u8::max_value().average_floor(&2), 128);
-    /// assert_eq!(i8::min_value().average_floor(&-1), -65);
-    /// assert_eq!(i8::min_value().average_floor(&i8::max_value()), -1);
-    /// ```
-    ///
-    fn average_floor(&self, other: &Self) -> Self;
-}
-
-impl<I> Average for I
-where
-    I: Integer + Shr<usize, Output = I>,
-    for<'a, 'b> &'a I:
-        BitAnd<&'b I, Output = I> + BitOr<&'b I, Output = I> + BitXor<&'b I, Output = I>,
-{
-    // The Henry Gordon Dietz implementation as shown in the Hacker's Delight,
-    // see http://aggregate.org/MAGIC/#Average%20of%20Integers
-
-    /// Returns the floor value of the average of `self` and `other`.
-    #[inline]
-    fn average_floor(&self, other: &I) -> I {
-        (self & other) + ((self ^ other) >> 1)
-    }
-
-    /// Returns the ceil value of the average of `self` and `other`.
-    #[inline]
-    fn average_ceil(&self, other: &I) -> I {
-        (self | other) - ((self ^ other) >> 1)
-    }
-}
-
-/// Returns the floor value of the average of `x` and `y` --
-/// see [Average::average_floor](trait.Average.html#tymethod.average_floor).
-#[inline]
-pub fn average_floor<T: Average>(x: T, y: T) -> T {
-    x.average_floor(&y)
-}
-/// Returns the ceiling value of the average of `x` and `y` --
-/// see [Average::average_ceil](trait.Average.html#tymethod.average_ceil).
-#[inline]
-pub fn average_ceil<T: Average>(x: T, y: T) -> T {
-    x.average_ceil(&y)
-}
diff --git a/vendor/num-integer/src/lib.rs b/vendor/num-integer/src/lib.rs
deleted file mode 100644
index 02819541b..000000000
--- a/vendor/num-integer/src/lib.rs
+++ /dev/null
@@ -1,1343 +0,0 @@
-// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! Integer trait and functions.
-//!
-//! ## Compatibility
-//!
-//! 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::mem;
-use core::ops::Add;
-
-use traits::{Num, Signed, Zero};
-
-mod roots;
-pub use roots::Roots;
-pub use roots::{cbrt, nth_root, sqrt};
-
-mod average;
-pub use average::Average;
-pub use average::{average_ceil, average_floor};
-
-pub trait Integer: Sized + Num + PartialOrd + Ord + Eq {
-    /// Floored integer division.
-    ///
-    /// # Examples
-    ///
-    /// ~~~
-    /// # use num_integer::Integer;
-    /// assert!(( 8).div_floor(& 3) ==  2);
-    /// assert!(( 8).div_floor(&-3) == -3);
-    /// assert!((-8).div_floor(& 3) == -3);
-    /// assert!((-8).div_floor(&-3) ==  2);
-    ///
-    /// assert!(( 1).div_floor(& 2) ==  0);
-    /// assert!(( 1).div_floor(&-2) == -1);
-    /// assert!((-1).div_floor(& 2) == -1);
-    /// assert!((-1).div_floor(&-2) ==  0);
-    /// ~~~
-    fn div_floor(&self, other: &Self) -> Self;
-
-    /// Floored integer modulo, satisfying:
-    ///
-    /// ~~~
-    /// # use num_integer::Integer;
-    /// # let n = 1; let d = 1;
-    /// assert!(n.div_floor(&d) * d + n.mod_floor(&d) == n)
-    /// ~~~
-    ///
-    /// # Examples
-    ///
-    /// ~~~
-    /// # use num_integer::Integer;
-    /// assert!(( 8).mod_floor(& 3) ==  2);
-    /// assert!(( 8).mod_floor(&-3) == -1);
-    /// assert!((-8).mod_floor(& 3) ==  1);
-    /// assert!((-8).mod_floor(&-3) == -2);
-    ///
-    /// assert!(( 1).mod_floor(& 2) ==  1);
-    /// assert!(( 1).mod_floor(&-2) == -1);
-    /// assert!((-1).mod_floor(& 2) ==  1);
-    /// assert!((-1).mod_floor(&-2) == -1);
-    /// ~~~
-    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!(6.gcd(&8), 2);
-    /// assert_eq!(7.gcd(&3), 1);
-    /// ~~~
-    fn gcd(&self, other: &Self) -> Self;
-
-    /// Lowest Common Multiple (LCM).
-    ///
-    /// # 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;
-
-    /// Returns `true` if `self` is a multiple of `other`.
-    ///
-    /// # Examples
-    ///
-    /// ~~~
-    /// # use num_integer::Integer;
-    /// assert_eq!(9.is_multiple_of(&3), true);
-    /// assert_eq!(3.is_multiple_of(&9), false);
-    /// ~~~
-    fn is_multiple_of(&self, other: &Self) -> bool;
-
-    /// Returns `true` if the number is even.
-    ///
-    /// # Examples
-    ///
-    /// ~~~
-    /// # use num_integer::Integer;
-    /// assert_eq!(3.is_even(), false);
-    /// assert_eq!(4.is_even(), true);
-    /// ~~~
-    fn is_even(&self) -> bool;
-
-    /// Returns `true` if the number is odd.
-    ///
-    /// # Examples
-    ///
-    /// ~~~
-    /// # use num_integer::Integer;
-    /// assert_eq!(3.is_odd(), true);
-    /// assert_eq!(4.is_odd(), false);
-    /// ~~~
-    fn is_odd(&self) -> bool;
-
-    /// Simultaneous truncated integer division and modulus.
-    /// Returns `(quotient, remainder)`.
-    ///
-    /// # Examples
-    ///
-    /// ~~~
-    /// # use num_integer::Integer;
-    /// assert_eq!(( 8).div_rem( &3), ( 2,  2));
-    /// assert_eq!(( 8).div_rem(&-3), (-2,  2));
-    /// assert_eq!((-8).div_rem( &3), (-2, -2));
-    /// assert_eq!((-8).div_rem(&-3), ( 2, -2));
-    ///
-    /// assert_eq!(( 1).div_rem( &2), ( 0,  1));
-    /// assert_eq!(( 1).div_rem(&-2), ( 0,  1));
-    /// assert_eq!((-1).div_rem( &2), ( 0, -1));
-    /// assert_eq!((-1).div_rem(&-2), ( 0, -1));
-    /// ~~~
-    fn div_rem(&self, other: &Self) -> (Self, Self);
-
-    /// Simultaneous floored integer division and modulus.
-    /// Returns `(quotient, remainder)`.
-    ///
-    /// # Examples
-    ///
-    /// ~~~
-    /// # use num_integer::Integer;
-    /// assert_eq!(( 8).div_mod_floor( &3), ( 2,  2));
-    /// assert_eq!(( 8).div_mod_floor(&-3), (-3, -1));
-    /// assert_eq!((-8).div_mod_floor( &3), (-3,  1));
-    /// assert_eq!((-8).div_mod_floor(&-3), ( 2, -2));
-    ///
-    /// assert_eq!(( 1).div_mod_floor( &2), ( 0,  1));
-    /// assert_eq!(( 1).div_mod_floor(&-2), (-1, -1));
-    /// assert_eq!((-1).div_mod_floor( &2), (-1,  1));
-    /// assert_eq!((-1).div_mod_floor(&-2), ( 0, -1));
-    /// ~~~
-    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
-#[inline]
-pub fn div_rem<T: Integer>(x: T, y: T) -> (T, T) {
-    x.div_rem(&y)
-}
-/// Floored integer division
-#[inline]
-pub fn div_floor<T: Integer>(x: T, y: T) -> T {
-    x.div_floor(&y)
-}
-/// Floored integer modulus
-#[inline]
-pub fn mod_floor<T: Integer>(x: T, y: T) -> T {
-    x.mod_floor(&y)
-}
-/// Simultaneous floored integer division and modulus
-#[inline]
-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.
-#[inline(always)]
-pub fn gcd<T: Integer>(x: T, y: T) -> T {
-    x.gcd(&y)
-}
-/// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
-#[inline(always)]
-pub fn lcm<T: Integer>(x: T, y: T) -> T {
-    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) => {
-        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)
-                let (d, r) = self.div_rem(other);
-                if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
-                    d - 1
-                } else {
-                    d
-                }
-            }
-
-            /// Floored integer modulo
-            #[inline]
-            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)
-                let r = *self % *other;
-                if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
-                    r + *other
-                } else {
-                    r
-                }
-            }
-
-            /// Calculates `div_floor` and `mod_floor` simultaneously
-            #[inline]
-            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)
-                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
-                }
-            }
-
-            /// Calculates the Greatest Common Divisor (GCD) of the number and
-            /// `other`. The result is always positive.
-            #[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).abs();
-                }
-
-                // find common factors of 2
-                let shift = (m | n).trailing_zeros();
-
-                // The algorithm needs positive numbers, but the minimum value
-                // can't be represented as a positive one.
-                // It's also a power of two, so the gcd can be
-                // calculated by bitshifting in that case
-
-                // Assuming two's complement, the number created by the shift
-                // 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();
-                }
-
-                // guaranteed to be positive now, rest like unsigned algorithm
-                m = m.abs();
-                n = n.abs();
-
-                // divide n and m by 2 until odd
-                m >>= m.trailing_zeros();
-                n >>= n.trailing_zeros();
-
-                while m != n {
-                    if m > n {
-                        m -= n;
-                        m >>= m.trailing_zeros();
-                    } else {
-                        n -= m;
-                        n >>= n.trailing_zeros();
-                    }
-                }
-                m << 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
-                let lcm = (*self * (*other / gcd)).abs();
-                (gcd, lcm)
-            }
-
-            /// Deprecated, use `is_multiple_of` instead.
-            #[inline]
-            fn divides(&self, other: &Self) -> bool {
-                self.is_multiple_of(other)
-            }
-
-            /// Returns `true` if the number is a multiple of `other`.
-            #[inline]
-            fn is_multiple_of(&self, other: &Self) -> bool {
-                *self % *other == 0
-            }
-
-            /// Returns `true` if the number is divisible by `2`
-            #[inline]
-            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()
-            }
-
-            /// Simultaneous truncated integer division and modulus.
-            #[inline]
-            fn div_rem(&self, other: &Self) -> (Self, Self) {
-                (*self / *other, *self % *other)
-            }
-        }
-
-        #[cfg(test)]
-        mod $test_mod {
-            use core::mem;
-            use Integer;
-
-            /// Checks that the division rule holds for:
-            ///
-            /// - `n`: numerator (dividend)
-            /// - `d`: denominator (divisor)
-            /// - `qr`: quotient and remainder
-            #[cfg(test)]
-            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;
-                    let separate_div_rem = (n / d, n % d);
-                    let combined_div_rem = n.div_rem(&d);
-
-                    assert_eq!(separate_div_rem, qr);
-                    assert_eq!(combined_div_rem, qr);
-
-                    test_division_rule(nd, separate_div_rem);
-                    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((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;
-                    let separate_div_mod_floor = (n.div_floor(&d), n.mod_floor(&d));
-                    let combined_div_mod_floor = n.div_mod_floor(&d);
-
-                    assert_eq!(separate_div_mod_floor, dm);
-                    assert_eq!(combined_div_mod_floor, dm);
-
-                    test_division_rule(nd, separate_div_mod_floor);
-                    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((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]
-            fn test_gcd() {
-                assert_eq!((10 as $T).gcd(&2), 2 as $T);
-                assert_eq!((10 as $T).gcd(&3), 1 as $T);
-                assert_eq!((0 as $T).gcd(&3), 3 as $T);
-                assert_eq!((3 as $T).gcd(&3), 3 as $T);
-                assert_eq!((56 as $T).gcd(&42), 14 as $T);
-                assert_eq!((3 as $T).gcd(&-3), 3 as $T);
-                assert_eq!((-6 as $T).gcd(&3), 3 as $T);
-                assert_eq!((-4 as $T).gcd(&-2), 2 as $T);
-            }
-
-            #[test]
-            fn test_gcd_cmp_with_euclidean() {
-                fn euclidean_gcd(mut m: $T, mut n: $T) -> $T {
-                    while m != 0 {
-                        mem::swap(&mut m, &mut n);
-                        m %= n;
-                    }
-
-                    n.abs()
-                }
-
-                // gcd(-128, b) = 128 is not representable as positive value
-                // for i8
-                for i in -127..127 {
-                    for j in -127..127 {
-                        assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
-                    }
-                }
-
-                // last value
-                // 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!(127.gcd(&127), 127);
-            }
-
-            #[test]
-            fn test_gcd_min_val() {
-                let min = <$T>::min_value();
-                let max = <$T>::max_value();
-                let max_pow2 = max / 2 + 1;
-                assert_eq!(min.gcd(&max), 1 as $T);
-                assert_eq!(max.gcd(&min), 1 as $T);
-                assert_eq!(min.gcd(&max_pow2), max_pow2);
-                assert_eq!(max_pow2.gcd(&min), max_pow2);
-                assert_eq!(min.gcd(&42), 2 as $T);
-                assert_eq!((42 as $T).gcd(&min), 2 as $T);
-            }
-
-            #[test]
-            #[should_panic]
-            fn test_gcd_min_val_min_val() {
-                let min = <$T>::min_value();
-                assert!(min.gcd(&min) >= 0);
-            }
-
-            #[test]
-            #[should_panic]
-            fn test_gcd_min_val_0() {
-                let min = <$T>::min_value();
-                assert!(min.gcd(&0) >= 0);
-            }
-
-            #[test]
-            #[should_panic]
-            fn test_gcd_0_min_val() {
-                let min = <$T>::min_value();
-                assert!((0 as $T).gcd(&min) >= 0);
-            }
-
-            #[test]
-            fn test_lcm() {
-                assert_eq!((1 as $T).lcm(&0), 0 as $T);
-                assert_eq!((0 as $T).lcm(&1), 0 as $T);
-                assert_eq!((1 as $T).lcm(&1), 1 as $T);
-                assert_eq!((-1 as $T).lcm(&1), 1 as $T);
-                assert_eq!((1 as $T).lcm(&-1), 1 as $T);
-                assert_eq!((-1 as $T).lcm(&-1), 1 as $T);
-                assert_eq!((8 as $T).lcm(&9), 72 as $T);
-                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!((-3 as $T).is_even(), false);
-                assert_eq!((-2 as $T).is_even(), true);
-                assert_eq!((-1 as $T).is_even(), false);
-                assert_eq!((0 as $T).is_even(), true);
-                assert_eq!((1 as $T).is_even(), false);
-                assert_eq!((2 as $T).is_even(), true);
-                assert_eq!((3 as $T).is_even(), false);
-                assert_eq!((4 as $T).is_even(), true);
-            }
-
-            #[test]
-            fn test_odd() {
-                assert_eq!((-4 as $T).is_odd(), false);
-                assert_eq!((-3 as $T).is_odd(), true);
-                assert_eq!((-2 as $T).is_odd(), false);
-                assert_eq!((-1 as $T).is_odd(), true);
-                assert_eq!((0 as $T).is_odd(), false);
-                assert_eq!((1 as $T).is_odd(), true);
-                assert_eq!((2 as $T).is_odd(), false);
-                assert_eq!((3 as $T).is_odd(), true);
-                assert_eq!((4 as $T).is_odd(), false);
-            }
-        }
-    };
-}
-
-impl_integer_for_isize!(i8, test_integer_i8);
-impl_integer_for_isize!(i16, test_integer_i16);
-impl_integer_for_isize!(i32, test_integer_i32);
-impl_integer_for_isize!(i64, test_integer_i64);
-impl_integer_for_isize!(isize, test_integer_isize);
-#[cfg(has_i128)]
-impl_integer_for_isize!(i128, test_integer_i128);
-
-macro_rules! impl_integer_for_usize {
-    ($T:ty, $test_mod:ident) => {
-        impl Integer for $T {
-            /// Unsigned integer division. Returns the same result as `div` (`/`).
-            #[inline]
-            fn div_floor(&self, other: &Self) -> Self {
-                *self / *other
-            }
-
-            /// Unsigned integer modulo operation. Returns the same result as `rem` (`%`).
-            #[inline]
-            fn mod_floor(&self, other: &Self) -> Self {
-                *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;
-                }
-
-                // find common factors of 2
-                let shift = (m | n).trailing_zeros();
-
-                // divide n and m by 2 until odd
-                m >>= m.trailing_zeros();
-                n >>= n.trailing_zeros();
-
-                while m != n {
-                    if m > n {
-                        m -= n;
-                        m >>= m.trailing_zeros();
-                    } else {
-                        n -= m;
-                        n >>= n.trailing_zeros();
-                    }
-                }
-                m << 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.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.
-            #[inline]
-            fn divides(&self, other: &Self) -> bool {
-                self.is_multiple_of(other)
-            }
-
-            /// Returns `true` if the number is a multiple of `other`.
-            #[inline]
-            fn is_multiple_of(&self, other: &Self) -> bool {
-                *self % *other == 0
-            }
-
-            /// Returns `true` if the number is divisible by `2`.
-            #[inline]
-            fn is_even(&self) -> bool {
-                *self % 2 == 0
-            }
-
-            /// Returns `true` if the number is not divisible by `2`.
-            #[inline]
-            fn is_odd(&self) -> bool {
-                !self.is_even()
-            }
-
-            /// Simultaneous truncated integer division and modulus.
-            #[inline]
-            fn div_rem(&self, other: &Self) -> (Self, Self) {
-                (*self / *other, *self % *other)
-            }
-        }
-
-        #[cfg(test)]
-        mod $test_mod {
-            use core::mem;
-            use Integer;
-
-            #[test]
-            fn test_div_mod_floor() {
-                assert_eq!((10 as $T).div_floor(&(3 as $T)), 3 as $T);
-                assert_eq!((10 as $T).mod_floor(&(3 as $T)), 1 as $T);
-                assert_eq!((10 as $T).div_mod_floor(&(3 as $T)), (3 as $T, 1 as $T));
-                assert_eq!((5 as $T).div_floor(&(5 as $T)), 1 as $T);
-                assert_eq!((5 as $T).mod_floor(&(5 as $T)), 0 as $T);
-                assert_eq!((5 as $T).div_mod_floor(&(5 as $T)), (1 as $T, 0 as $T));
-                assert_eq!((3 as $T).div_floor(&(7 as $T)), 0 as $T);
-                assert_eq!((3 as $T).mod_floor(&(7 as $T)), 3 as $T);
-                assert_eq!((3 as $T).div_mod_floor(&(7 as $T)), (0 as $T, 3 as $T));
-            }
-
-            #[test]
-            fn test_gcd() {
-                assert_eq!((10 as $T).gcd(&2), 2 as $T);
-                assert_eq!((10 as $T).gcd(&3), 1 as $T);
-                assert_eq!((0 as $T).gcd(&3), 3 as $T);
-                assert_eq!((3 as $T).gcd(&3), 3 as $T);
-                assert_eq!((56 as $T).gcd(&42), 14 as $T);
-            }
-
-            #[test]
-            fn test_gcd_cmp_with_euclidean() {
-                fn euclidean_gcd(mut m: $T, mut n: $T) -> $T {
-                    while m != 0 {
-                        mem::swap(&mut m, &mut n);
-                        m %= n;
-                    }
-                    n
-                }
-
-                for i in 0..255 {
-                    for j in 0..255 {
-                        assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
-                    }
-                }
-
-                // last value
-                // 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!(255.gcd(&255), 255);
-            }
-
-            #[test]
-            fn test_lcm() {
-                assert_eq!((1 as $T).lcm(&0), 0 as $T);
-                assert_eq!((0 as $T).lcm(&1), 0 as $T);
-                assert_eq!((1 as $T).lcm(&1), 1 as $T);
-                assert_eq!((8 as $T).lcm(&9), 72 as $T);
-                assert_eq!((11 as $T).lcm(&5), 55 as $T);
-                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!((6 as $T).is_multiple_of(&(3 as $T)));
-                assert!((6 as $T).is_multiple_of(&(1 as $T)));
-            }
-
-            #[test]
-            fn test_even() {
-                assert_eq!((0 as $T).is_even(), true);
-                assert_eq!((1 as $T).is_even(), false);
-                assert_eq!((2 as $T).is_even(), true);
-                assert_eq!((3 as $T).is_even(), false);
-                assert_eq!((4 as $T).is_even(), true);
-            }
-
-            #[test]
-            fn test_odd() {
-                assert_eq!((0 as $T).is_odd(), false);
-                assert_eq!((1 as $T).is_odd(), true);
-                assert_eq!((2 as $T).is_odd(), false);
-                assert_eq!((3 as $T).is_odd(), true);
-                assert_eq!((4 as $T).is_odd(), false);
-            }
-        }
-    };
-}
-
-impl_integer_for_usize!(u8, test_integer_u8);
-impl_integer_for_usize!(u16, test_integer_u16);
-impl_integer_for_usize!(u32, test_integer_u32);
-impl_integer_for_usize!(u64, test_integer_u64);
-impl_integer_for_usize!(usize, test_integer_usize);
-#[cfg(has_i128)]
-impl_integer_for_usize!(u128, test_integer_u128);
-
-/// An iterator over binomial coefficients.
-pub struct IterBinomial<T> {
-    a: T,
-    n: T,
-    k: T,
-}
-
-impl<T> IterBinomial<T>
-where
-    T: Integer,
-{
-    /// For a given n, iterate over all binomial coefficients binomial(n, k), for k=0...n.
-    ///
-    /// Note that this might overflow, depending on `T`. For the primitive
-    /// integer types, the following n are the largest ones for which there will
-    /// be no overflow:
-    ///
-    /// type | n
-    /// -----|---
-    /// u8   | 10
-    /// i8   |  9
-    /// u16  | 18
-    /// i16  | 17
-    /// u32  | 34
-    /// i32  | 33
-    /// u64  | 67
-    /// i64  | 66
-    ///
-    /// 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,
-        }
-    }
-}
-
-impl<T> Iterator for IterBinomial<T>
-where
-    T: Integer + Clone,
-{
-    type Item = T;
-
-    fn next(&mut self) -> Option<T> {
-        if self.k > self.n {
-            return None;
-        }
-        self.a = if !self.k.is_zero() {
-            multiply_and_divide(
-                self.a.clone(),
-                self.n.clone() - self.k.clone() + T::one(),
-                self.k.clone(),
-            )
-        } else {
-            T::one()
-        };
-        self.k = self.k.clone() + T::one();
-        Some(self.a.clone())
-    }
-}
-
-/// Calculate r * a / b, avoiding overflows and fractions.
-///
-/// Assumes that b divides r * a evenly.
-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))
-}
-
-/// Calculate the binomial coefficient.
-///
-/// Note that this might overflow, depending on `T`. For the primitive integer
-/// types, the following n are the largest ones possible such that there will
-/// be no overflow for any k:
-///
-/// type | n
-/// -----|---
-/// u8   | 10
-/// i8   |  9
-/// u16  | 18
-/// i16  | 17
-/// u32  | 34
-/// i32  | 33
-/// u64  | 67
-/// i64  | 66
-///
-/// For larger n, consider using a bigint type for `T`.
-pub fn binomial<T: Integer + Clone>(mut n: T, k: T) -> T {
-    // See http://blog.plover.com/math/choose.html for the idea.
-    if k > n {
-        return T::zero();
-    }
-    if k > n.clone() - k.clone() {
-        return binomial(n.clone(), n - k);
-    }
-    let mut r = T::one();
-    let mut d = T::one();
-    loop {
-        if d > k {
-            break;
-        }
-        r = multiply_and_divide(r, n.clone(), d.clone());
-        n = n - T::one();
-        d = d + T::one();
-    }
-    r
-}
-
-/// Calculate the multinomial coefficient.
-pub fn multinomial<T: Integer + Clone>(k: &[T]) -> T
-where
-    for<'a> T: Add<&'a T, Output = T>,
-{
-    let mut r = T::one();
-    let mut p = T::zero();
-    for i in k {
-        p = p + i;
-        r = r * binomial(p.clone(), i.clone());
-    }
-    r
-}
-
-#[test]
-fn test_lcm_overflow() {
-    macro_rules! check {
-        ($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_eq!(x.lcm(&y), $r);
-            assert_eq!(y.lcm(&x), $r);
-        }};
-    }
-
-    // Original bug (Issue #166)
-    check!(i64, 46656000000000000, 600, 46656000000000000);
-
-    check!(i8, 0x40, 0x04, 0x40);
-    check!(u8, 0x80, 0x02, 0x80);
-    check!(i16, 0x40_00, 0x04, 0x40_00);
-    check!(u16, 0x80_00, 0x02, 0x80_00);
-    check!(i32, 0x4000_0000, 0x04, 0x4000_0000);
-    check!(u32, 0x8000_0000, 0x02, 0x8000_0000);
-    check!(i64, 0x4000_0000_0000_0000, 0x04, 0x4000_0000_0000_0000);
-    check!(u64, 0x8000_0000_0000_0000, 0x02, 0x8000_0000_0000_0000);
-}
-
-#[test]
-fn test_iter_binomial() {
-    macro_rules! check_simple {
-        ($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!(i8);
-    check_simple!(u16);
-    check_simple!(i16);
-    check_simple!(u32);
-    check_simple!(i32);
-    check_simple!(u64);
-    check_simple!(i64);
-
-    macro_rules! check_binomial {
-        ($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.
-    check_binomial!(u8, 10);
-    check_binomial!(i8, 9);
-    check_binomial!(u16, 18);
-    check_binomial!(i16, 17);
-    check_binomial!(u32, 34);
-    check_binomial!(i32, 33);
-    check_binomial!(u64, 67);
-    check_binomial!(i64, 66);
-}
-
-#[test]
-fn test_binomial() {
-    macro_rules! check {
-        ($t:ty, $x:expr, $y:expr, $r:expr) => {{
-            let x: $t = $x;
-            let y: $t = $y;
-            let expected: $t = $r;
-            assert_eq!(binomial(x, y), expected);
-            if y <= x {
-                assert_eq!(binomial(x, x - y), expected);
-            }
-        }};
-    }
-    check!(u8, 9, 4, 126);
-    check!(u8, 0, 0, 1);
-    check!(u8, 2, 3, 0);
-
-    check!(i8, 9, 4, 126);
-    check!(i8, 0, 0, 1);
-    check!(i8, 2, 3, 0);
-
-    check!(u16, 100, 2, 4950);
-    check!(u16, 14, 4, 1001);
-    check!(u16, 0, 0, 1);
-    check!(u16, 2, 3, 0);
-
-    check!(i16, 100, 2, 4950);
-    check!(i16, 14, 4, 1001);
-    check!(i16, 0, 0, 1);
-    check!(i16, 2, 3, 0);
-
-    check!(u32, 100, 2, 4950);
-    check!(u32, 35, 11, 417225900);
-    check!(u32, 14, 4, 1001);
-    check!(u32, 0, 0, 1);
-    check!(u32, 2, 3, 0);
-
-    check!(i32, 100, 2, 4950);
-    check!(i32, 35, 11, 417225900);
-    check!(i32, 14, 4, 1001);
-    check!(i32, 0, 0, 1);
-    check!(i32, 2, 3, 0);
-
-    check!(u64, 100, 2, 4950);
-    check!(u64, 35, 11, 417225900);
-    check!(u64, 14, 4, 1001);
-    check!(u64, 0, 0, 1);
-    check!(u64, 2, 3, 0);
-
-    check!(i64, 100, 2, 4950);
-    check!(i64, 35, 11, 417225900);
-    check!(i64, 14, 4, 1001);
-    check!(i64, 0, 0, 1);
-    check!(i64, 2, 3, 0);
-}
-
-#[test]
-fn test_multinomial() {
-    macro_rules! check_binomial {
-        ($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!(i8, &[4, 5]);
-
-    check_binomial!(u16, &[2, 98]);
-    check_binomial!(u16, &[4, 10]);
-
-    check_binomial!(i16, &[2, 98]);
-    check_binomial!(i16, &[4, 10]);
-
-    check_binomial!(u32, &[2, 98]);
-    check_binomial!(u32, &[11, 24]);
-    check_binomial!(u32, &[4, 10]);
-
-    check_binomial!(i32, &[2, 98]);
-    check_binomial!(i32, &[11, 24]);
-    check_binomial!(i32, &[4, 10]);
-
-    check_binomial!(u64, &[2, 98]);
-    check_binomial!(u64, &[11, 24]);
-    check_binomial!(u64, &[4, 10]);
-
-    check_binomial!(i64, &[2, 98]);
-    check_binomial!(i64, &[11, 24]);
-    check_binomial!(i64, &[4, 10]);
-
-    macro_rules! check_multinomial {
-        ($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);
-    check_multinomial!(u8, &[2, 3, 0], 10);
-
-    check_multinomial!(i8, &[2, 1, 2], 30);
-    check_multinomial!(i8, &[2, 3, 0], 10);
-
-    check_multinomial!(u16, &[2, 1, 2], 30);
-    check_multinomial!(u16, &[2, 3, 0], 10);
-
-    check_multinomial!(i16, &[2, 1, 2], 30);
-    check_multinomial!(i16, &[2, 3, 0], 10);
-
-    check_multinomial!(u32, &[2, 1, 2], 30);
-    check_multinomial!(u32, &[2, 3, 0], 10);
-
-    check_multinomial!(i32, &[2, 1, 2], 30);
-    check_multinomial!(i32, &[2, 3, 0], 10);
-
-    check_multinomial!(u64, &[2, 1, 2], 30);
-    check_multinomial!(u64, &[2, 3, 0], 10);
-
-    check_multinomial!(i64, &[2, 1, 2], 30);
-    check_multinomial!(i64, &[2, 3, 0], 10);
-
-    check_multinomial!(u64, &[], 1);
-    check_multinomial!(u64, &[0], 1);
-    check_multinomial!(u64, &[12345], 1);
-}
diff --git a/vendor/num-integer/src/roots.rs b/vendor/num-integer/src/roots.rs
deleted file mode 100644
index a9eec1a93..000000000
--- a/vendor/num-integer/src/roots.rs
+++ /dev/null
@@ -1,391 +0,0 @@
-use core;
-use core::mem;
-use traits::checked_pow;
-use traits::PrimInt;
-use Integer;
-
-/// Provides methods to compute an integer's square root, cube root,
-/// and arbitrary `n`th root.
-pub trait Roots: Integer {
-    /// Returns the truncated principal `n`th root of an integer
-    /// -- `if x >= 0 { ⌊ⁿ√x⌋ } else { ⌈ⁿ√x⌉ }`
-    ///
-    /// This is solving for `r` in `rⁿ = x`, rounding toward zero.
-    /// If `x` is positive, the result will satisfy `rⁿ ≤ x < (r+1)ⁿ`.
-    /// If `x` is negative and `n` is odd, then `(r-1)ⁿ < x ≤ rⁿ`.
-    ///
-    /// # Panics
-    ///
-    /// Panics if `n` is zero:
-    ///
-    /// ```should_panic
-    /// # use num_integer::Roots;
-    /// println!("can't compute ⁰√x : {}", 123.nth_root(0));
-    /// ```
-    ///
-    /// or if `n` is even and `self` is negative:
-    ///
-    /// ```should_panic
-    /// # use num_integer::Roots;
-    /// println!("no imaginary numbers... {}", (-1).nth_root(10));
-    /// ```
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use num_integer::Roots;
-    ///
-    /// let x: i32 = 12345;
-    /// assert_eq!(x.nth_root(1), x);
-    /// assert_eq!(x.nth_root(2), x.sqrt());
-    /// assert_eq!(x.nth_root(3), x.cbrt());
-    /// assert_eq!(x.nth_root(4), 10);
-    /// assert_eq!(x.nth_root(13), 2);
-    /// assert_eq!(x.nth_root(14), 1);
-    /// assert_eq!(x.nth_root(std::u32::MAX), 1);
-    ///
-    /// assert_eq!(std::i32::MAX.nth_root(30), 2);
-    /// assert_eq!(std::i32::MAX.nth_root(31), 1);
-    /// assert_eq!(std::i32::MIN.nth_root(31), -2);
-    /// assert_eq!((std::i32::MIN + 1).nth_root(31), -1);
-    ///
-    /// assert_eq!(std::u32::MAX.nth_root(31), 2);
-    /// assert_eq!(std::u32::MAX.nth_root(32), 1);
-    /// ```
-    fn nth_root(&self, n: u32) -> Self;
-
-    /// Returns the truncated principal square root of an integer -- `⌊√x⌋`
-    ///
-    /// This is solving for `r` in `r² = x`, rounding toward zero.
-    /// The result will satisfy `r² ≤ x < (r+1)²`.
-    ///
-    /// # Panics
-    ///
-    /// Panics if `self` is less than zero:
-    ///
-    /// ```should_panic
-    /// # use num_integer::Roots;
-    /// println!("no imaginary numbers... {}", (-1).sqrt());
-    /// ```
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use num_integer::Roots;
-    ///
-    /// let x: i32 = 12345;
-    /// assert_eq!((x * x).sqrt(), x);
-    /// assert_eq!((x * x + 1).sqrt(), x);
-    /// assert_eq!((x * x - 1).sqrt(), x - 1);
-    /// ```
-    #[inline]
-    fn sqrt(&self) -> Self {
-        self.nth_root(2)
-    }
-
-    /// Returns the truncated principal cube root of an integer --
-    /// `if x >= 0 { ⌊∛x⌋ } else { ⌈∛x⌉ }`
-    ///
-    /// This is solving for `r` in `r³ = x`, rounding toward zero.
-    /// If `x` is positive, the result will satisfy `r³ ≤ x < (r+1)³`.
-    /// If `x` is negative, then `(r-1)³ < x ≤ r³`.
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use num_integer::Roots;
-    ///
-    /// let x: i32 = 1234;
-    /// assert_eq!((x * x * x).cbrt(), x);
-    /// assert_eq!((x * x * x + 1).cbrt(), x);
-    /// assert_eq!((x * x * x - 1).cbrt(), x - 1);
-    ///
-    /// assert_eq!((-(x * x * x)).cbrt(), -x);
-    /// assert_eq!((-(x * x * x + 1)).cbrt(), -x);
-    /// assert_eq!((-(x * x * x - 1)).cbrt(), -(x - 1));
-    /// ```
-    #[inline]
-    fn cbrt(&self) -> Self {
-        self.nth_root(3)
-    }
-}
-
-/// Returns the truncated principal square root of an integer --
-/// see [Roots::sqrt](trait.Roots.html#method.sqrt).
-#[inline]
-pub fn sqrt<T: Roots>(x: T) -> T {
-    x.sqrt()
-}
-
-/// Returns the truncated principal cube root of an integer --
-/// see [Roots::cbrt](trait.Roots.html#method.cbrt).
-#[inline]
-pub fn cbrt<T: Roots>(x: T) -> T {
-    x.cbrt()
-}
-
-/// Returns the truncated principal `n`th root of an integer --
-/// see [Roots::nth_root](trait.Roots.html#tymethod.nth_root).
-#[inline]
-pub fn nth_root<T: Roots>(x: T, n: u32) -> T {
-    x.nth_root(n)
-}
-
-macro_rules! signed_roots {
-    ($T:ty, $U:ty) => {
-        impl Roots for $T {
-            #[inline]
-            fn nth_root(&self, n: u32) -> Self {
-                if *self >= 0 {
-                    (*self as $U).nth_root(n) as Self
-                } else {
-                    assert!(n.is_odd(), "even roots of a negative are imaginary");
-                    -((self.wrapping_neg() as $U).nth_root(n) as Self)
-                }
-            }
-
-            #[inline]
-            fn sqrt(&self) -> Self {
-                assert!(*self >= 0, "the square root of a negative is imaginary");
-                (*self as $U).sqrt() as Self
-            }
-
-            #[inline]
-            fn cbrt(&self) -> Self {
-                if *self >= 0 {
-                    (*self as $U).cbrt() as Self
-                } else {
-                    -((self.wrapping_neg() as $U).cbrt() as Self)
-                }
-            }
-        }
-    };
-}
-
-signed_roots!(i8, u8);
-signed_roots!(i16, u16);
-signed_roots!(i32, u32);
-signed_roots!(i64, u64);
-#[cfg(has_i128)]
-signed_roots!(i128, u128);
-signed_roots!(isize, usize);
-
-#[inline]
-fn fixpoint<T, F>(mut x: T, f: F) -> T
-where
-    T: Integer + Copy,
-    F: Fn(T) -> T,
-{
-    let mut xn = f(x);
-    while x < xn {
-        x = xn;
-        xn = f(x);
-    }
-    while x > xn {
-        x = xn;
-        xn = f(x);
-    }
-    x
-}
-
-#[inline]
-fn bits<T>() -> u32 {
-    8 * mem::size_of::<T>() as u32
-}
-
-#[inline]
-fn log2<T: PrimInt>(x: T) -> u32 {
-    debug_assert!(x > T::zero());
-    bits::<T>() - 1 - x.leading_zeros()
-}
-
-macro_rules! unsigned_roots {
-    ($T:ident) => {
-        impl Roots for $T {
-            #[inline]
-            fn nth_root(&self, n: u32) -> Self {
-                fn go(a: $T, n: u32) -> $T {
-                    // Specialize small roots
-                    match n {
-                        0 => panic!("can't find a root of degree 0!"),
-                        1 => return a,
-                        2 => return a.sqrt(),
-                        3 => return a.cbrt(),
-                        _ => (),
-                    }
-
-                    // The root of values less than 2ⁿ can only be 0 or 1.
-                    if bits::<$T>() <= n || a < (1 << n) {
-                        return (a > 0) as $T;
-                    }
-
-                    if bits::<$T>() > 64 {
-                        // 128-bit division is slow, so do a bitwise `nth_root` until it's small enough.
-                        return if a <= core::u64::MAX as $T {
-                            (a as u64).nth_root(n) as $T
-                        } else {
-                            let lo = (a >> n).nth_root(n) << 1;
-                            let hi = lo + 1;
-                            // 128-bit `checked_mul` also involves division, but we can't always
-                            // compute `hiⁿ` without risking overflow.  Try to avoid it though...
-                            if hi.next_power_of_two().trailing_zeros() * n >= bits::<$T>() {
-                                match checked_pow(hi, n as usize) {
-                                    Some(x) if x <= a => hi,
-                                    _ => lo,
-                                }
-                            } else {
-                                if hi.pow(n) <= a {
-                                    hi
-                                } else {
-                                    lo
-                                }
-                            }
-                        };
-                    }
-
-                    #[cfg(feature = "std")]
-                    #[inline]
-                    fn guess(x: $T, n: u32) -> $T {
-                        // for smaller inputs, `f64` doesn't justify its cost.
-                        if bits::<$T>() <= 32 || x <= core::u32::MAX as $T {
-                            1 << ((log2(x) + n - 1) / n)
-                        } else {
-                            ((x as f64).ln() / f64::from(n)).exp() as $T
-                        }
-                    }
-
-                    #[cfg(not(feature = "std"))]
-                    #[inline]
-                    fn guess(x: $T, n: u32) -> $T {
-                        1 << ((log2(x) + n - 1) / n)
-                    }
-
-                    // https://en.wikipedia.org/wiki/Nth_root_algorithm
-                    let n1 = n - 1;
-                    let next = |x: $T| {
-                        let y = match checked_pow(x, n1 as usize) {
-                            Some(ax) => a / ax,
-                            None => 0,
-                        };
-                        (y + x * n1 as $T) / n as $T
-                    };
-                    fixpoint(guess(a, n), next)
-                }
-                go(*self, n)
-            }
-
-            #[inline]
-            fn sqrt(&self) -> Self {
-                fn go(a: $T) -> $T {
-                    if bits::<$T>() > 64 {
-                        // 128-bit division is slow, so do a bitwise `sqrt` until it's small enough.
-                        return if a <= core::u64::MAX as $T {
-                            (a as u64).sqrt() as $T
-                        } else {
-                            let lo = (a >> 2u32).sqrt() << 1;
-                            let hi = lo + 1;
-                            if hi * hi <= a {
-                                hi
-                            } else {
-                                lo
-                            }
-                        };
-                    }
-
-                    if a < 4 {
-                        return (a > 0) as $T;
-                    }
-
-                    #[cfg(feature = "std")]
-                    #[inline]
-                    fn guess(x: $T) -> $T {
-                        (x as f64).sqrt() as $T
-                    }
-
-                    #[cfg(not(feature = "std"))]
-                    #[inline]
-                    fn guess(x: $T) -> $T {
-                        1 << ((log2(x) + 1) / 2)
-                    }
-
-                    // https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
-                    let next = |x: $T| (a / x + x) >> 1;
-                    fixpoint(guess(a), next)
-                }
-                go(*self)
-            }
-
-            #[inline]
-            fn cbrt(&self) -> Self {
-                fn go(a: $T) -> $T {
-                    if bits::<$T>() > 64 {
-                        // 128-bit division is slow, so do a bitwise `cbrt` until it's small enough.
-                        return if a <= core::u64::MAX as $T {
-                            (a as u64).cbrt() as $T
-                        } else {
-                            let lo = (a >> 3u32).cbrt() << 1;
-                            let hi = lo + 1;
-                            if hi * hi * hi <= a {
-                                hi
-                            } else {
-                                lo
-                            }
-                        };
-                    }
-
-                    if bits::<$T>() <= 32 {
-                        // Implementation based on Hacker's Delight `icbrt2`
-                        let mut x = a;
-                        let mut y2 = 0;
-                        let mut y = 0;
-                        let smax = bits::<$T>() / 3;
-                        for s in (0..smax + 1).rev() {
-                            let s = s * 3;
-                            y2 *= 4;
-                            y *= 2;
-                            let b = 3 * (y2 + y) + 1;
-                            if x >> s >= b {
-                                x -= b << s;
-                                y2 += 2 * y + 1;
-                                y += 1;
-                            }
-                        }
-                        return y;
-                    }
-
-                    if a < 8 {
-                        return (a > 0) as $T;
-                    }
-                    if a <= core::u32::MAX as $T {
-                        return (a as u32).cbrt() as $T;
-                    }
-
-                    #[cfg(feature = "std")]
-                    #[inline]
-                    fn guess(x: $T) -> $T {
-                        (x as f64).cbrt() as $T
-                    }
-
-                    #[cfg(not(feature = "std"))]
-                    #[inline]
-                    fn guess(x: $T) -> $T {
-                        1 << ((log2(x) + 2) / 3)
-                    }
-
-                    // https://en.wikipedia.org/wiki/Cube_root#Numerical_methods
-                    let next = |x: $T| (a / (x * x) + x * 2) / 3;
-                    fixpoint(guess(a), next)
-                }
-                go(*self)
-            }
-        }
-    };
-}
-
-unsigned_roots!(u8);
-unsigned_roots!(u16);
-unsigned_roots!(u32);
-unsigned_roots!(u64);
-#[cfg(has_i128)]
-unsigned_roots!(u128);
-unsigned_roots!(usize);