src/libnum/lib.rs

   1 // Copyright 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 #![feature(macro_rules)]
  12
  13 #![crate_id = "num#0.10-pre"]
  14 #![crate_type = "rlib"]
  15 #![crate_type = "dylib"]
  16 #![license = "MIT/ASL2"]
  17 #![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
  18        html_favicon_url = "http://www.rust-lang.org/favicon.ico",
  19        html_root_url = "http://static.rust-lang.org/doc/master")]
  20
  21 #![deny(deprecated_owned_vector)]
  22
  23 extern crate rand;
  24
  25 pub mod bigint;
  26 pub mod rational;
  27 pub mod complex;
  28
  29 pub trait Integer: Num + Ord
  30                  + Div<Self, Self>
  31                  + Rem<Self, Self> {
  32     /// Simultaneous truncated integer division and modulus
  33     #[inline]
  34     fn div_rem(&self, other: &Self) -> (Self, Self) {
  35         (*self / *other, *self % *other)
  36     }
  37
  38     /// Floored integer division
  39     ///
  40     /// # Examples
  41     ///
  42     /// ~~~
  43     /// # use num::Integer;
  44     /// assert!(( 8i).div_floor(& 3) ==  2);
  45     /// assert!(( 8i).div_floor(&-3) == -3);
  46     /// assert!((-8i).div_floor(& 3) == -3);
  47     /// assert!((-8i).div_floor(&-3) ==  2);
  48     ///
  49     /// assert!(( 1i).div_floor(& 2) ==  0);
  50     /// assert!(( 1i).div_floor(&-2) == -1);
  51     /// assert!((-1i).div_floor(& 2) == -1);
  52     /// assert!((-1i).div_floor(&-2) ==  0);
  53     /// ~~~
  54     fn div_floor(&self, other: &Self) -> Self;
  55
  56     /// Floored integer modulo, satisfying:
  57     ///
  58     /// ~~~
  59     /// # use num::Integer;
  60     /// # let n = 1i; let d = 1i;
  61     /// assert!(n.div_floor(&d) * d + n.mod_floor(&d) == n)
  62     /// ~~~
  63     ///
  64     /// # Examples
  65     ///
  66     /// ~~~
  67     /// # use num::Integer;
  68     /// assert!(( 8i).mod_floor(& 3) ==  2);
  69     /// assert!(( 8i).mod_floor(&-3) == -1);
  70     /// assert!((-8i).mod_floor(& 3) ==  1);
  71     /// assert!((-8i).mod_floor(&-3) == -2);
  72     ///
  73     /// assert!(( 1i).mod_floor(& 2) ==  1);
  74     /// assert!(( 1i).mod_floor(&-2) == -1);
  75     /// assert!((-1i).mod_floor(& 2) ==  1);
  76     /// assert!((-1i).mod_floor(&-2) == -1);
  77     /// ~~~
  78     fn mod_floor(&self, other: &Self) -> Self;
  79
  80     /// Simultaneous floored integer division and modulus
  81     fn div_mod_floor(&self, other: &Self) -> (Self, Self) {
  82         (self.div_floor(other), self.mod_floor(other))
  83     }
  84
  85     /// Greatest Common Divisor (GCD)
  86     fn gcd(&self, other: &Self) -> Self;
  87
  88     /// Lowest Common Multiple (LCM)
  89     fn lcm(&self, other: &Self) -> Self;
  90
  91     /// Returns `true` if `other` divides evenly into `self`
  92     fn divides(&self, other: &Self) -> bool;
  93
  94     /// Returns `true` if the number is even
  95     fn is_even(&self) -> bool;
  96
  97     /// Returns `true` if the number is odd
  98     fn is_odd(&self) -> bool;
  99 }
 100
 101 /// Simultaneous integer division and modulus
 102 #[inline] pub fn div_rem<T: Integer>(x: T, y: T) -> (T, T) { x.div_rem(&y) }
 103 /// Floored integer division
 104 #[inline] pub fn div_floor<T: Integer>(x: T, y: T) -> T { x.div_floor(&y) }
 105 /// Floored integer modulus
 106 #[inline] pub fn mod_floor<T: Integer>(x: T, y: T) -> T { x.mod_floor(&y) }
 107 /// Simultaneous floored integer division and modulus
 108 #[inline] pub fn div_mod_floor<T: Integer>(x: T, y: T) -> (T, T) { x.div_mod_floor(&y) }
 109
 110 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`. The
 111 /// result is always positive.
 112 #[inline(always)] pub fn gcd<T: Integer>(x: T, y: T) -> T { x.gcd(&y) }
 113 /// Calculates the Lowest Common Multiple (LCM) of the number and `other`.
 114 #[inline(always)] pub fn lcm<T: Integer>(x: T, y: T) -> T { x.lcm(&y) }
 115
 116 macro_rules! impl_integer_for_int {
 117     ($T:ty, $test_mod:ident) => (
 118         impl Integer for $T {
 119             /// Floored integer division
 120             #[inline]
 121             fn div_floor(&self, other: &$T) -> $T {
 122                 // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
 123                 // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
 124                 match self.div_rem(other) {
 125                     (d, r) if (r > 0 && *other < 0)
 126                            || (r < 0 && *other > 0) => d - 1,
 127                     (d, _)                          => d,
 128                 }
 129             }
 130
 131             /// Floored integer modulo
 132             #[inline]
 133             fn mod_floor(&self, other: &$T) -> $T {
 134                 // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
 135                 // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
 136                 match *self % *other {
 137                     r if (r > 0 && *other < 0)
 138                       || (r < 0 && *other > 0) => r + *other,
 139                     r                          => r,
 140                 }
 141             }
 142
 143             /// Calculates `div_floor` and `mod_floor` simultaneously
 144             #[inline]
 145             fn div_mod_floor(&self, other: &$T) -> ($T,$T) {
 146                 // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
 147                 // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
 148                 match self.div_rem(other) {
 149                     (d, r) if (r > 0 && *other < 0)
 150                            || (r < 0 && *other > 0) => (d - 1, r + *other),
 151                     (d, r)                          => (d, r),
 152                 }
 153             }
 154
 155             /// Calculates the Greatest Common Divisor (GCD) of the number and
 156             /// `other`. The result is always positive.
 157             #[inline]
 158             fn gcd(&self, other: &$T) -> $T {
 159                 // Use Euclid's algorithm
 160                 let mut m = *self;
 161                 let mut n = *other;
 162                 while m != 0 {
 163                     let temp = m;
 164                     m = n % temp;
 165                     n = temp;
 166                 }
 167                 n.abs()
 168             }
 169
 170             /// Calculates the Lowest Common Multiple (LCM) of the number and
 171             /// `other`.
 172             #[inline]
 173             fn lcm(&self, other: &$T) -> $T {
 174                 // should not have to recaluculate abs
 175                 ((*self * *other) / self.gcd(other)).abs()
 176             }
 177
 178             /// Returns `true` if the number can be divided by `other` without
 179             /// leaving a remainder
 180             #[inline]
 181             fn divides(&self, other: &$T) -> bool { *self % *other == 0 }
 182
 183             /// Returns `true` if the number is divisible by `2`
 184             #[inline]
 185             fn is_even(&self) -> bool { self & 1 == 0 }
 186
 187             /// Returns `true` if the number is not divisible by `2`
 188             #[inline]
 189             fn is_odd(&self) -> bool { !self.is_even() }
 190         }
 191
 192         #[cfg(test)]
 193         mod $test_mod {
 194             use Integer;
 195
 196             /// Checks that the division rule holds for:
 197             ///
 198             /// - `n`: numerator (dividend)
 199             /// - `d`: denominator (divisor)
 200             /// - `qr`: quotient and remainder
 201             #[cfg(test)]
 202             fn test_division_rule((n,d): ($T,$T), (q,r): ($T,$T)) {
 203                 assert_eq!(d * q + r, n);
 204             }
 205
 206             #[test]
 207             fn test_div_rem() {
 208                 fn test_nd_dr(nd: ($T,$T), qr: ($T,$T)) {
 209                     let (n,d) = nd;
 210                     let separate_div_rem = (n / d, n % d);
 211                     let combined_div_rem = n.div_rem(&d);
 212
 213                     assert_eq!(separate_div_rem, qr);
 214                     assert_eq!(combined_div_rem, qr);
 215
 216                     test_division_rule(nd, separate_div_rem);
 217                     test_division_rule(nd, combined_div_rem);
 218                 }
 219
 220                 test_nd_dr(( 8,  3), ( 2,  2));
 221                 test_nd_dr(( 8, -3), (-2,  2));
 222                 test_nd_dr((-8,  3), (-2, -2));
 223                 test_nd_dr((-8, -3), ( 2, -2));
 224
 225                 test_nd_dr(( 1,  2), ( 0,  1));
 226                 test_nd_dr(( 1, -2), ( 0,  1));
 227                 test_nd_dr((-1,  2), ( 0, -1));
 228                 test_nd_dr((-1, -2), ( 0, -1));
 229             }
 230
 231             #[test]
 232             fn test_div_mod_floor() {
 233                 fn test_nd_dm(nd: ($T,$T), dm: ($T,$T)) {
 234                     let (n,d) = nd;
 235                     let separate_div_mod_floor = (n.div_floor(&d), n.mod_floor(&d));
 236                     let combined_div_mod_floor = n.div_mod_floor(&d);
 237
 238                     assert_eq!(separate_div_mod_floor, dm);
 239                     assert_eq!(combined_div_mod_floor, dm);
 240
 241                     test_division_rule(nd, separate_div_mod_floor);
 242                     test_division_rule(nd, combined_div_mod_floor);
 243                 }
 244
 245                 test_nd_dm(( 8,  3), ( 2,  2));
 246                 test_nd_dm(( 8, -3), (-3, -1));
 247                 test_nd_dm((-8,  3), (-3,  1));
 248                 test_nd_dm((-8, -3), ( 2, -2));
 249
 250                 test_nd_dm(( 1,  2), ( 0,  1));
 251                 test_nd_dm(( 1, -2), (-1, -1));
 252                 test_nd_dm((-1,  2), (-1,  1));
 253                 test_nd_dm((-1, -2), ( 0, -1));
 254             }
 255
 256             #[test]
 257             fn test_gcd() {
 258                 assert_eq!((10 as $T).gcd(&2), 2 as $T);
 259                 assert_eq!((10 as $T).gcd(&3), 1 as $T);
 260                 assert_eq!((0 as $T).gcd(&3), 3 as $T);
 261                 assert_eq!((3 as $T).gcd(&3), 3 as $T);
 262                 assert_eq!((56 as $T).gcd(&42), 14 as $T);
 263                 assert_eq!((3 as $T).gcd(&-3), 3 as $T);
 264                 assert_eq!((-6 as $T).gcd(&3), 3 as $T);
 265                 assert_eq!((-4 as $T).gcd(&-2), 2 as $T);
 266             }
 267
 268             #[test]
 269             fn test_lcm() {
 270                 assert_eq!((1 as $T).lcm(&0), 0 as $T);
 271                 assert_eq!((0 as $T).lcm(&1), 0 as $T);
 272                 assert_eq!((1 as $T).lcm(&1), 1 as $T);
 273                 assert_eq!((-1 as $T).lcm(&1), 1 as $T);
 274                 assert_eq!((1 as $T).lcm(&-1), 1 as $T);
 275                 assert_eq!((-1 as $T).lcm(&-1), 1 as $T);
 276                 assert_eq!((8 as $T).lcm(&9), 72 as $T);
 277                 assert_eq!((11 as $T).lcm(&5), 55 as $T);
 278             }
 279
 280             #[test]
 281             fn test_even() {
 282                 assert_eq!((-4 as $T).is_even(), true);
 283                 assert_eq!((-3 as $T).is_even(), false);
 284                 assert_eq!((-2 as $T).is_even(), true);
 285                 assert_eq!((-1 as $T).is_even(), false);
 286                 assert_eq!((0 as $T).is_even(), true);
 287                 assert_eq!((1 as $T).is_even(), false);
 288                 assert_eq!((2 as $T).is_even(), true);
 289                 assert_eq!((3 as $T).is_even(), false);
 290                 assert_eq!((4 as $T).is_even(), true);
 291             }
 292
 293             #[test]
 294             fn test_odd() {
 295                 assert_eq!((-4 as $T).is_odd(), false);
 296                 assert_eq!((-3 as $T).is_odd(), true);
 297                 assert_eq!((-2 as $T).is_odd(), false);
 298                 assert_eq!((-1 as $T).is_odd(), true);
 299                 assert_eq!((0 as $T).is_odd(), false);
 300                 assert_eq!((1 as $T).is_odd(), true);
 301                 assert_eq!((2 as $T).is_odd(), false);
 302                 assert_eq!((3 as $T).is_odd(), true);
 303                 assert_eq!((4 as $T).is_odd(), false);
 304             }
 305         }
 306     )
 307 }
 308
 309 impl_integer_for_int!(i8,   test_integer_i8)
 310 impl_integer_for_int!(i16,  test_integer_i16)
 311 impl_integer_for_int!(i32,  test_integer_i32)
 312 impl_integer_for_int!(i64,  test_integer_i64)
 313 impl_integer_for_int!(int,  test_integer_int)
 314
 315 macro_rules! impl_integer_for_uint {
 316     ($T:ty, $test_mod:ident) => (
 317         impl Integer for $T {
 318             /// Unsigned integer division. Returns the same result as `div` (`/`).
 319             #[inline]
 320             fn div_floor(&self, other: &$T) -> $T { *self / *other }
 321
 322             /// Unsigned integer modulo operation. Returns the same result as `rem` (`%`).
 323             #[inline]
 324             fn mod_floor(&self, other: &$T) -> $T { *self % *other }
 325
 326             /// Calculates the Greatest Common Divisor (GCD) of the number and `other`
 327             #[inline]
 328             fn gcd(&self, other: &$T) -> $T {
 329                 // Use Euclid's algorithm
 330                 let mut m = *self;
 331                 let mut n = *other;
 332                 while m != 0 {
 333                     let temp = m;
 334                     m = n % temp;
 335                     n = temp;
 336                 }
 337                 n
 338             }
 339
 340             /// Calculates the Lowest Common Multiple (LCM) of the number and `other`
 341             #[inline]
 342             fn lcm(&self, other: &$T) -> $T {
 343                 (*self * *other) / self.gcd(other)
 344             }
 345
 346             /// Returns `true` if the number can be divided by `other` without leaving a remainder
 347             #[inline]
 348             fn divides(&self, other: &$T) -> bool { *self % *other == 0 }
 349
 350             /// Returns `true` if the number is divisible by `2`
 351             #[inline]
 352             fn is_even(&self) -> bool { self & 1 == 0 }
 353
 354             /// Returns `true` if the number is not divisible by `2`
 355             #[inline]
 356             fn is_odd(&self) -> bool { !self.is_even() }
 357         }
 358
 359         #[cfg(test)]
 360         mod $test_mod {
 361             use Integer;
 362
 363             #[test]
 364             fn test_div_mod_floor() {
 365                 assert_eq!((10 as $T).div_floor(&(3 as $T)), 3 as $T);
 366                 assert_eq!((10 as $T).mod_floor(&(3 as $T)), 1 as $T);
 367                 assert_eq!((10 as $T).div_mod_floor(&(3 as $T)), (3 as $T, 1 as $T));
 368                 assert_eq!((5 as $T).div_floor(&(5 as $T)), 1 as $T);
 369                 assert_eq!((5 as $T).mod_floor(&(5 as $T)), 0 as $T);
 370                 assert_eq!((5 as $T).div_mod_floor(&(5 as $T)), (1 as $T, 0 as $T));
 371                 assert_eq!((3 as $T).div_floor(&(7 as $T)), 0 as $T);
 372                 assert_eq!((3 as $T).mod_floor(&(7 as $T)), 3 as $T);
 373                 assert_eq!((3 as $T).div_mod_floor(&(7 as $T)), (0 as $T, 3 as $T));
 374             }
 375
 376             #[test]
 377             fn test_gcd() {
 378                 assert_eq!((10 as $T).gcd(&2), 2 as $T);
 379                 assert_eq!((10 as $T).gcd(&3), 1 as $T);
 380                 assert_eq!((0 as $T).gcd(&3), 3 as $T);
 381                 assert_eq!((3 as $T).gcd(&3), 3 as $T);
 382                 assert_eq!((56 as $T).gcd(&42), 14 as $T);
 383             }
 384
 385             #[test]
 386             fn test_lcm() {
 387                 assert_eq!((1 as $T).lcm(&0), 0 as $T);
 388                 assert_eq!((0 as $T).lcm(&1), 0 as $T);
 389                 assert_eq!((1 as $T).lcm(&1), 1 as $T);
 390                 assert_eq!((8 as $T).lcm(&9), 72 as $T);
 391                 assert_eq!((11 as $T).lcm(&5), 55 as $T);
 392                 assert_eq!((99 as $T).lcm(&17), 1683 as $T);
 393             }
 394
 395             #[test]
 396             fn test_divides() {
 397                 assert!((6 as $T).divides(&(6 as $T)));
 398                 assert!((6 as $T).divides(&(3 as $T)));
 399                 assert!((6 as $T).divides(&(1 as $T)));
 400             }
 401
 402             #[test]
 403             fn test_even() {
 404                 assert_eq!((0 as $T).is_even(), true);
 405                 assert_eq!((1 as $T).is_even(), false);
 406                 assert_eq!((2 as $T).is_even(), true);
 407                 assert_eq!((3 as $T).is_even(), false);
 408                 assert_eq!((4 as $T).is_even(), true);
 409             }
 410
 411             #[test]
 412             fn test_odd() {
 413                 assert_eq!((0 as $T).is_odd(), false);
 414                 assert_eq!((1 as $T).is_odd(), true);
 415                 assert_eq!((2 as $T).is_odd(), false);
 416                 assert_eq!((3 as $T).is_odd(), true);
 417                 assert_eq!((4 as $T).is_odd(), false);
 418             }
 419         }
 420     )
 421 }
 422
 423 impl_integer_for_uint!(u8,   test_integer_u8)
 424 impl_integer_for_uint!(u16,  test_integer_u16)
 425 impl_integer_for_uint!(u32,  test_integer_u32)
 426 impl_integer_for_uint!(u64,  test_integer_u64)
 427 impl_integer_for_uint!(uint, test_integer_uint)