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
19 #![no_std]
20 #[cfg(feature = "std")]
21 extern crate std;
22
23 extern crate num_traits as traits;
24
25 use core::ops::Add;
26 use core::mem;
27
28 use traits::{Num, Signed};
29
30 mod roots;
31 pub use roots::Roots;
32 pub use roots::{sqrt, cbrt, nth_root};
33
34 pub trait Integer: Sized + Num + PartialOrd + Ord + Eq {
35 /// Floored integer division.
36 ///
37 /// # Examples
38 ///
39 /// ~~~
40 /// # use num_integer::Integer;
41 /// assert!(( 8).div_floor(& 3) == 2);
42 /// assert!(( 8).div_floor(&-3) == -3);
43 /// assert!((-8).div_floor(& 3) == -3);
44 /// assert!((-8).div_floor(&-3) == 2);
45 ///
46 /// assert!(( 1).div_floor(& 2) == 0);
47 /// assert!(( 1).div_floor(&-2) == -1);
48 /// assert!((-1).div_floor(& 2) == -1);
49 /// assert!((-1).div_floor(&-2) == 0);
50 /// ~~~
div_floor(&self, other: &Self) -> Self51 fn div_floor(&self, other: &Self) -> Self;
52
53 /// Floored integer modulo, satisfying:
54 ///
55 /// ~~~
56 /// # use num_integer::Integer;
57 /// # let n = 1; let d = 1;
58 /// assert!(n.div_floor(&d) * d + n.mod_floor(&d) == n)
59 /// ~~~
60 ///
61 /// # Examples
62 ///
63 /// ~~~
64 /// # use num_integer::Integer;
65 /// assert!(( 8).mod_floor(& 3) == 2);
66 /// assert!(( 8).mod_floor(&-3) == -1);
67 /// assert!((-8).mod_floor(& 3) == 1);
68 /// assert!((-8).mod_floor(&-3) == -2);
69 ///
70 /// assert!(( 1).mod_floor(& 2) == 1);
71 /// assert!(( 1).mod_floor(&-2) == -1);
72 /// assert!((-1).mod_floor(& 2) == 1);
73 /// assert!((-1).mod_floor(&-2) == -1);
74 /// ~~~
mod_floor(&self, other: &Self) -> Self75 fn mod_floor(&self, other: &Self) -> Self;
76
77 /// Greatest Common Divisor (GCD).
78 ///
79 /// # Examples
80 ///
81 /// ~~~
82 /// # use num_integer::Integer;
83 /// assert_eq!(6.gcd(&8), 2);
84 /// assert_eq!(7.gcd(&3), 1);
85 /// ~~~
gcd(&self, other: &Self) -> Self86 fn gcd(&self, other: &Self) -> Self;
87
88 /// Lowest Common Multiple (LCM).
89 ///
90 /// # Examples
91 ///
92 /// ~~~
93 /// # use num_integer::Integer;
94 /// assert_eq!(7.lcm(&3), 21);
95 /// assert_eq!(2.lcm(&4), 4);
96 /// ~~~
lcm(&self, other: &Self) -> Self97 fn lcm(&self, other: &Self) -> Self;
98
99 /// Deprecated, use `is_multiple_of` instead.
divides(&self, other: &Self) -> bool100 fn divides(&self, other: &Self) -> bool;
101
102 /// Returns `true` if `self` is a multiple of `other`.
103 ///
104 /// # Examples
105 ///
106 /// ~~~
107 /// # use num_integer::Integer;
108 /// assert_eq!(9.is_multiple_of(&3), true);
109 /// assert_eq!(3.is_multiple_of(&9), false);
110 /// ~~~
is_multiple_of(&self, other: &Self) -> bool111 fn is_multiple_of(&self, other: &Self) -> bool;
112
113 /// Returns `true` if the number is even.
114 ///
115 /// # Examples
116 ///
117 /// ~~~
118 /// # use num_integer::Integer;
119 /// assert_eq!(3.is_even(), false);
120 /// assert_eq!(4.is_even(), true);
121 /// ~~~
is_even(&self) -> bool122 fn is_even(&self) -> bool;
123
124 /// Returns `true` if the number is odd.
125 ///
126 /// # Examples
127 ///
128 /// ~~~
129 /// # use num_integer::Integer;
130 /// assert_eq!(3.is_odd(), true);
131 /// assert_eq!(4.is_odd(), false);
132 /// ~~~
is_odd(&self) -> bool133 fn is_odd(&self) -> bool;
134
135 /// Simultaneous truncated integer division and modulus.
136 /// Returns `(quotient, remainder)`.
137 ///
138 /// # Examples
139 ///
140 /// ~~~
141 /// # use num_integer::Integer;
142 /// assert_eq!(( 8).div_rem( &3), ( 2, 2));
143 /// assert_eq!(( 8).div_rem(&-3), (-2, 2));
144 /// assert_eq!((-8).div_rem( &3), (-2, -2));
145 /// assert_eq!((-8).div_rem(&-3), ( 2, -2));
146 ///
147 /// assert_eq!(( 1).div_rem( &2), ( 0, 1));
148 /// assert_eq!(( 1).div_rem(&-2), ( 0, 1));
149 /// assert_eq!((-1).div_rem( &2), ( 0, -1));
150 /// assert_eq!((-1).div_rem(&-2), ( 0, -1));
151 /// ~~~
152 #[inline]
div_rem(&self, other: &Self) -> (Self, Self)153 fn div_rem(&self, other: &Self) -> (Self, Self);
154
155 /// Simultaneous floored integer division and modulus.
156 /// Returns `(quotient, remainder)`.
157 ///
158 /// # Examples
159 ///
160 /// ~~~
161 /// # use num_integer::Integer;
162 /// assert_eq!(( 8).div_mod_floor( &3), ( 2, 2));
163 /// assert_eq!(( 8).div_mod_floor(&-3), (-3, -1));
164 /// assert_eq!((-8).div_mod_floor( &3), (-3, 1));
165 /// assert_eq!((-8).div_mod_floor(&-3), ( 2, -2));
166 ///
167 /// assert_eq!(( 1).div_mod_floor( &2), ( 0, 1));
168 /// assert_eq!(( 1).div_mod_floor(&-2), (-1, -1));
169 /// assert_eq!((-1).div_mod_floor( &2), (-1, 1));
170 /// assert_eq!((-1).div_mod_floor(&-2), ( 0, -1));
171 /// ~~~
div_mod_floor(&self, other: &Self) -> (Self, Self)172 fn div_mod_floor(&self, other: &Self) -> (Self, Self) {
173 (self.div_floor(other), self.mod_floor(other))
174 }
175 }
176
177 /// Simultaneous integer division and modulus
178 #[inline]
div_rem<T: Integer>(x: T, y: T) -> (T, T)179 pub fn div_rem<T: Integer>(x: T, y: T) -> (T, T) {
180 x.div_rem(&y)
181 }
182 /// Floored integer division
183 #[inline]
div_floor<T: Integer>(x: T, y: T) -> T184 pub fn div_floor<T: Integer>(x: T, y: T) -> T {
185 x.div_floor(&y)
186 }
187 /// Floored integer modulus
188 #[inline]
mod_floor<T: Integer>(x: T, y: T) -> T189 pub fn mod_floor<T: Integer>(x: T, y: T) -> T {
190 x.mod_floor(&y)
191 }
192 /// Simultaneous floored integer division and modulus
193 #[inline]
div_mod_floor<T: Integer>(x: T, y: T) -> (T, T)194 pub fn div_mod_floor<T: Integer>(x: T, y: T) -> (T, T) {
195 x.div_mod_floor(&y)
196 }
197
198 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`. The
199 /// result is always positive.
200 #[inline(always)]
gcd<T: Integer>(x: T, y: T) -> T201 pub fn gcd<T: Integer>(x: T, y: T) -> T {
202 x.gcd(&y)
203 }
204 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
205 #[inline(always)]
lcm<T: Integer>(x: T, y: T) -> T206 pub fn lcm<T: Integer>(x: T, y: T) -> T {
207 x.lcm(&y)
208 }
209
210 macro_rules! impl_integer_for_isize {
211 ($T:ty, $test_mod:ident) => (
212 impl Integer for $T {
213 /// Floored integer division
214 #[inline]
215 fn div_floor(&self, other: &Self) -> Self {
216 // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
217 // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
218 match self.div_rem(other) {
219 (d, r) if (r > 0 && *other < 0)
220 || (r < 0 && *other > 0) => d - 1,
221 (d, _) => d,
222 }
223 }
224
225 /// Floored integer modulo
226 #[inline]
227 fn mod_floor(&self, other: &Self) -> Self {
228 // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
229 // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
230 match *self % *other {
231 r if (r > 0 && *other < 0)
232 || (r < 0 && *other > 0) => r + *other,
233 r => r,
234 }
235 }
236
237 /// Calculates `div_floor` and `mod_floor` simultaneously
238 #[inline]
239 fn div_mod_floor(&self, other: &Self) -> (Self, Self) {
240 // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
241 // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
242 match self.div_rem(other) {
243 (d, r) if (r > 0 && *other < 0)
244 || (r < 0 && *other > 0) => (d - 1, r + *other),
245 (d, r) => (d, r),
246 }
247 }
248
249 /// Calculates the Greatest Common Divisor (GCD) of the number and
250 /// `other`. The result is always positive.
251 #[inline]
252 fn gcd(&self, other: &Self) -> Self {
253 // Use Stein's algorithm
254 let mut m = *self;
255 let mut n = *other;
256 if m == 0 || n == 0 { return (m | n).abs() }
257
258 // find common factors of 2
259 let shift = (m | n).trailing_zeros();
260
261 // The algorithm needs positive numbers, but the minimum value
262 // can't be represented as a positive one.
263 // It's also a power of two, so the gcd can be
264 // calculated by bitshifting in that case
265
266 // Assuming two's complement, the number created by the shift
267 // is positive for all numbers except gcd = abs(min value)
268 // The call to .abs() causes a panic in debug mode
269 if m == Self::min_value() || n == Self::min_value() {
270 return (1 << shift).abs()
271 }
272
273 // guaranteed to be positive now, rest like unsigned algorithm
274 m = m.abs();
275 n = n.abs();
276
277 // divide n and m by 2 until odd
278 // m inside loop
279 n >>= n.trailing_zeros();
280
281 while m != 0 {
282 m >>= m.trailing_zeros();
283 if n > m { mem::swap(&mut n, &mut m) }
284 m -= n;
285 }
286
287 n << shift
288 }
289
290 /// Calculates the Lowest Common Multiple (LCM) of the number and
291 /// `other`.
292 #[inline]
293 fn lcm(&self, other: &Self) -> Self {
294 // should not have to recalculate abs
295 (*self * (*other / self.gcd(other))).abs()
296 }
297
298 /// Deprecated, use `is_multiple_of` instead.
299 #[inline]
300 fn divides(&self, other: &Self) -> bool {
301 self.is_multiple_of(other)
302 }
303
304 /// Returns `true` if the number is a multiple of `other`.
305 #[inline]
306 fn is_multiple_of(&self, other: &Self) -> bool {
307 *self % *other == 0
308 }
309
310 /// Returns `true` if the number is divisible by `2`
311 #[inline]
312 fn is_even(&self) -> bool { (*self) & 1 == 0 }
313
314 /// Returns `true` if the number is not divisible by `2`
315 #[inline]
316 fn is_odd(&self) -> bool { !self.is_even() }
317
318 /// Simultaneous truncated integer division and modulus.
319 #[inline]
320 fn div_rem(&self, other: &Self) -> (Self, Self) {
321 (*self / *other, *self % *other)
322 }
323 }
324
325 #[cfg(test)]
326 mod $test_mod {
327 use Integer;
328 use core::mem;
329
330 /// Checks that the division rule holds for:
331 ///
332 /// - `n`: numerator (dividend)
333 /// - `d`: denominator (divisor)
334 /// - `qr`: quotient and remainder
335 #[cfg(test)]
336 fn test_division_rule((n,d): ($T, $T), (q,r): ($T, $T)) {
337 assert_eq!(d * q + r, n);
338 }
339
340 #[test]
341 fn test_div_rem() {
342 fn test_nd_dr(nd: ($T,$T), qr: ($T,$T)) {
343 let (n,d) = nd;
344 let separate_div_rem = (n / d, n % d);
345 let combined_div_rem = n.div_rem(&d);
346
347 assert_eq!(separate_div_rem, qr);
348 assert_eq!(combined_div_rem, qr);
349
350 test_division_rule(nd, separate_div_rem);
351 test_division_rule(nd, combined_div_rem);
352 }
353
354 test_nd_dr(( 8, 3), ( 2, 2));
355 test_nd_dr(( 8, -3), (-2, 2));
356 test_nd_dr((-8, 3), (-2, -2));
357 test_nd_dr((-8, -3), ( 2, -2));
358
359 test_nd_dr(( 1, 2), ( 0, 1));
360 test_nd_dr(( 1, -2), ( 0, 1));
361 test_nd_dr((-1, 2), ( 0, -1));
362 test_nd_dr((-1, -2), ( 0, -1));
363 }
364
365 #[test]
366 fn test_div_mod_floor() {
367 fn test_nd_dm(nd: ($T,$T), dm: ($T,$T)) {
368 let (n,d) = nd;
369 let separate_div_mod_floor = (n.div_floor(&d), n.mod_floor(&d));
370 let combined_div_mod_floor = n.div_mod_floor(&d);
371
372 assert_eq!(separate_div_mod_floor, dm);
373 assert_eq!(combined_div_mod_floor, dm);
374
375 test_division_rule(nd, separate_div_mod_floor);
376 test_division_rule(nd, combined_div_mod_floor);
377 }
378
379 test_nd_dm(( 8, 3), ( 2, 2));
380 test_nd_dm(( 8, -3), (-3, -1));
381 test_nd_dm((-8, 3), (-3, 1));
382 test_nd_dm((-8, -3), ( 2, -2));
383
384 test_nd_dm(( 1, 2), ( 0, 1));
385 test_nd_dm(( 1, -2), (-1, -1));
386 test_nd_dm((-1, 2), (-1, 1));
387 test_nd_dm((-1, -2), ( 0, -1));
388 }
389
390 #[test]
391 fn test_gcd() {
392 assert_eq!((10 as $T).gcd(&2), 2 as $T);
393 assert_eq!((10 as $T).gcd(&3), 1 as $T);
394 assert_eq!((0 as $T).gcd(&3), 3 as $T);
395 assert_eq!((3 as $T).gcd(&3), 3 as $T);
396 assert_eq!((56 as $T).gcd(&42), 14 as $T);
397 assert_eq!((3 as $T).gcd(&-3), 3 as $T);
398 assert_eq!((-6 as $T).gcd(&3), 3 as $T);
399 assert_eq!((-4 as $T).gcd(&-2), 2 as $T);
400 }
401
402 #[test]
403 fn test_gcd_cmp_with_euclidean() {
404 fn euclidean_gcd(mut m: $T, mut n: $T) -> $T {
405 while m != 0 {
406 mem::swap(&mut m, &mut n);
407 m %= n;
408 }
409
410 n.abs()
411 }
412
413 // gcd(-128, b) = 128 is not representable as positive value
414 // for i8
415 for i in -127..127 {
416 for j in -127..127 {
417 assert_eq!(euclidean_gcd(i,j), i.gcd(&j));
418 }
419 }
420
421 // last value
422 // FIXME: Use inclusive ranges for above loop when implemented
423 let i = 127;
424 for j in -127..127 {
425 assert_eq!(euclidean_gcd(i,j), i.gcd(&j));
426 }
427 assert_eq!(127.gcd(&127), 127);
428 }
429
430 #[test]
431 fn test_gcd_min_val() {
432 let min = <$T>::min_value();
433 let max = <$T>::max_value();
434 let max_pow2 = max / 2 + 1;
435 assert_eq!(min.gcd(&max), 1 as $T);
436 assert_eq!(max.gcd(&min), 1 as $T);
437 assert_eq!(min.gcd(&max_pow2), max_pow2);
438 assert_eq!(max_pow2.gcd(&min), max_pow2);
439 assert_eq!(min.gcd(&42), 2 as $T);
440 assert_eq!((42 as $T).gcd(&min), 2 as $T);
441 }
442
443 #[test]
444 #[should_panic]
445 fn test_gcd_min_val_min_val() {
446 let min = <$T>::min_value();
447 assert!(min.gcd(&min) >= 0);
448 }
449
450 #[test]
451 #[should_panic]
452 fn test_gcd_min_val_0() {
453 let min = <$T>::min_value();
454 assert!(min.gcd(&0) >= 0);
455 }
456
457 #[test]
458 #[should_panic]
459 fn test_gcd_0_min_val() {
460 let min = <$T>::min_value();
461 assert!((0 as $T).gcd(&min) >= 0);
462 }
463
464 #[test]
465 fn test_lcm() {
466 assert_eq!((1 as $T).lcm(&0), 0 as $T);
467 assert_eq!((0 as $T).lcm(&1), 0 as $T);
468 assert_eq!((1 as $T).lcm(&1), 1 as $T);
469 assert_eq!((-1 as $T).lcm(&1), 1 as $T);
470 assert_eq!((1 as $T).lcm(&-1), 1 as $T);
471 assert_eq!((-1 as $T).lcm(&-1), 1 as $T);
472 assert_eq!((8 as $T).lcm(&9), 72 as $T);
473 assert_eq!((11 as $T).lcm(&5), 55 as $T);
474 }
475
476 #[test]
477 fn test_even() {
478 assert_eq!((-4 as $T).is_even(), true);
479 assert_eq!((-3 as $T).is_even(), false);
480 assert_eq!((-2 as $T).is_even(), true);
481 assert_eq!((-1 as $T).is_even(), false);
482 assert_eq!((0 as $T).is_even(), true);
483 assert_eq!((1 as $T).is_even(), false);
484 assert_eq!((2 as $T).is_even(), true);
485 assert_eq!((3 as $T).is_even(), false);
486 assert_eq!((4 as $T).is_even(), true);
487 }
488
489 #[test]
490 fn test_odd() {
491 assert_eq!((-4 as $T).is_odd(), false);
492 assert_eq!((-3 as $T).is_odd(), true);
493 assert_eq!((-2 as $T).is_odd(), false);
494 assert_eq!((-1 as $T).is_odd(), true);
495 assert_eq!((0 as $T).is_odd(), false);
496 assert_eq!((1 as $T).is_odd(), true);
497 assert_eq!((2 as $T).is_odd(), false);
498 assert_eq!((3 as $T).is_odd(), true);
499 assert_eq!((4 as $T).is_odd(), false);
500 }
501 }
502 )
503 }
504
505 impl_integer_for_isize!(i8, test_integer_i8);
506 impl_integer_for_isize!(i16, test_integer_i16);
507 impl_integer_for_isize!(i32, test_integer_i32);
508 impl_integer_for_isize!(i64, test_integer_i64);
509 impl_integer_for_isize!(isize, test_integer_isize);
510 #[cfg(has_i128)]
511 impl_integer_for_isize!(i128, test_integer_i128);
512
513 macro_rules! impl_integer_for_usize {
514 ($T:ty, $test_mod:ident) => (
515 impl Integer for $T {
516 /// Unsigned integer division. Returns the same result as `div` (`/`).
517 #[inline]
518 fn div_floor(&self, other: &Self) -> Self {
519 *self / *other
520 }
521
522 /// Unsigned integer modulo operation. Returns the same result as `rem` (`%`).
523 #[inline]
524 fn mod_floor(&self, other: &Self) -> Self {
525 *self % *other
526 }
527
528 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`
529 #[inline]
530 fn gcd(&self, other: &Self) -> Self {
531 // Use Stein's algorithm
532 let mut m = *self;
533 let mut n = *other;
534 if m == 0 || n == 0 { return m | n }
535
536 // find common factors of 2
537 let shift = (m | n).trailing_zeros();
538
539 // divide n and m by 2 until odd
540 // m inside loop
541 n >>= n.trailing_zeros();
542
543 while m != 0 {
544 m >>= m.trailing_zeros();
545 if n > m { mem::swap(&mut n, &mut m) }
546 m -= n;
547 }
548
549 n << shift
550 }
551
552 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
553 #[inline]
554 fn lcm(&self, other: &Self) -> Self {
555 *self * (*other / self.gcd(other))
556 }
557
558 /// Deprecated, use `is_multiple_of` instead.
559 #[inline]
560 fn divides(&self, other: &Self) -> bool {
561 self.is_multiple_of(other)
562 }
563
564 /// Returns `true` if the number is a multiple of `other`.
565 #[inline]
566 fn is_multiple_of(&self, other: &Self) -> bool {
567 *self % *other == 0
568 }
569
570 /// Returns `true` if the number is divisible by `2`.
571 #[inline]
572 fn is_even(&self) -> bool {
573 *self % 2 == 0
574 }
575
576 /// Returns `true` if the number is not divisible by `2`.
577 #[inline]
578 fn is_odd(&self) -> bool {
579 !self.is_even()
580 }
581
582 /// Simultaneous truncated integer division and modulus.
583 #[inline]
584 fn div_rem(&self, other: &Self) -> (Self, Self) {
585 (*self / *other, *self % *other)
586 }
587 }
588
589 #[cfg(test)]
590 mod $test_mod {
591 use Integer;
592 use core::mem;
593
594 #[test]
595 fn test_div_mod_floor() {
596 assert_eq!((10 as $T).div_floor(&(3 as $T)), 3 as $T);
597 assert_eq!((10 as $T).mod_floor(&(3 as $T)), 1 as $T);
598 assert_eq!((10 as $T).div_mod_floor(&(3 as $T)), (3 as $T, 1 as $T));
599 assert_eq!((5 as $T).div_floor(&(5 as $T)), 1 as $T);
600 assert_eq!((5 as $T).mod_floor(&(5 as $T)), 0 as $T);
601 assert_eq!((5 as $T).div_mod_floor(&(5 as $T)), (1 as $T, 0 as $T));
602 assert_eq!((3 as $T).div_floor(&(7 as $T)), 0 as $T);
603 assert_eq!((3 as $T).mod_floor(&(7 as $T)), 3 as $T);
604 assert_eq!((3 as $T).div_mod_floor(&(7 as $T)), (0 as $T, 3 as $T));
605 }
606
607 #[test]
608 fn test_gcd() {
609 assert_eq!((10 as $T).gcd(&2), 2 as $T);
610 assert_eq!((10 as $T).gcd(&3), 1 as $T);
611 assert_eq!((0 as $T).gcd(&3), 3 as $T);
612 assert_eq!((3 as $T).gcd(&3), 3 as $T);
613 assert_eq!((56 as $T).gcd(&42), 14 as $T);
614 }
615
616 #[test]
617 fn test_gcd_cmp_with_euclidean() {
618 fn euclidean_gcd(mut m: $T, mut n: $T) -> $T {
619 while m != 0 {
620 mem::swap(&mut m, &mut n);
621 m %= n;
622 }
623 n
624 }
625
626 for i in 0..255 {
627 for j in 0..255 {
628 assert_eq!(euclidean_gcd(i,j), i.gcd(&j));
629 }
630 }
631
632 // last value
633 // FIXME: Use inclusive ranges for above loop when implemented
634 let i = 255;
635 for j in 0..255 {
636 assert_eq!(euclidean_gcd(i,j), i.gcd(&j));
637 }
638 assert_eq!(255.gcd(&255), 255);
639 }
640
641 #[test]
642 fn test_lcm() {
643 assert_eq!((1 as $T).lcm(&0), 0 as $T);
644 assert_eq!((0 as $T).lcm(&1), 0 as $T);
645 assert_eq!((1 as $T).lcm(&1), 1 as $T);
646 assert_eq!((8 as $T).lcm(&9), 72 as $T);
647 assert_eq!((11 as $T).lcm(&5), 55 as $T);
648 assert_eq!((15 as $T).lcm(&17), 255 as $T);
649 }
650
651 #[test]
652 fn test_is_multiple_of() {
653 assert!((6 as $T).is_multiple_of(&(6 as $T)));
654 assert!((6 as $T).is_multiple_of(&(3 as $T)));
655 assert!((6 as $T).is_multiple_of(&(1 as $T)));
656 }
657
658 #[test]
659 fn test_even() {
660 assert_eq!((0 as $T).is_even(), true);
661 assert_eq!((1 as $T).is_even(), false);
662 assert_eq!((2 as $T).is_even(), true);
663 assert_eq!((3 as $T).is_even(), false);
664 assert_eq!((4 as $T).is_even(), true);
665 }
666
667 #[test]
668 fn test_odd() {
669 assert_eq!((0 as $T).is_odd(), false);
670 assert_eq!((1 as $T).is_odd(), true);
671 assert_eq!((2 as $T).is_odd(), false);
672 assert_eq!((3 as $T).is_odd(), true);
673 assert_eq!((4 as $T).is_odd(), false);
674 }
675 }
676 )
677 }
678
679 impl_integer_for_usize!(u8, test_integer_u8);
680 impl_integer_for_usize!(u16, test_integer_u16);
681 impl_integer_for_usize!(u32, test_integer_u32);
682 impl_integer_for_usize!(u64, test_integer_u64);
683 impl_integer_for_usize!(usize, test_integer_usize);
684 #[cfg(has_i128)]
685 impl_integer_for_usize!(u128, test_integer_u128);
686
687 /// An iterator over binomial coefficients.
688 pub struct IterBinomial<T> {
689 a: T,
690 n: T,
691 k: T,
692 }
693
694 impl<T> IterBinomial<T>
695 where T: Integer,
696 {
697 /// For a given n, iterate over all binomial coefficients binomial(n, k), for k=0...n.
698 ///
699 /// Note that this might overflow, depending on `T`. For the primitive
700 /// integer types, the following n are the largest ones for which there will
701 /// be no overflow:
702 ///
703 /// type | n
704 /// -----|---
705 /// u8 | 10
706 /// i8 | 9
707 /// u16 | 18
708 /// i16 | 17
709 /// u32 | 34
710 /// i32 | 33
711 /// u64 | 67
712 /// i64 | 66
713 ///
714 /// For larger n, `T` should be a bigint type.
new(n: T) -> IterBinomial<T>715 pub fn new(n: T) -> IterBinomial<T> {
716 IterBinomial {
717 k: T::zero(), a: T::one(), n: n
718 }
719 }
720 }
721
722 impl<T> Iterator for IterBinomial<T>
723 where T: Integer + Clone
724 {
725 type Item = T;
726
next(&mut self) -> Option<T>727 fn next(&mut self) -> Option<T> {
728 if self.k > self.n {
729 return None;
730 }
731 self.a = if !self.k.is_zero() {
732 multiply_and_divide(
733 self.a.clone(),
734 self.n.clone() - self.k.clone() + T::one(),
735 self.k.clone()
736 )
737 } else {
738 T::one()
739 };
740 self.k = self.k.clone() + T::one();
741 Some(self.a.clone())
742 }
743 }
744
745 /// Calculate r * a / b, avoiding overflows and fractions.
746 ///
747 /// Assumes that b divides r * a evenly.
multiply_and_divide<T: Integer + Clone>(r: T, a: T, b: T) -> T748 fn multiply_and_divide<T: Integer + Clone>(r: T, a: T, b: T) -> T {
749 // See http://blog.plover.com/math/choose-2.html for the idea.
750 let g = gcd(r.clone(), b.clone());
751 r/g.clone() * (a / (b/g))
752 }
753
754 /// Calculate the binomial coefficient.
755 ///
756 /// Note that this might overflow, depending on `T`. For the primitive integer
757 /// types, the following n are the largest ones possible such that there will
758 /// be no overflow for any k:
759 ///
760 /// type | n
761 /// -----|---
762 /// u8 | 10
763 /// i8 | 9
764 /// u16 | 18
765 /// i16 | 17
766 /// u32 | 34
767 /// i32 | 33
768 /// u64 | 67
769 /// i64 | 66
770 ///
771 /// For larger n, consider using a bigint type for `T`.
binomial<T: Integer + Clone>(mut n: T, k: T) -> T772 pub fn binomial<T: Integer + Clone>(mut n: T, k: T) -> T {
773 // See http://blog.plover.com/math/choose.html for the idea.
774 if k > n {
775 return T::zero();
776 }
777 if k > n.clone() - k.clone() {
778 return binomial(n.clone(), n - k);
779 }
780 let mut r = T::one();
781 let mut d = T::one();
782 loop {
783 if d > k {
784 break;
785 }
786 r = multiply_and_divide(r, n.clone(), d.clone());
787 n = n - T::one();
788 d = d + T::one();
789 }
790 r
791 }
792
793 /// Calculate the multinomial coefficient.
multinomial<T: Integer + Clone>(k: &[T]) -> T where for<'a> T: Add<&'a T, Output = T>794 pub fn multinomial<T: Integer + Clone>(k: &[T]) -> T
795 where for<'a> T: Add<&'a T, Output = T>
796 {
797 let mut r = T::one();
798 let mut p = T::zero();
799 for i in k {
800 p = p + i;
801 r = r * binomial(p.clone(), i.clone());
802 }
803 r
804 }
805
806 #[test]
test_lcm_overflow()807 fn test_lcm_overflow() {
808 macro_rules! check {
809 ($t:ty, $x:expr, $y:expr, $r:expr) => { {
810 let x: $t = $x;
811 let y: $t = $y;
812 let o = x.checked_mul(y);
813 assert!(o.is_none(),
814 "sanity checking that {} input {} * {} overflows",
815 stringify!($t), x, y);
816 assert_eq!(x.lcm(&y), $r);
817 assert_eq!(y.lcm(&x), $r);
818 } }
819 }
820
821 // Original bug (Issue #166)
822 check!(i64, 46656000000000000, 600, 46656000000000000);
823
824 check!(i8, 0x40, 0x04, 0x40);
825 check!(u8, 0x80, 0x02, 0x80);
826 check!(i16, 0x40_00, 0x04, 0x40_00);
827 check!(u16, 0x80_00, 0x02, 0x80_00);
828 check!(i32, 0x4000_0000, 0x04, 0x4000_0000);
829 check!(u32, 0x8000_0000, 0x02, 0x8000_0000);
830 check!(i64, 0x4000_0000_0000_0000, 0x04, 0x4000_0000_0000_0000);
831 check!(u64, 0x8000_0000_0000_0000, 0x02, 0x8000_0000_0000_0000);
832 }
833
834 #[test]
test_iter_binomial()835 fn test_iter_binomial() {
836 macro_rules! check_simple {
837 ($t:ty) => { {
838 let n: $t = 3;
839 let expected = [1, 3, 3, 1];
840 for (b, &e) in IterBinomial::new(n).zip(&expected) {
841 assert_eq!(b, e);
842 }
843 } }
844 }
845
846 check_simple!(u8);
847 check_simple!(i8);
848 check_simple!(u16);
849 check_simple!(i16);
850 check_simple!(u32);
851 check_simple!(i32);
852 check_simple!(u64);
853 check_simple!(i64);
854
855 macro_rules! check_binomial {
856 ($t:ty, $n:expr) => { {
857 let n: $t = $n;
858 let mut k: $t = 0;
859 for b in IterBinomial::new(n) {
860 assert_eq!(b, binomial(n, k));
861 k += 1;
862 }
863 } }
864 }
865
866 // Check the largest n for which there is no overflow.
867 check_binomial!(u8, 10);
868 check_binomial!(i8, 9);
869 check_binomial!(u16, 18);
870 check_binomial!(i16, 17);
871 check_binomial!(u32, 34);
872 check_binomial!(i32, 33);
873 check_binomial!(u64, 67);
874 check_binomial!(i64, 66);
875 }
876
877 #[test]
test_binomial()878 fn test_binomial() {
879 macro_rules! check {
880 ($t:ty, $x:expr, $y:expr, $r:expr) => { {
881 let x: $t = $x;
882 let y: $t = $y;
883 let expected: $t = $r;
884 assert_eq!(binomial(x, y), expected);
885 if y <= x {
886 assert_eq!(binomial(x, x - y), expected);
887 }
888 } }
889 }
890 check!(u8, 9, 4, 126);
891 check!(u8, 0, 0, 1);
892 check!(u8, 2, 3, 0);
893
894 check!(i8, 9, 4, 126);
895 check!(i8, 0, 0, 1);
896 check!(i8, 2, 3, 0);
897
898 check!(u16, 100, 2, 4950);
899 check!(u16, 14, 4, 1001);
900 check!(u16, 0, 0, 1);
901 check!(u16, 2, 3, 0);
902
903 check!(i16, 100, 2, 4950);
904 check!(i16, 14, 4, 1001);
905 check!(i16, 0, 0, 1);
906 check!(i16, 2, 3, 0);
907
908 check!(u32, 100, 2, 4950);
909 check!(u32, 35, 11, 417225900);
910 check!(u32, 14, 4, 1001);
911 check!(u32, 0, 0, 1);
912 check!(u32, 2, 3, 0);
913
914 check!(i32, 100, 2, 4950);
915 check!(i32, 35, 11, 417225900);
916 check!(i32, 14, 4, 1001);
917 check!(i32, 0, 0, 1);
918 check!(i32, 2, 3, 0);
919
920 check!(u64, 100, 2, 4950);
921 check!(u64, 35, 11, 417225900);
922 check!(u64, 14, 4, 1001);
923 check!(u64, 0, 0, 1);
924 check!(u64, 2, 3, 0);
925
926 check!(i64, 100, 2, 4950);
927 check!(i64, 35, 11, 417225900);
928 check!(i64, 14, 4, 1001);
929 check!(i64, 0, 0, 1);
930 check!(i64, 2, 3, 0);
931 }
932
933 #[test]
test_multinomial()934 fn test_multinomial() {
935 macro_rules! check_binomial {
936 ($t:ty, $k:expr) => { {
937 let n: $t = $k.iter().fold(0, |acc, &x| acc + x);
938 let k: &[$t] = $k;
939 assert_eq!(k.len(), 2);
940 assert_eq!(multinomial(k), binomial(n, k[0]));
941 } }
942 }
943
944 check_binomial!(u8, &[4, 5]);
945
946 check_binomial!(i8, &[4, 5]);
947
948 check_binomial!(u16, &[2, 98]);
949 check_binomial!(u16, &[4, 10]);
950
951 check_binomial!(i16, &[2, 98]);
952 check_binomial!(i16, &[4, 10]);
953
954 check_binomial!(u32, &[2, 98]);
955 check_binomial!(u32, &[11, 24]);
956 check_binomial!(u32, &[4, 10]);
957
958 check_binomial!(i32, &[2, 98]);
959 check_binomial!(i32, &[11, 24]);
960 check_binomial!(i32, &[4, 10]);
961
962 check_binomial!(u64, &[2, 98]);
963 check_binomial!(u64, &[11, 24]);
964 check_binomial!(u64, &[4, 10]);
965
966 check_binomial!(i64, &[2, 98]);
967 check_binomial!(i64, &[11, 24]);
968 check_binomial!(i64, &[4, 10]);
969
970 macro_rules! check_multinomial {
971 ($t:ty, $k:expr, $r:expr) => { {
972 let k: &[$t] = $k;
973 let expected: $t = $r;
974 assert_eq!(multinomial(k), expected);
975 } }
976 }
977
978 check_multinomial!(u8, &[2, 1, 2], 30);
979 check_multinomial!(u8, &[2, 3, 0], 10);
980
981 check_multinomial!(i8, &[2, 1, 2], 30);
982 check_multinomial!(i8, &[2, 3, 0], 10);
983
984 check_multinomial!(u16, &[2, 1, 2], 30);
985 check_multinomial!(u16, &[2, 3, 0], 10);
986
987 check_multinomial!(i16, &[2, 1, 2], 30);
988 check_multinomial!(i16, &[2, 3, 0], 10);
989
990 check_multinomial!(u32, &[2, 1, 2], 30);
991 check_multinomial!(u32, &[2, 3, 0], 10);
992
993 check_multinomial!(i32, &[2, 1, 2], 30);
994 check_multinomial!(i32, &[2, 3, 0], 10);
995
996 check_multinomial!(u64, &[2, 1, 2], 30);
997 check_multinomial!(u64, &[2, 3, 0], 10);
998
999 check_multinomial!(i64, &[2, 1, 2], 30);
1000 check_multinomial!(i64, &[2, 3, 0], 10);
1001
1002 check_multinomial!(u64, &[], 1);
1003 check_multinomial!(u64, &[0], 1);
1004 check_multinomial!(u64, &[12345], 1);
1005 }
1006