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