(index<- ) ./libnum/lib.rs
git branch: * master 5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
modified: Fri Apr 25 22:40:04 2014
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.11-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 recalculate 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)