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