num_integer/
lib.rs

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//! Integer trait and functions.
12//!
13//! ## Compatibility
14//!
15//! The `num-integer` crate is tested for rustc 1.31 and greater.
16
17#![doc(html_root_url = "https://docs.rs/num-integer/0.1")]
18#![no_std]
19
20use core::mem;
21use core::ops::Add;
22
23use num_traits::{Num, Signed, Zero};
24
25mod roots;
26pub use crate::roots::Roots;
27pub use crate::roots::{cbrt, nth_root, sqrt};
28
29mod average;
30pub use crate::average::Average;
31pub use crate::average::{average_ceil, average_floor};
32
33pub trait Integer: Sized + Num + PartialOrd + Ord + Eq {
34    /// Floored integer division.
35    ///
36    /// # Examples
37    ///
38    /// ~~~
39    /// # use num_integer::Integer;
40    /// assert!(( 8).div_floor(& 3) ==  2);
41    /// assert!(( 8).div_floor(&-3) == -3);
42    /// assert!((-8).div_floor(& 3) == -3);
43    /// assert!((-8).div_floor(&-3) ==  2);
44    ///
45    /// assert!(( 1).div_floor(& 2) ==  0);
46    /// assert!(( 1).div_floor(&-2) == -1);
47    /// assert!((-1).div_floor(& 2) == -1);
48    /// assert!((-1).div_floor(&-2) ==  0);
49    /// ~~~
50    fn div_floor(&self, other: &Self) -> Self;
51
52    /// Floored integer modulo, satisfying:
53    ///
54    /// ~~~
55    /// # use num_integer::Integer;
56    /// # let n = 1; let d = 1;
57    /// assert!(n.div_floor(&d) * d + n.mod_floor(&d) == n)
58    /// ~~~
59    ///
60    /// # Examples
61    ///
62    /// ~~~
63    /// # use num_integer::Integer;
64    /// assert!(( 8).mod_floor(& 3) ==  2);
65    /// assert!(( 8).mod_floor(&-3) == -1);
66    /// assert!((-8).mod_floor(& 3) ==  1);
67    /// assert!((-8).mod_floor(&-3) == -2);
68    ///
69    /// assert!(( 1).mod_floor(& 2) ==  1);
70    /// assert!(( 1).mod_floor(&-2) == -1);
71    /// assert!((-1).mod_floor(& 2) ==  1);
72    /// assert!((-1).mod_floor(&-2) == -1);
73    /// ~~~
74    fn mod_floor(&self, other: &Self) -> Self;
75
76    /// Ceiled integer division.
77    ///
78    /// # Examples
79    ///
80    /// ~~~
81    /// # use num_integer::Integer;
82    /// assert_eq!(( 8).div_ceil( &3),  3);
83    /// assert_eq!(( 8).div_ceil(&-3), -2);
84    /// assert_eq!((-8).div_ceil( &3), -2);
85    /// assert_eq!((-8).div_ceil(&-3),  3);
86    ///
87    /// assert_eq!(( 1).div_ceil( &2), 1);
88    /// assert_eq!(( 1).div_ceil(&-2), 0);
89    /// assert_eq!((-1).div_ceil( &2), 0);
90    /// assert_eq!((-1).div_ceil(&-2), 1);
91    /// ~~~
92    fn div_ceil(&self, other: &Self) -> Self {
93        let (q, r) = self.div_mod_floor(other);
94        if r.is_zero() {
95            q
96        } else {
97            q + Self::one()
98        }
99    }
100
101    /// Greatest Common Divisor (GCD).
102    ///
103    /// The result should always be non-negative.
104    ///
105    /// # Examples
106    ///
107    /// ~~~
108    /// # use num_integer::Integer;
109    /// assert_eq!(6.gcd(&8), 2);
110    /// assert_eq!(7.gcd(&3), 1);
111    /// ~~~
112    fn gcd(&self, other: &Self) -> Self;
113
114    /// Lowest Common Multiple (LCM).
115    ///
116    /// # Examples
117    ///
118    /// ~~~
119    /// # use num_integer::Integer;
120    /// assert_eq!(7.lcm(&3), 21);
121    /// assert_eq!(2.lcm(&4), 4);
122    /// assert_eq!(0.lcm(&0), 0);
123    /// ~~~
124    fn lcm(&self, other: &Self) -> Self;
125
126    /// Greatest Common Divisor (GCD) and
127    /// Lowest Common Multiple (LCM) together.
128    ///
129    /// Potentially more efficient than calling `gcd` and `lcm`
130    /// individually for identical inputs.
131    ///
132    /// # Examples
133    ///
134    /// ~~~
135    /// # use num_integer::Integer;
136    /// assert_eq!(10.gcd_lcm(&4), (2, 20));
137    /// assert_eq!(8.gcd_lcm(&9), (1, 72));
138    /// ~~~
139    #[inline]
140    fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
141        (self.gcd(other), self.lcm(other))
142    }
143
144    /// Greatest common divisor and Bézout coefficients.
145    ///
146    /// # Examples
147    ///
148    /// ~~~
149    /// # fn main() {
150    /// # use num_integer::{ExtendedGcd, Integer};
151    /// # use num_traits::NumAssign;
152    /// fn check<A: Copy + Integer + NumAssign>(a: A, b: A) -> bool {
153    ///     let ExtendedGcd { gcd, x, y, .. } = a.extended_gcd(&b);
154    ///     gcd == x * a + y * b
155    /// }
156    /// assert!(check(10isize, 4isize));
157    /// assert!(check(8isize,  9isize));
158    /// # }
159    /// ~~~
160    #[inline]
161    fn extended_gcd(&self, other: &Self) -> ExtendedGcd<Self>
162    where
163        Self: Clone,
164    {
165        let mut s = (Self::zero(), Self::one());
166        let mut t = (Self::one(), Self::zero());
167        let mut r = (other.clone(), self.clone());
168
169        while !r.0.is_zero() {
170            let q = r.1.clone() / r.0.clone();
171            let f = |mut r: (Self, Self)| {
172                mem::swap(&mut r.0, &mut r.1);
173                r.0 = r.0 - q.clone() * r.1.clone();
174                r
175            };
176            r = f(r);
177            s = f(s);
178            t = f(t);
179        }
180
181        if r.1 >= Self::zero() {
182            ExtendedGcd {
183                gcd: r.1,
184                x: s.1,
185                y: t.1,
186            }
187        } else {
188            ExtendedGcd {
189                gcd: Self::zero() - r.1,
190                x: Self::zero() - s.1,
191                y: Self::zero() - t.1,
192            }
193        }
194    }
195
196    /// Greatest common divisor, least common multiple, and Bézout coefficients.
197    #[inline]
198    fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self)
199    where
200        Self: Clone + Signed,
201    {
202        (self.extended_gcd(other), self.lcm(other))
203    }
204
205    /// Deprecated, use `is_multiple_of` instead.
206    #[deprecated(note = "Please use is_multiple_of instead")]
207    #[inline]
208    fn divides(&self, other: &Self) -> bool {
209        self.is_multiple_of(other)
210    }
211
212    /// Returns `true` if `self` is a multiple of `other`.
213    ///
214    /// # Examples
215    ///
216    /// ~~~
217    /// # use num_integer::Integer;
218    /// assert_eq!(9.is_multiple_of(&3), true);
219    /// assert_eq!(3.is_multiple_of(&9), false);
220    /// ~~~
221    fn is_multiple_of(&self, other: &Self) -> bool;
222
223    /// Returns `true` if the number is even.
224    ///
225    /// # Examples
226    ///
227    /// ~~~
228    /// # use num_integer::Integer;
229    /// assert_eq!(3.is_even(), false);
230    /// assert_eq!(4.is_even(), true);
231    /// ~~~
232    fn is_even(&self) -> bool;
233
234    /// Returns `true` if the number is odd.
235    ///
236    /// # Examples
237    ///
238    /// ~~~
239    /// # use num_integer::Integer;
240    /// assert_eq!(3.is_odd(), true);
241    /// assert_eq!(4.is_odd(), false);
242    /// ~~~
243    fn is_odd(&self) -> bool;
244
245    /// Simultaneous truncated integer division and modulus.
246    /// Returns `(quotient, remainder)`.
247    ///
248    /// # Examples
249    ///
250    /// ~~~
251    /// # use num_integer::Integer;
252    /// assert_eq!(( 8).div_rem( &3), ( 2,  2));
253    /// assert_eq!(( 8).div_rem(&-3), (-2,  2));
254    /// assert_eq!((-8).div_rem( &3), (-2, -2));
255    /// assert_eq!((-8).div_rem(&-3), ( 2, -2));
256    ///
257    /// assert_eq!(( 1).div_rem( &2), ( 0,  1));
258    /// assert_eq!(( 1).div_rem(&-2), ( 0,  1));
259    /// assert_eq!((-1).div_rem( &2), ( 0, -1));
260    /// assert_eq!((-1).div_rem(&-2), ( 0, -1));
261    /// ~~~
262    fn div_rem(&self, other: &Self) -> (Self, Self);
263
264    /// Simultaneous floored integer division and modulus.
265    /// Returns `(quotient, remainder)`.
266    ///
267    /// # Examples
268    ///
269    /// ~~~
270    /// # use num_integer::Integer;
271    /// assert_eq!(( 8).div_mod_floor( &3), ( 2,  2));
272    /// assert_eq!(( 8).div_mod_floor(&-3), (-3, -1));
273    /// assert_eq!((-8).div_mod_floor( &3), (-3,  1));
274    /// assert_eq!((-8).div_mod_floor(&-3), ( 2, -2));
275    ///
276    /// assert_eq!(( 1).div_mod_floor( &2), ( 0,  1));
277    /// assert_eq!(( 1).div_mod_floor(&-2), (-1, -1));
278    /// assert_eq!((-1).div_mod_floor( &2), (-1,  1));
279    /// assert_eq!((-1).div_mod_floor(&-2), ( 0, -1));
280    /// ~~~
281    fn div_mod_floor(&self, other: &Self) -> (Self, Self) {
282        (self.div_floor(other), self.mod_floor(other))
283    }
284
285    /// Rounds up to nearest multiple of argument.
286    ///
287    /// # Notes
288    ///
289    /// For signed types, `a.next_multiple_of(b) = a.prev_multiple_of(b.neg())`.
290    ///
291    /// # Examples
292    ///
293    /// ~~~
294    /// # use num_integer::Integer;
295    /// assert_eq!(( 16).next_multiple_of(& 8),  16);
296    /// assert_eq!(( 23).next_multiple_of(& 8),  24);
297    /// assert_eq!(( 16).next_multiple_of(&-8),  16);
298    /// assert_eq!(( 23).next_multiple_of(&-8),  16);
299    /// assert_eq!((-16).next_multiple_of(& 8), -16);
300    /// assert_eq!((-23).next_multiple_of(& 8), -16);
301    /// assert_eq!((-16).next_multiple_of(&-8), -16);
302    /// assert_eq!((-23).next_multiple_of(&-8), -24);
303    /// ~~~
304    #[inline]
305    fn next_multiple_of(&self, other: &Self) -> Self
306    where
307        Self: Clone,
308    {
309        let m = self.mod_floor(other);
310        self.clone()
311            + if m.is_zero() {
312                Self::zero()
313            } else {
314                other.clone() - m
315            }
316    }
317
318    /// Rounds down to nearest multiple of argument.
319    ///
320    /// # Notes
321    ///
322    /// For signed types, `a.prev_multiple_of(b) = a.next_multiple_of(b.neg())`.
323    ///
324    /// # Examples
325    ///
326    /// ~~~
327    /// # use num_integer::Integer;
328    /// assert_eq!(( 16).prev_multiple_of(& 8),  16);
329    /// assert_eq!(( 23).prev_multiple_of(& 8),  16);
330    /// assert_eq!(( 16).prev_multiple_of(&-8),  16);
331    /// assert_eq!(( 23).prev_multiple_of(&-8),  24);
332    /// assert_eq!((-16).prev_multiple_of(& 8), -16);
333    /// assert_eq!((-23).prev_multiple_of(& 8), -24);
334    /// assert_eq!((-16).prev_multiple_of(&-8), -16);
335    /// assert_eq!((-23).prev_multiple_of(&-8), -16);
336    /// ~~~
337    #[inline]
338    fn prev_multiple_of(&self, other: &Self) -> Self
339    where
340        Self: Clone,
341    {
342        self.clone() - self.mod_floor(other)
343    }
344
345    /// Decrements self by one.
346    ///
347    /// # Examples
348    ///
349    /// ~~~
350    /// # use num_integer::Integer;
351    /// let mut x: i32 = 43;
352    /// x.dec();
353    /// assert_eq!(x, 42);
354    /// ~~~
355    fn dec(&mut self)
356    where
357        Self: Clone,
358    {
359        *self = self.clone() - Self::one()
360    }
361
362    /// Increments self by one.
363    ///
364    /// # Examples
365    ///
366    /// ~~~
367    /// # use num_integer::Integer;
368    /// let mut x: i32 = 41;
369    /// x.inc();
370    /// assert_eq!(x, 42);
371    /// ~~~
372    fn inc(&mut self)
373    where
374        Self: Clone,
375    {
376        *self = self.clone() + Self::one()
377    }
378}
379
380/// Greatest common divisor and Bézout coefficients
381///
382/// ```no_build
383/// let e = isize::extended_gcd(a, b);
384/// assert_eq!(e.gcd, e.x*a + e.y*b);
385/// ```
386#[derive(Debug, Clone, Copy, PartialEq, Eq)]
387pub struct ExtendedGcd<A> {
388    pub gcd: A,
389    pub x: A,
390    pub y: A,
391}
392
393/// Simultaneous integer division and modulus
394#[inline]
395pub fn div_rem<T: Integer>(x: T, y: T) -> (T, T) {
396    x.div_rem(&y)
397}
398/// Floored integer division
399#[inline]
400pub fn div_floor<T: Integer>(x: T, y: T) -> T {
401    x.div_floor(&y)
402}
403/// Floored integer modulus
404#[inline]
405pub fn mod_floor<T: Integer>(x: T, y: T) -> T {
406    x.mod_floor(&y)
407}
408/// Simultaneous floored integer division and modulus
409#[inline]
410pub fn div_mod_floor<T: Integer>(x: T, y: T) -> (T, T) {
411    x.div_mod_floor(&y)
412}
413/// Ceiled integer division
414#[inline]
415pub fn div_ceil<T: Integer>(x: T, y: T) -> T {
416    x.div_ceil(&y)
417}
418
419/// Calculates the Greatest Common Divisor (GCD) of the number and `other`. The
420/// result is always non-negative.
421#[inline(always)]
422pub fn gcd<T: Integer>(x: T, y: T) -> T {
423    x.gcd(&y)
424}
425/// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
426#[inline(always)]
427pub fn lcm<T: Integer>(x: T, y: T) -> T {
428    x.lcm(&y)
429}
430
431/// Calculates the Greatest Common Divisor (GCD) and
432/// Lowest Common Multiple (LCM) of the number and `other`.
433#[inline(always)]
434pub fn gcd_lcm<T: Integer>(x: T, y: T) -> (T, T) {
435    x.gcd_lcm(&y)
436}
437
438macro_rules! impl_integer_for_isize {
439    ($T:ty, $test_mod:ident) => {
440        impl Integer for $T {
441            /// Floored integer division
442            #[inline]
443            fn div_floor(&self, other: &Self) -> Self {
444                // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
445                // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
446                let (d, r) = self.div_rem(other);
447                if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
448                    d - 1
449                } else {
450                    d
451                }
452            }
453
454            /// Floored integer modulo
455            #[inline]
456            fn mod_floor(&self, other: &Self) -> Self {
457                // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
458                // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
459                let r = *self % *other;
460                if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
461                    r + *other
462                } else {
463                    r
464                }
465            }
466
467            /// Calculates `div_floor` and `mod_floor` simultaneously
468            #[inline]
469            fn div_mod_floor(&self, other: &Self) -> (Self, Self) {
470                // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
471                // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
472                let (d, r) = self.div_rem(other);
473                if (r > 0 && *other < 0) || (r < 0 && *other > 0) {
474                    (d - 1, r + *other)
475                } else {
476                    (d, r)
477                }
478            }
479
480            #[inline]
481            fn div_ceil(&self, other: &Self) -> Self {
482                let (d, r) = self.div_rem(other);
483                if (r > 0 && *other > 0) || (r < 0 && *other < 0) {
484                    d + 1
485                } else {
486                    d
487                }
488            }
489
490            /// Calculates the Greatest Common Divisor (GCD) of the number and
491            /// `other`. The result is always non-negative.
492            #[inline]
493            fn gcd(&self, other: &Self) -> Self {
494                // Use Stein's algorithm
495                let mut m = *self;
496                let mut n = *other;
497                if m == 0 || n == 0 {
498                    return (m | n).abs();
499                }
500
501                // find common factors of 2
502                let shift = (m | n).trailing_zeros();
503
504                // The algorithm needs positive numbers, but the minimum value
505                // can't be represented as a positive one.
506                // It's also a power of two, so the gcd can be
507                // calculated by bitshifting in that case
508
509                // Assuming two's complement, the number created by the shift
510                // is positive for all numbers except gcd = abs(min value)
511                // The call to .abs() causes a panic in debug mode
512                if m == Self::min_value() || n == Self::min_value() {
513                    return (1 << shift).abs();
514                }
515
516                // guaranteed to be positive now, rest like unsigned algorithm
517                m = m.abs();
518                n = n.abs();
519
520                // divide n and m by 2 until odd
521                m >>= m.trailing_zeros();
522                n >>= n.trailing_zeros();
523
524                while m != n {
525                    if m > n {
526                        m -= n;
527                        m >>= m.trailing_zeros();
528                    } else {
529                        n -= m;
530                        n >>= n.trailing_zeros();
531                    }
532                }
533                m << shift
534            }
535
536            #[inline]
537            fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self) {
538                let egcd = self.extended_gcd(other);
539                // should not have to recalculate abs
540                let lcm = if egcd.gcd.is_zero() {
541                    Self::zero()
542                } else {
543                    (*self * (*other / egcd.gcd)).abs()
544                };
545                (egcd, lcm)
546            }
547
548            /// Calculates the Lowest Common Multiple (LCM) of the number and
549            /// `other`.
550            #[inline]
551            fn lcm(&self, other: &Self) -> Self {
552                self.gcd_lcm(other).1
553            }
554
555            /// Calculates the Greatest Common Divisor (GCD) and
556            /// Lowest Common Multiple (LCM) of the number and `other`.
557            #[inline]
558            fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
559                if self.is_zero() && other.is_zero() {
560                    return (Self::zero(), Self::zero());
561                }
562                let gcd = self.gcd(other);
563                // should not have to recalculate abs
564                let lcm = (*self * (*other / gcd)).abs();
565                (gcd, lcm)
566            }
567
568            /// Returns `true` if the number is a multiple of `other`.
569            #[inline]
570            fn is_multiple_of(&self, other: &Self) -> bool {
571                if other.is_zero() {
572                    return self.is_zero();
573                }
574                *self % *other == 0
575            }
576
577            /// Returns `true` if the number is divisible by `2`
578            #[inline]
579            fn is_even(&self) -> bool {
580                (*self) & 1 == 0
581            }
582
583            /// Returns `true` if the number is not divisible by `2`
584            #[inline]
585            fn is_odd(&self) -> bool {
586                !self.is_even()
587            }
588
589            /// Simultaneous truncated integer division and modulus.
590            #[inline]
591            fn div_rem(&self, other: &Self) -> (Self, Self) {
592                (*self / *other, *self % *other)
593            }
594
595            /// Rounds up to nearest multiple of argument.
596            #[inline]
597            fn next_multiple_of(&self, other: &Self) -> Self {
598                // Avoid the overflow of `MIN % -1`
599                if *other == -1 {
600                    return *self;
601                }
602
603                let m = Integer::mod_floor(self, other);
604                *self + if m == 0 { 0 } else { other - m }
605            }
606
607            /// Rounds down to nearest multiple of argument.
608            #[inline]
609            fn prev_multiple_of(&self, other: &Self) -> Self {
610                // Avoid the overflow of `MIN % -1`
611                if *other == -1 {
612                    return *self;
613                }
614
615                *self - Integer::mod_floor(self, other)
616            }
617        }
618
619        #[cfg(test)]
620        mod $test_mod {
621            use crate::Integer;
622            use core::mem;
623
624            /// Checks that the division rule holds for:
625            ///
626            /// - `n`: numerator (dividend)
627            /// - `d`: denominator (divisor)
628            /// - `qr`: quotient and remainder
629            #[cfg(test)]
630            fn test_division_rule((n, d): ($T, $T), (q, r): ($T, $T)) {
631                assert_eq!(d * q + r, n);
632            }
633
634            #[test]
635            fn test_div_rem() {
636                fn test_nd_dr(nd: ($T, $T), qr: ($T, $T)) {
637                    let (n, d) = nd;
638                    let separate_div_rem = (n / d, n % d);
639                    let combined_div_rem = n.div_rem(&d);
640
641                    test_division_rule(nd, qr);
642
643                    assert_eq!(separate_div_rem, qr);
644                    assert_eq!(combined_div_rem, qr);
645                }
646
647                test_nd_dr((8, 3), (2, 2));
648                test_nd_dr((8, -3), (-2, 2));
649                test_nd_dr((-8, 3), (-2, -2));
650                test_nd_dr((-8, -3), (2, -2));
651
652                test_nd_dr((1, 2), (0, 1));
653                test_nd_dr((1, -2), (0, 1));
654                test_nd_dr((-1, 2), (0, -1));
655                test_nd_dr((-1, -2), (0, -1));
656            }
657
658            #[test]
659            fn test_div_mod_floor() {
660                fn test_nd_dm(nd: ($T, $T), dm: ($T, $T)) {
661                    let (n, d) = nd;
662                    let separate_div_mod_floor =
663                        (Integer::div_floor(&n, &d), Integer::mod_floor(&n, &d));
664                    let combined_div_mod_floor = Integer::div_mod_floor(&n, &d);
665
666                    test_division_rule(nd, dm);
667
668                    assert_eq!(separate_div_mod_floor, dm);
669                    assert_eq!(combined_div_mod_floor, dm);
670                }
671
672                test_nd_dm((8, 3), (2, 2));
673                test_nd_dm((8, -3), (-3, -1));
674                test_nd_dm((-8, 3), (-3, 1));
675                test_nd_dm((-8, -3), (2, -2));
676
677                test_nd_dm((1, 2), (0, 1));
678                test_nd_dm((1, -2), (-1, -1));
679                test_nd_dm((-1, 2), (-1, 1));
680                test_nd_dm((-1, -2), (0, -1));
681            }
682
683            #[test]
684            fn test_gcd() {
685                assert_eq!((10 as $T).gcd(&2), 2 as $T);
686                assert_eq!((10 as $T).gcd(&3), 1 as $T);
687                assert_eq!((0 as $T).gcd(&3), 3 as $T);
688                assert_eq!((3 as $T).gcd(&3), 3 as $T);
689                assert_eq!((56 as $T).gcd(&42), 14 as $T);
690                assert_eq!((3 as $T).gcd(&-3), 3 as $T);
691                assert_eq!((-6 as $T).gcd(&3), 3 as $T);
692                assert_eq!((-4 as $T).gcd(&-2), 2 as $T);
693            }
694
695            #[test]
696            fn test_gcd_cmp_with_euclidean() {
697                fn euclidean_gcd(mut m: $T, mut n: $T) -> $T {
698                    while m != 0 {
699                        mem::swap(&mut m, &mut n);
700                        m %= n;
701                    }
702
703                    n.abs()
704                }
705
706                // gcd(-128, b) = 128 is not representable as positive value
707                // for i8
708                for i in -127..=127 {
709                    for j in -127..=127 {
710                        assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
711                    }
712                }
713            }
714
715            #[test]
716            fn test_gcd_min_val() {
717                let min = <$T>::min_value();
718                let max = <$T>::max_value();
719                let max_pow2 = max / 2 + 1;
720                assert_eq!(min.gcd(&max), 1 as $T);
721                assert_eq!(max.gcd(&min), 1 as $T);
722                assert_eq!(min.gcd(&max_pow2), max_pow2);
723                assert_eq!(max_pow2.gcd(&min), max_pow2);
724                assert_eq!(min.gcd(&42), 2 as $T);
725                assert_eq!((42 as $T).gcd(&min), 2 as $T);
726            }
727
728            #[test]
729            #[should_panic]
730            fn test_gcd_min_val_min_val() {
731                let min = <$T>::min_value();
732                assert!(min.gcd(&min) >= 0);
733            }
734
735            #[test]
736            #[should_panic]
737            fn test_gcd_min_val_0() {
738                let min = <$T>::min_value();
739                assert!(min.gcd(&0) >= 0);
740            }
741
742            #[test]
743            #[should_panic]
744            fn test_gcd_0_min_val() {
745                let min = <$T>::min_value();
746                assert!((0 as $T).gcd(&min) >= 0);
747            }
748
749            #[test]
750            fn test_lcm() {
751                assert_eq!((1 as $T).lcm(&0), 0 as $T);
752                assert_eq!((0 as $T).lcm(&1), 0 as $T);
753                assert_eq!((1 as $T).lcm(&1), 1 as $T);
754                assert_eq!((-1 as $T).lcm(&1), 1 as $T);
755                assert_eq!((1 as $T).lcm(&-1), 1 as $T);
756                assert_eq!((-1 as $T).lcm(&-1), 1 as $T);
757                assert_eq!((8 as $T).lcm(&9), 72 as $T);
758                assert_eq!((11 as $T).lcm(&5), 55 as $T);
759            }
760
761            #[test]
762            fn test_gcd_lcm() {
763                use core::iter::once;
764                for i in once(0)
765                    .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
766                    .chain(once(-128))
767                {
768                    for j in once(0)
769                        .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
770                        .chain(once(-128))
771                    {
772                        assert_eq!(i.gcd_lcm(&j), (i.gcd(&j), i.lcm(&j)));
773                    }
774                }
775            }
776
777            #[test]
778            fn test_extended_gcd_lcm() {
779                use crate::ExtendedGcd;
780                use core::fmt::Debug;
781                use num_traits::NumAssign;
782
783                fn check<A: Copy + Debug + Integer + NumAssign>(a: A, b: A) {
784                    let ExtendedGcd { gcd, x, y, .. } = a.extended_gcd(&b);
785                    assert_eq!(gcd, x * a + y * b);
786                }
787
788                use core::iter::once;
789                for i in once(0)
790                    .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
791                    .chain(once(-128))
792                {
793                    for j in once(0)
794                        .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
795                        .chain(once(-128))
796                    {
797                        check(i, j);
798                        let (ExtendedGcd { gcd, .. }, lcm) = i.extended_gcd_lcm(&j);
799                        assert_eq!((gcd, lcm), (i.gcd(&j), i.lcm(&j)));
800                    }
801                }
802            }
803
804            #[test]
805            fn test_even() {
806                assert_eq!((-4 as $T).is_even(), true);
807                assert_eq!((-3 as $T).is_even(), false);
808                assert_eq!((-2 as $T).is_even(), true);
809                assert_eq!((-1 as $T).is_even(), false);
810                assert_eq!((0 as $T).is_even(), true);
811                assert_eq!((1 as $T).is_even(), false);
812                assert_eq!((2 as $T).is_even(), true);
813                assert_eq!((3 as $T).is_even(), false);
814                assert_eq!((4 as $T).is_even(), true);
815            }
816
817            #[test]
818            fn test_odd() {
819                assert_eq!((-4 as $T).is_odd(), false);
820                assert_eq!((-3 as $T).is_odd(), true);
821                assert_eq!((-2 as $T).is_odd(), false);
822                assert_eq!((-1 as $T).is_odd(), true);
823                assert_eq!((0 as $T).is_odd(), false);
824                assert_eq!((1 as $T).is_odd(), true);
825                assert_eq!((2 as $T).is_odd(), false);
826                assert_eq!((3 as $T).is_odd(), true);
827                assert_eq!((4 as $T).is_odd(), false);
828            }
829
830            #[test]
831            fn test_multiple_of_one_limits() {
832                for x in &[<$T>::min_value(), <$T>::max_value()] {
833                    for one in &[1, -1] {
834                        assert_eq!(Integer::next_multiple_of(x, one), *x);
835                        assert_eq!(Integer::prev_multiple_of(x, one), *x);
836                    }
837                }
838            }
839        }
840    };
841}
842
843impl_integer_for_isize!(i8, test_integer_i8);
844impl_integer_for_isize!(i16, test_integer_i16);
845impl_integer_for_isize!(i32, test_integer_i32);
846impl_integer_for_isize!(i64, test_integer_i64);
847impl_integer_for_isize!(i128, test_integer_i128);
848impl_integer_for_isize!(isize, test_integer_isize);
849
850macro_rules! impl_integer_for_usize {
851    ($T:ty, $test_mod:ident) => {
852        impl Integer for $T {
853            /// Unsigned integer division. Returns the same result as `div` (`/`).
854            #[inline]
855            fn div_floor(&self, other: &Self) -> Self {
856                *self / *other
857            }
858
859            /// Unsigned integer modulo operation. Returns the same result as `rem` (`%`).
860            #[inline]
861            fn mod_floor(&self, other: &Self) -> Self {
862                *self % *other
863            }
864
865            #[inline]
866            fn div_ceil(&self, other: &Self) -> Self {
867                *self / *other + (0 != *self % *other) as Self
868            }
869
870            /// Calculates the Greatest Common Divisor (GCD) of the number and `other`
871            #[inline]
872            fn gcd(&self, other: &Self) -> Self {
873                // Use Stein's algorithm
874                let mut m = *self;
875                let mut n = *other;
876                if m == 0 || n == 0 {
877                    return m | n;
878                }
879
880                // find common factors of 2
881                let shift = (m | n).trailing_zeros();
882
883                // divide n and m by 2 until odd
884                m >>= m.trailing_zeros();
885                n >>= n.trailing_zeros();
886
887                while m != n {
888                    if m > n {
889                        m -= n;
890                        m >>= m.trailing_zeros();
891                    } else {
892                        n -= m;
893                        n >>= n.trailing_zeros();
894                    }
895                }
896                m << shift
897            }
898
899            #[inline]
900            fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self) {
901                let egcd = self.extended_gcd(other);
902                // should not have to recalculate abs
903                let lcm = if egcd.gcd.is_zero() {
904                    Self::zero()
905                } else {
906                    *self * (*other / egcd.gcd)
907                };
908                (egcd, lcm)
909            }
910
911            /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
912            #[inline]
913            fn lcm(&self, other: &Self) -> Self {
914                self.gcd_lcm(other).1
915            }
916
917            /// Calculates the Greatest Common Divisor (GCD) and
918            /// Lowest Common Multiple (LCM) of the number and `other`.
919            #[inline]
920            fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
921                if self.is_zero() && other.is_zero() {
922                    return (Self::zero(), Self::zero());
923                }
924                let gcd = self.gcd(other);
925                let lcm = *self * (*other / gcd);
926                (gcd, lcm)
927            }
928
929            /// Returns `true` if the number is a multiple of `other`.
930            #[inline]
931            fn is_multiple_of(&self, other: &Self) -> bool {
932                if other.is_zero() {
933                    return self.is_zero();
934                }
935                *self % *other == 0
936            }
937
938            /// Returns `true` if the number is divisible by `2`.
939            #[inline]
940            fn is_even(&self) -> bool {
941                *self % 2 == 0
942            }
943
944            /// Returns `true` if the number is not divisible by `2`.
945            #[inline]
946            fn is_odd(&self) -> bool {
947                !self.is_even()
948            }
949
950            /// Simultaneous truncated integer division and modulus.
951            #[inline]
952            fn div_rem(&self, other: &Self) -> (Self, Self) {
953                (*self / *other, *self % *other)
954            }
955        }
956
957        #[cfg(test)]
958        mod $test_mod {
959            use crate::Integer;
960            use core::mem;
961
962            #[test]
963            fn test_div_mod_floor() {
964                assert_eq!(<$T as Integer>::div_floor(&10, &3), 3 as $T);
965                assert_eq!(<$T as Integer>::mod_floor(&10, &3), 1 as $T);
966                assert_eq!(<$T as Integer>::div_mod_floor(&10, &3), (3 as $T, 1 as $T));
967                assert_eq!(<$T as Integer>::div_floor(&5, &5), 1 as $T);
968                assert_eq!(<$T as Integer>::mod_floor(&5, &5), 0 as $T);
969                assert_eq!(<$T as Integer>::div_mod_floor(&5, &5), (1 as $T, 0 as $T));
970                assert_eq!(<$T as Integer>::div_floor(&3, &7), 0 as $T);
971                assert_eq!(<$T as Integer>::div_floor(&3, &7), 0 as $T);
972                assert_eq!(<$T as Integer>::mod_floor(&3, &7), 3 as $T);
973                assert_eq!(<$T as Integer>::div_mod_floor(&3, &7), (0 as $T, 3 as $T));
974            }
975
976            #[test]
977            fn test_gcd() {
978                assert_eq!((10 as $T).gcd(&2), 2 as $T);
979                assert_eq!((10 as $T).gcd(&3), 1 as $T);
980                assert_eq!((0 as $T).gcd(&3), 3 as $T);
981                assert_eq!((3 as $T).gcd(&3), 3 as $T);
982                assert_eq!((56 as $T).gcd(&42), 14 as $T);
983            }
984
985            #[test]
986            fn test_gcd_cmp_with_euclidean() {
987                fn euclidean_gcd(mut m: $T, mut n: $T) -> $T {
988                    while m != 0 {
989                        mem::swap(&mut m, &mut n);
990                        m %= n;
991                    }
992                    n
993                }
994
995                for i in 0..=255 {
996                    for j in 0..=255 {
997                        assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
998                    }
999                }
1000            }
1001
1002            #[test]
1003            fn test_lcm() {
1004                assert_eq!((1 as $T).lcm(&0), 0 as $T);
1005                assert_eq!((0 as $T).lcm(&1), 0 as $T);
1006                assert_eq!((1 as $T).lcm(&1), 1 as $T);
1007                assert_eq!((8 as $T).lcm(&9), 72 as $T);
1008                assert_eq!((11 as $T).lcm(&5), 55 as $T);
1009                assert_eq!((15 as $T).lcm(&17), 255 as $T);
1010            }
1011
1012            #[test]
1013            fn test_gcd_lcm() {
1014                for i in (0..).take(256) {
1015                    for j in (0..).take(256) {
1016                        assert_eq!(i.gcd_lcm(&j), (i.gcd(&j), i.lcm(&j)));
1017                    }
1018                }
1019            }
1020
1021            #[test]
1022            fn test_is_multiple_of() {
1023                assert!(<$T as Integer>::is_multiple_of(&(0 as $T), &(0 as $T)));
1024                assert!(<$T as Integer>::is_multiple_of(&(6 as $T), &(6 as $T)));
1025                assert!(<$T as Integer>::is_multiple_of(&(6 as $T), &(3 as $T)));
1026                assert!(<$T as Integer>::is_multiple_of(&(6 as $T), &(1 as $T)));
1027
1028                assert!(!<$T as Integer>::is_multiple_of(&(42 as $T), &(5 as $T)));
1029                assert!(!<$T as Integer>::is_multiple_of(&(5 as $T), &(3 as $T)));
1030                assert!(!<$T as Integer>::is_multiple_of(&(42 as $T), &(0 as $T)));
1031            }
1032
1033            #[test]
1034            fn test_even() {
1035                assert_eq!((0 as $T).is_even(), true);
1036                assert_eq!((1 as $T).is_even(), false);
1037                assert_eq!((2 as $T).is_even(), true);
1038                assert_eq!((3 as $T).is_even(), false);
1039                assert_eq!((4 as $T).is_even(), true);
1040            }
1041
1042            #[test]
1043            fn test_odd() {
1044                assert_eq!((0 as $T).is_odd(), false);
1045                assert_eq!((1 as $T).is_odd(), true);
1046                assert_eq!((2 as $T).is_odd(), false);
1047                assert_eq!((3 as $T).is_odd(), true);
1048                assert_eq!((4 as $T).is_odd(), false);
1049            }
1050        }
1051    };
1052}
1053
1054impl_integer_for_usize!(u8, test_integer_u8);
1055impl_integer_for_usize!(u16, test_integer_u16);
1056impl_integer_for_usize!(u32, test_integer_u32);
1057impl_integer_for_usize!(u64, test_integer_u64);
1058impl_integer_for_usize!(u128, test_integer_u128);
1059impl_integer_for_usize!(usize, test_integer_usize);
1060
1061/// An iterator over binomial coefficients.
1062pub struct IterBinomial<T> {
1063    a: T,
1064    n: T,
1065    k: T,
1066}
1067
1068impl<T> IterBinomial<T>
1069where
1070    T: Integer,
1071{
1072    /// For a given n, iterate over all binomial coefficients binomial(n, k), for k=0...n.
1073    ///
1074    /// Note that this might overflow, depending on `T`. For the primitive
1075    /// integer types, the following n are the largest ones for which there will
1076    /// be no overflow:
1077    ///
1078    /// type | n
1079    /// -----|---
1080    /// u8   | 10
1081    /// i8   |  9
1082    /// u16  | 18
1083    /// i16  | 17
1084    /// u32  | 34
1085    /// i32  | 33
1086    /// u64  | 67
1087    /// i64  | 66
1088    ///
1089    /// For larger n, `T` should be a bigint type.
1090    pub fn new(n: T) -> IterBinomial<T> {
1091        IterBinomial {
1092            k: T::zero(),
1093            a: T::one(),
1094            n,
1095        }
1096    }
1097}
1098
1099impl<T> Iterator for IterBinomial<T>
1100where
1101    T: Integer + Clone,
1102{
1103    type Item = T;
1104
1105    fn next(&mut self) -> Option<T> {
1106        if self.k > self.n {
1107            return None;
1108        }
1109        self.a = if !self.k.is_zero() {
1110            multiply_and_divide(
1111                self.a.clone(),
1112                self.n.clone() - self.k.clone() + T::one(),
1113                self.k.clone(),
1114            )
1115        } else {
1116            T::one()
1117        };
1118        self.k = self.k.clone() + T::one();
1119        Some(self.a.clone())
1120    }
1121}
1122
1123/// Calculate r * a / b, avoiding overflows and fractions.
1124///
1125/// Assumes that b divides r * a evenly.
1126fn multiply_and_divide<T: Integer + Clone>(r: T, a: T, b: T) -> T {
1127    // See http://blog.plover.com/math/choose-2.html for the idea.
1128    let g = gcd(r.clone(), b.clone());
1129    r / g.clone() * (a / (b / g))
1130}
1131
1132/// Calculate the binomial coefficient.
1133///
1134/// Note that this might overflow, depending on `T`. For the primitive integer
1135/// types, the following n are the largest ones possible such that there will
1136/// be no overflow for any k:
1137///
1138/// type | n
1139/// -----|---
1140/// u8   | 10
1141/// i8   |  9
1142/// u16  | 18
1143/// i16  | 17
1144/// u32  | 34
1145/// i32  | 33
1146/// u64  | 67
1147/// i64  | 66
1148///
1149/// For larger n, consider using a bigint type for `T`.
1150pub fn binomial<T: Integer + Clone>(mut n: T, k: T) -> T {
1151    // See http://blog.plover.com/math/choose.html for the idea.
1152    if k > n {
1153        return T::zero();
1154    }
1155    if k > n.clone() - k.clone() {
1156        return binomial(n.clone(), n - k);
1157    }
1158    let mut r = T::one();
1159    let mut d = T::one();
1160    loop {
1161        if d > k {
1162            break;
1163        }
1164        r = multiply_and_divide(r, n.clone(), d.clone());
1165        n = n - T::one();
1166        d = d + T::one();
1167    }
1168    r
1169}
1170
1171/// Calculate the multinomial coefficient.
1172pub fn multinomial<T: Integer + Clone>(k: &[T]) -> T
1173where
1174    for<'a> T: Add<&'a T, Output = T>,
1175{
1176    let mut r = T::one();
1177    let mut p = T::zero();
1178    for i in k {
1179        p = p + i;
1180        r = r * binomial(p.clone(), i.clone());
1181    }
1182    r
1183}
1184
1185#[test]
1186fn test_lcm_overflow() {
1187    macro_rules! check {
1188        ($t:ty, $x:expr, $y:expr, $r:expr) => {{
1189            let x: $t = $x;
1190            let y: $t = $y;
1191            let o = x.checked_mul(y);
1192            assert!(
1193                o.is_none(),
1194                "sanity checking that {} input {} * {} overflows",
1195                stringify!($t),
1196                x,
1197                y
1198            );
1199            assert_eq!(x.lcm(&y), $r);
1200            assert_eq!(y.lcm(&x), $r);
1201        }};
1202    }
1203
1204    // Original bug (Issue #166)
1205    check!(i64, 46656000000000000, 600, 46656000000000000);
1206
1207    check!(i8, 0x40, 0x04, 0x40);
1208    check!(u8, 0x80, 0x02, 0x80);
1209    check!(i16, 0x40_00, 0x04, 0x40_00);
1210    check!(u16, 0x80_00, 0x02, 0x80_00);
1211    check!(i32, 0x4000_0000, 0x04, 0x4000_0000);
1212    check!(u32, 0x8000_0000, 0x02, 0x8000_0000);
1213    check!(i64, 0x4000_0000_0000_0000, 0x04, 0x4000_0000_0000_0000);
1214    check!(u64, 0x8000_0000_0000_0000, 0x02, 0x8000_0000_0000_0000);
1215}
1216
1217#[test]
1218fn test_iter_binomial() {
1219    macro_rules! check_simple {
1220        ($t:ty) => {{
1221            let n: $t = 3;
1222            let expected = [1, 3, 3, 1];
1223            for (b, &e) in IterBinomial::new(n).zip(&expected) {
1224                assert_eq!(b, e);
1225            }
1226        }};
1227    }
1228
1229    check_simple!(u8);
1230    check_simple!(i8);
1231    check_simple!(u16);
1232    check_simple!(i16);
1233    check_simple!(u32);
1234    check_simple!(i32);
1235    check_simple!(u64);
1236    check_simple!(i64);
1237
1238    macro_rules! check_binomial {
1239        ($t:ty, $n:expr) => {{
1240            let n: $t = $n;
1241            let mut k: $t = 0;
1242            for b in IterBinomial::new(n) {
1243                assert_eq!(b, binomial(n, k));
1244                k += 1;
1245            }
1246        }};
1247    }
1248
1249    // Check the largest n for which there is no overflow.
1250    check_binomial!(u8, 10);
1251    check_binomial!(i8, 9);
1252    check_binomial!(u16, 18);
1253    check_binomial!(i16, 17);
1254    check_binomial!(u32, 34);
1255    check_binomial!(i32, 33);
1256    check_binomial!(u64, 67);
1257    check_binomial!(i64, 66);
1258}
1259
1260#[test]
1261fn test_binomial() {
1262    macro_rules! check {
1263        ($t:ty, $x:expr, $y:expr, $r:expr) => {{
1264            let x: $t = $x;
1265            let y: $t = $y;
1266            let expected: $t = $r;
1267            assert_eq!(binomial(x, y), expected);
1268            if y <= x {
1269                assert_eq!(binomial(x, x - y), expected);
1270            }
1271        }};
1272    }
1273    check!(u8, 9, 4, 126);
1274    check!(u8, 0, 0, 1);
1275    check!(u8, 2, 3, 0);
1276
1277    check!(i8, 9, 4, 126);
1278    check!(i8, 0, 0, 1);
1279    check!(i8, 2, 3, 0);
1280
1281    check!(u16, 100, 2, 4950);
1282    check!(u16, 14, 4, 1001);
1283    check!(u16, 0, 0, 1);
1284    check!(u16, 2, 3, 0);
1285
1286    check!(i16, 100, 2, 4950);
1287    check!(i16, 14, 4, 1001);
1288    check!(i16, 0, 0, 1);
1289    check!(i16, 2, 3, 0);
1290
1291    check!(u32, 100, 2, 4950);
1292    check!(u32, 35, 11, 417225900);
1293    check!(u32, 14, 4, 1001);
1294    check!(u32, 0, 0, 1);
1295    check!(u32, 2, 3, 0);
1296
1297    check!(i32, 100, 2, 4950);
1298    check!(i32, 35, 11, 417225900);
1299    check!(i32, 14, 4, 1001);
1300    check!(i32, 0, 0, 1);
1301    check!(i32, 2, 3, 0);
1302
1303    check!(u64, 100, 2, 4950);
1304    check!(u64, 35, 11, 417225900);
1305    check!(u64, 14, 4, 1001);
1306    check!(u64, 0, 0, 1);
1307    check!(u64, 2, 3, 0);
1308
1309    check!(i64, 100, 2, 4950);
1310    check!(i64, 35, 11, 417225900);
1311    check!(i64, 14, 4, 1001);
1312    check!(i64, 0, 0, 1);
1313    check!(i64, 2, 3, 0);
1314}
1315
1316#[test]
1317fn test_multinomial() {
1318    macro_rules! check_binomial {
1319        ($t:ty, $k:expr) => {{
1320            let n: $t = $k.iter().fold(0, |acc, &x| acc + x);
1321            let k: &[$t] = $k;
1322            assert_eq!(k.len(), 2);
1323            assert_eq!(multinomial(k), binomial(n, k[0]));
1324        }};
1325    }
1326
1327    check_binomial!(u8, &[4, 5]);
1328
1329    check_binomial!(i8, &[4, 5]);
1330
1331    check_binomial!(u16, &[2, 98]);
1332    check_binomial!(u16, &[4, 10]);
1333
1334    check_binomial!(i16, &[2, 98]);
1335    check_binomial!(i16, &[4, 10]);
1336
1337    check_binomial!(u32, &[2, 98]);
1338    check_binomial!(u32, &[11, 24]);
1339    check_binomial!(u32, &[4, 10]);
1340
1341    check_binomial!(i32, &[2, 98]);
1342    check_binomial!(i32, &[11, 24]);
1343    check_binomial!(i32, &[4, 10]);
1344
1345    check_binomial!(u64, &[2, 98]);
1346    check_binomial!(u64, &[11, 24]);
1347    check_binomial!(u64, &[4, 10]);
1348
1349    check_binomial!(i64, &[2, 98]);
1350    check_binomial!(i64, &[11, 24]);
1351    check_binomial!(i64, &[4, 10]);
1352
1353    macro_rules! check_multinomial {
1354        ($t:ty, $k:expr, $r:expr) => {{
1355            let k: &[$t] = $k;
1356            let expected: $t = $r;
1357            assert_eq!(multinomial(k), expected);
1358        }};
1359    }
1360
1361    check_multinomial!(u8, &[2, 1, 2], 30);
1362    check_multinomial!(u8, &[2, 3, 0], 10);
1363
1364    check_multinomial!(i8, &[2, 1, 2], 30);
1365    check_multinomial!(i8, &[2, 3, 0], 10);
1366
1367    check_multinomial!(u16, &[2, 1, 2], 30);
1368    check_multinomial!(u16, &[2, 3, 0], 10);
1369
1370    check_multinomial!(i16, &[2, 1, 2], 30);
1371    check_multinomial!(i16, &[2, 3, 0], 10);
1372
1373    check_multinomial!(u32, &[2, 1, 2], 30);
1374    check_multinomial!(u32, &[2, 3, 0], 10);
1375
1376    check_multinomial!(i32, &[2, 1, 2], 30);
1377    check_multinomial!(i32, &[2, 3, 0], 10);
1378
1379    check_multinomial!(u64, &[2, 1, 2], 30);
1380    check_multinomial!(u64, &[2, 3, 0], 10);
1381
1382    check_multinomial!(i64, &[2, 1, 2], 30);
1383    check_multinomial!(i64, &[2, 3, 0], 10);
1384
1385    check_multinomial!(u64, &[], 1);
1386    check_multinomial!(u64, &[0], 1);
1387    check_multinomial!(u64, &[12345], 1);
1388}
num_integer/lib.rs

num_integer/
lib.rs
