(index<- ) ./libstd/rand/mod.rs
1 // Copyright 2013 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 /*!
12 Random number generation.
13
14 The key functions are `random()` and `Rng::gen()`. These are polymorphic
15 and so can be used to generate any type that implements `Rand`. Type inference
16 means that often a simple call to `rand::random()` or `rng.gen()` will
17 suffice, but sometimes an annotation is required, e.g. `rand::random::<f64>()`.
18
19 See the `distributions` submodule for sampling random numbers from
20 distributions like normal and exponential.
21
22 # Task-local RNG
23
24 There is built-in support for a RNG associated with each task stored
25 in task-local storage. This RNG can be accessed via `task_rng`, or
26 used implicitly via `random`. This RNG is normally randomly seeded
27 from an operating-system source of randomness, e.g. `/dev/urandom` on
28 Unix systems, and will automatically reseed itself from this source
29 after generating 32 KiB of random data.
30
31 # Examples
32
33 ```rust
34 use std::rand;
35 use std::rand::Rng;
36
37 fn main() {
38 let mut rng = rand::rng();
39 if rng.gen() { // bool
40 println!("int: {}, uint: {}", rng.gen::<int>(), rng.gen::<uint>())
41 }
42 }
43 ```
44
45 ```rust
46 use std::rand;
47
48 fn main () {
49 let tuple_ptr = rand::random::<~(f64, char)>();
50 println!(tuple_ptr)
51 }
52 ```
53 */
54
55 use sys::size_of;
56 use unstable::raw::Slice;
57 use cast;
58 use container::Container;
59 use iter::{Iterator, range};
60 use local_data;
61 use prelude::*;
62 use str;
63 use u64;
64 use vec;
65
66 pub use self::isaac::{IsaacRng, Isaac64Rng};
67 pub use self::os::OSRng;
68
69 pub mod distributions;
70 pub mod isaac;
71 pub mod os;
72 pub mod reader;
73 pub mod reseeding;
74 mod rand_impls;
75
76 /// A type that can be randomly generated using an Rng
77 pub trait Rand {
78 /// Generates a random instance of this type using the specified source of
79 /// randomness
80 fn rand<R: Rng>(rng: &mut R) -> Self;
81 }
82
83 /// A value with a particular weight compared to other values
84 pub struct Weighted<T> {
85 /// The numerical weight of this item
86 weight: uint,
87 /// The actual item which is being weighted
88 item: T,
89 }
90
91 /// A random number generator
92 pub trait Rng {
93 /// Return the next random u32. This rarely needs to be called
94 /// directly, prefer `r.gen()` to `r.next_u32()`.
95 ///
96 // FIXME #7771: Should be implemented in terms of next_u64
97 fn next_u32(&mut self) -> u32;
98
99 /// Return the next random u64. This rarely needs to be called
100 /// directly, prefer `r.gen()` to `r.next_u64()`.
101 ///
102 /// By default this is implemented in terms of `next_u32`. An
103 /// implementation of this trait must provide at least one of
104 /// these two methods.
105 fn next_u64(&mut self) -> u64 {
106 (self.next_u32() as u64 << 32) | (self.next_u32() as u64)
107 }
108
109 /// Fill `dest` with random data.
110 ///
111 /// This has a default implementation in terms of `next_u64` and
112 /// `next_u32`, but should be overriden by implementations that
113 /// offer a more efficient solution than just calling those
114 /// methods repeatedly.
115 ///
116 /// This method does *not* have a requirement to bear any fixed
117 /// relationship to the other methods, for example, it does *not*
118 /// have to result in the same output as progressively filling
119 /// `dest` with `self.gen::<u8>()`, and any such behaviour should
120 /// not be relied upon.
121 ///
122 /// This method should guarantee that `dest` is entirely filled
123 /// with new data, and may fail if this is impossible
124 /// (e.g. reading past the end of a file that is being used as the
125 /// source of randomness).
126 ///
127 /// # Example
128 ///
129 /// ```rust
130 /// use std::rand::{task_rng, Rng};
131 ///
132 /// fn main() {
133 /// let mut v = [0u8, .. 13579];
134 /// task_rng().fill_bytes(v);
135 /// println!("{:?}", v);
136 /// }
137 /// ```
138 fn fill_bytes(&mut self, dest: &mut [u8]) {
139 let mut slice: Slice<u64> = unsafe { cast::transmute_copy(&dest) };
140 slice.len /= size_of::<u64>();
141 let as_u64: &mut [u64] = unsafe { cast::transmute(slice) };
142 for dest in as_u64.mut_iter() {
143 *dest = self.next_u64();
144 }
145
146 // the above will have filled up the vector as much as
147 // possible in multiples of 8 bytes.
148 let mut remaining = dest.len() % 8;
149
150 // space for a u32
151 if remaining >= 4 {
152 let mut slice: Slice<u32> = unsafe { cast::transmute_copy(&dest) };
153 slice.len /= size_of::<u32>();
154 let as_u32: &mut [u32] = unsafe { cast::transmute(slice) };
155 as_u32[as_u32.len() - 1] = self.next_u32();
156 remaining -= 4;
157 }
158 // exactly filled
159 if remaining == 0 { return }
160
161 // now we know we've either got 1, 2 or 3 spots to go,
162 // i.e. exactly one u32 is enough.
163 let rand = self.next_u32();
164 let remaining_index = dest.len() - remaining;
165 match dest.mut_slice_from(remaining_index) {
166 [ref mut a] => {
167 *a = rand as u8;
168 }
169 [ref mut a, ref mut b] => {
170 *a = rand as u8;
171 *b = (rand >> 8) as u8;
172 }
173 [ref mut a, ref mut b, ref mut c] => {
174 *a = rand as u8;
175 *b = (rand >> 8) as u8;
176 *c = (rand >> 16) as u8;
177 }
178 _ => fail2!("Rng.fill_bytes: the impossible occurred: remaining != 1, 2 or 3")
179 }
180 }
181
182 /// Return a random value of a Rand type.
183 ///
184 /// # Example
185 ///
186 /// ```rust
187 /// use std::rand;
188 /// use std::rand::Rng;
189 ///
190 /// fn main() {
191 /// let mut rng = rand::task_rng();
192 /// let x: uint = rng.gen();
193 /// println!("{}", x);
194 /// println!("{:?}", rng.gen::<(f64, bool)>());
195 /// }
196 /// ```
197 #[inline(always)]
198 fn gen<T: Rand>(&mut self) -> T {
199 Rand::rand(self)
200 }
201
202 /// Return a random vector of the specified length.
203 ///
204 /// # Example
205 ///
206 /// ```rust
207 /// use std::rand;
208 /// use std::rand::Rng;
209 ///
210 /// fn main() {
211 /// let mut rng = rand::task_rng();
212 /// let x: ~[uint] = rng.gen_vec(10);
213 /// println!("{:?}", x);
214 /// println!("{:?}", rng.gen_vec::<(f64, bool)>(5));
215 /// }
216 /// ```
217 fn gen_vec<T: Rand>(&mut self, len: uint) -> ~[T] {
218 vec::from_fn(len, |_| self.gen())
219 }
220
221 /// Generate a random primitive integer in the range [`low`,
222 /// `high`). Fails if `low >= high`.
223 ///
224 /// This gives a uniform distribution (assuming this RNG is itself
225 /// uniform), even for edge cases like `gen_integer_range(0u8,
226 /// 170)`, which a naive modulo operation would return numbers
227 /// less than 85 with double the probability to those greater than
228 /// 85.
229 ///
230 /// # Example
231 ///
232 /// ```rust
233 /// use std::rand;
234 /// use std::rand::Rng;
235 ///
236 /// fn main() {
237 /// let mut rng = rand::task_rng();
238 /// let n: uint = rng.gen_integer_range(0u, 10);
239 /// println!("{}", n);
240 /// let m: int = rng.gen_integer_range(-40, 400);
241 /// println!("{}", m);
242 /// }
243 /// ```
244 fn gen_integer_range<T: Rand + Int>(&mut self, low: T, high: T) -> T {
245 assert!(low < high, "RNG.gen_integer_range called with low >= high");
246 let range = (high - low).to_u64().unwrap();
247 let accept_zone = u64::max_value - u64::max_value % range;
248 loop {
249 let rand = self.gen::<u64>();
250 if rand < accept_zone {
251 return low + NumCast::from(rand % range).unwrap();
252 }
253 }
254 }
255
256 /// Return a bool with a 1 in n chance of true
257 ///
258 /// # Example
259 ///
260 /// ```rust
261 /// use std::rand;
262 /// use std::rand::Rng;
263 ///
264 /// fn main() {
265 /// let mut rng = rand::rng();
266 /// println!("{:b}", rng.gen_weighted_bool(3));
267 /// }
268 /// ```
269 fn gen_weighted_bool(&mut self, n: uint) -> bool {
270 n == 0 || self.gen_integer_range(0, n) == 0
271 }
272
273 /// Return a random string of the specified length composed of
274 /// A-Z,a-z,0-9.
275 ///
276 /// # Example
277 ///
278 /// ```rust
279 /// use std::rand;
280 /// use std::rand::Rng;
281 ///
282 /// fn main() {
283 /// println(rand::task_rng().gen_ascii_str(10));
284 /// }
285 /// ```
286 fn gen_ascii_str(&mut self, len: uint) -> ~str {
287 static GEN_ASCII_STR_CHARSET: &'static [u8] = bytes!("ABCDEFGHIJKLMNOPQRSTUVWXYZ\
288 abcdefghijklmnopqrstuvwxyz\
289 0123456789");
290 let mut s = str::with_capacity(len);
291 for _ in range(0, len) {
292 s.push_char(self.choose(GEN_ASCII_STR_CHARSET) as char)
293 }
294 s
295 }
296
297 /// Choose an item randomly, failing if `values` is empty.
298 fn choose<T: Clone>(&mut self, values: &[T]) -> T {
299 self.choose_option(values).expect("Rng.choose: `values` is empty").clone()
300 }
301
302 /// Choose `Some(&item)` randomly, returning `None` if values is
303 /// empty.
304 ///
305 /// # Example
306 ///
307 /// ```rust
308 /// use std::rand;
309 /// use std::rand::Rng;
310 ///
311 /// fn main() {
312 /// println!("{:?}", rand::task_rng().choose_option([1,2,4,8,16,32]));
313 /// println!("{:?}", rand::task_rng().choose_option([]));
314 /// }
315 /// ```
316 fn choose_option<'a, T>(&mut self, values: &'a [T]) -> Option<&'a T> {
317 if values.is_empty() {
318 None
319 } else {
320 Some(&values[self.gen_integer_range(0u, values.len())])
321 }
322 }
323
324 /// Choose an item respecting the relative weights, failing if the sum of
325 /// the weights is 0
326 ///
327 /// # Example
328 ///
329 /// ```rust
330 /// use std::rand;
331 /// use std::rand::Rng;
332 ///
333 /// fn main() {
334 /// let mut rng = rand::rng();
335 /// let x = [rand::Weighted {weight: 4, item: 'a'},
336 /// rand::Weighted {weight: 2, item: 'b'},
337 /// rand::Weighted {weight: 2, item: 'c'}];
338 /// println!("{}", rng.choose_weighted(x));
339 /// }
340 /// ```
341 fn choose_weighted<T:Clone>(&mut self, v: &[Weighted<T>]) -> T {
342 self.choose_weighted_option(v).expect("Rng.choose_weighted: total weight is 0")
343 }
344
345 /// Choose Some(item) respecting the relative weights, returning none if
346 /// the sum of the weights is 0
347 ///
348 /// # Example
349 ///
350 /// ```rust
351 /// use std::rand;
352 /// use std::rand::Rng;
353 ///
354 /// fn main() {
355 /// let mut rng = rand::rng();
356 /// let x = [rand::Weighted {weight: 4, item: 'a'},
357 /// rand::Weighted {weight: 2, item: 'b'},
358 /// rand::Weighted {weight: 2, item: 'c'}];
359 /// println!("{:?}", rng.choose_weighted_option(x));
360 /// }
361 /// ```
362 fn choose_weighted_option<T:Clone>(&mut self, v: &[Weighted<T>])
363 -> Option<T> {
364 let mut total = 0u;
365 for item in v.iter() {
366 total += item.weight;
367 }
368 if total == 0u {
369 return None;
370 }
371 let chosen = self.gen_integer_range(0u, total);
372 let mut so_far = 0u;
373 for item in v.iter() {
374 so_far += item.weight;
375 if so_far > chosen {
376 return Some(item.item.clone());
377 }
378 }
379 unreachable!();
380 }
381
382 /// Return a vec containing copies of the items, in order, where
383 /// the weight of the item determines how many copies there are
384 ///
385 /// # Example
386 ///
387 /// ```rust
388 /// use std::rand;
389 /// use std::rand::Rng;
390 ///
391 /// fn main() {
392 /// let mut rng = rand::rng();
393 /// let x = [rand::Weighted {weight: 4, item: 'a'},
394 /// rand::Weighted {weight: 2, item: 'b'},
395 /// rand::Weighted {weight: 2, item: 'c'}];
396 /// println!("{}", rng.weighted_vec(x));
397 /// }
398 /// ```
399 fn weighted_vec<T:Clone>(&mut self, v: &[Weighted<T>]) -> ~[T] {
400 let mut r = ~[];
401 for item in v.iter() {
402 for _ in range(0u, item.weight) {
403 r.push(item.item.clone());
404 }
405 }
406 r
407 }
408
409 /// Shuffle a vec
410 ///
411 /// # Example
412 ///
413 /// ```rust
414 /// use std::rand;
415 /// use std::rand::Rng;
416 ///
417 /// fn main() {
418 /// println!("{:?}", rand::task_rng().shuffle(~[1,2,3]));
419 /// }
420 /// ```
421 fn shuffle<T>(&mut self, values: ~[T]) -> ~[T] {
422 let mut v = values;
423 self.shuffle_mut(v);
424 v
425 }
426
427 /// Shuffle a mutable vector in place.
428 ///
429 /// # Example
430 ///
431 /// ```rust
432 /// use std::rand;
433 /// use std::rand::Rng;
434 ///
435 /// fn main() {
436 /// let mut rng = rand::task_rng();
437 /// let mut y = [1,2,3];
438 /// rng.shuffle_mut(y);
439 /// println!("{:?}", y);
440 /// rng.shuffle_mut(y);
441 /// println!("{:?}", y);
442 /// }
443 /// ```
444 fn shuffle_mut<T>(&mut self, values: &mut [T]) {
445 let mut i = values.len();
446 while i >= 2u {
447 // invariant: elements with index >= i have been locked in place.
448 i -= 1u;
449 // lock element i in place.
450 values.swap(i, self.gen_integer_range(0u, i + 1u));
451 }
452 }
453
454 /// Randomly sample up to `n` elements from an iterator.
455 ///
456 /// # Example
457 ///
458 /// ```rust
459 /// use std::rand;
460 /// use std::rand::Rng;
461 ///
462 /// fn main() {
463 /// let mut rng = rand::task_rng();
464 /// let sample = rng.sample(range(1, 100), 5);
465 /// println!("{:?}", sample);
466 /// }
467 /// ```
468 fn sample<A, T: Iterator<A>>(&mut self, iter: T, n: uint) -> ~[A] {
469 let mut reservoir : ~[A] = vec::with_capacity(n);
470 for (i, elem) in iter.enumerate() {
471 if i < n {
472 reservoir.push(elem);
473 continue
474 }
475
476 let k = self.gen_integer_range(0, i + 1);
477 if k < reservoir.len() {
478 reservoir[k] = elem
479 }
480 }
481 reservoir
482 }
483 }
484
485 /// A random number generator that can be explicitly seeded to produce
486 /// the same stream of randomness multiple times.
487 pub trait SeedableRng<Seed>: Rng {
488 /// Reseed an RNG with the given seed.
489 ///
490 /// # Example
491 ///
492 /// ```rust
493 /// use std::rand;
494 /// use std::rand::Rng;
495 ///
496 /// fn main() {
497 /// let mut rng: rand::StdRng = rand::SeedableRng::from_seed(&[1, 2, 3, 4]);
498 /// println!("{}", rng.gen::<f64>());
499 /// rng.reseed([5, 6, 7, 8]);
500 /// println!("{}", rng.gen::<f64>());
501 /// }
502 /// ```
503 fn reseed(&mut self, Seed);
504
505 /// Create a new RNG with the given seed.
506 ///
507 /// # Example
508 ///
509 /// ```rust
510 /// use std::rand;
511 /// use std::rand::Rng;
512 ///
513 /// fn main() {
514 /// let mut rng: rand::StdRng = rand::SeedableRng::from_seed(&[1, 2, 3, 4]);
515 /// println!("{}", rng.gen::<f64>());
516 /// }
517 /// ```
518 fn from_seed(seed: Seed) -> Self;
519 }
520
521 /// Create a random number generator with a default algorithm and seed.
522 ///
523 /// It returns the cryptographically-safest `Rng` algorithm currently
524 /// available in Rust. If you require a specifically seeded `Rng` for
525 /// consistency over time you should pick one algorithm and create the
526 /// `Rng` yourself.
527 ///
528 /// This is a very expensive operation as it has to read randomness
529 /// from the operating system and use this in an expensive seeding
530 /// operation. If one does not require high performance generation of
531 /// random numbers, `task_rng` and/or `random` may be more
532 /// appropriate.
533 pub fn rng() -> StdRng {
534 StdRng::new()
535 }
536
537 /// The standard RNG. This is designed to be efficient on the current
538 /// platform.
539 #[cfg(not(target_word_size="64"))]
540 pub struct StdRng { priv rng: IsaacRng }
541
542 /// The standard RNG. This is designed to be efficient on the current
543 /// platform.
544 #[cfg(target_word_size="64")]
545 pub struct StdRng { priv rng: Isaac64Rng }
546
547 impl StdRng {
548 /// Create a randomly seeded instance of `StdRng`. This reads
549 /// randomness from the OS to seed the PRNG.
550 #[cfg(not(target_word_size="64"))]
551 pub fn new() -> StdRng {
552 StdRng { rng: IsaacRng::new() }
553 }
554 /// Create a randomly seeded instance of `StdRng`. This reads
555 /// randomness from the OS to seed the PRNG.
556 #[cfg(target_word_size="64")]
557 pub fn new() -> StdRng {
558 StdRng { rng: Isaac64Rng::new() }
559 }
560 }
561
562 impl Rng for StdRng {
563 #[inline]
564 fn next_u32(&mut self) -> u32 {
565 self.rng.next_u32()
566 }
567
568 #[inline]
569 fn next_u64(&mut self) -> u64 {
570 self.rng.next_u64()
571 }
572 }
573
574 impl<'self> SeedableRng<&'self [uint]> for StdRng {
575 fn reseed(&mut self, seed: &'self [uint]) {
576 // the internal RNG can just be seeded from the above
577 // randomness.
578 self.rng.reseed(unsafe {cast::transmute(seed)})
579 }
580
581 fn from_seed(seed: &'self [uint]) -> StdRng {
582 StdRng { rng: SeedableRng::from_seed(unsafe {cast::transmute(seed)}) }
583 }
584 }
585
586 /// Create a weak random number generator with a default algorithm and seed.
587 ///
588 /// It returns the fastest `Rng` algorithm currently available in Rust without
589 /// consideration for cryptography or security. If you require a specifically
590 /// seeded `Rng` for consistency over time you should pick one algorithm and
591 /// create the `Rng` yourself.
592 ///
593 /// This will read randomness from the operating system to seed the
594 /// generator.
595 pub fn weak_rng() -> XorShiftRng {
596 XorShiftRng::new()
597 }
598
599 /// An [Xorshift random number
600 /// generator](http://en.wikipedia.org/wiki/Xorshift).
601 ///
602 /// The Xorshift algorithm is not suitable for cryptographic purposes
603 /// but is very fast. If you do not know for sure that it fits your
604 /// requirements, use a more secure one such as `IsaacRng`.
605 pub struct XorShiftRng {
606 priv x: u32,
607 priv y: u32,
608 priv z: u32,
609 priv w: u32,
610 }
611
612 impl Rng for XorShiftRng {
613 #[inline]
614 fn next_u32(&mut self) -> u32 {
615 let x = self.x;
616 let t = x ^ (x << 11);
617 self.x = self.y;
618 self.y = self.z;
619 self.z = self.w;
620 let w = self.w;
621 self.w = w ^ (w >> 19) ^ (t ^ (t >> 8));
622 self.w
623 }
624 }
625
626 impl SeedableRng<[u32, .. 4]> for XorShiftRng {
627 /// Reseed an XorShiftRng. This will fail if `seed` is entirely 0.
628 fn reseed(&mut self, seed: [u32, .. 4]) {
629 assert!(!seed.iter().all(|&x| x == 0),
630 "XorShiftRng.reseed called with an all zero seed.");
631
632 self.x = seed[0];
633 self.y = seed[1];
634 self.z = seed[2];
635 self.w = seed[3];
636 }
637
638 /// Create a new XorShiftRng. This will fail if `seed` is entirely 0.
639 fn from_seed(seed: [u32, .. 4]) -> XorShiftRng {
640 assert!(!seed.iter().all(|&x| x == 0),
641 "XorShiftRng::from_seed called with an all zero seed.");
642
643 XorShiftRng {
644 x: seed[0],
645 y: seed[1],
646 z: seed[2],
647 w: seed[3]
648 }
649 }
650 }
651
652 impl XorShiftRng {
653 /// Create an xor shift random number generator with a random seed.
654 pub fn new() -> XorShiftRng {
655 let mut s = [0u8, ..16];
656 loop {
657 let mut r = OSRng::new();
658 r.fill_bytes(s);
659
660 if !s.iter().all(|x| *x == 0) {
661 break;
662 }
663 }
664 let s: [u32, ..4] = unsafe { cast::transmute(s) };
665 SeedableRng::from_seed(s)
666 }
667 }
668
669 /// Controls how the task-local RNG is reseeded.
670 struct TaskRngReseeder;
671
672 impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
673 fn reseed(&mut self, rng: &mut StdRng) {
674 *rng = StdRng::new();
675 }
676 }
677 static TASK_RNG_RESEED_THRESHOLD: uint = 32_768;
678 /// The task-local RNG.
679 pub type TaskRng = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
680
681 // used to make space in TLS for a random number generator
682 local_data_key!(TASK_RNG_KEY: @mut TaskRng)
683
684 /// Retrieve the lazily-initialized task-local random number
685 /// generator, seeded by the system. Intended to be used in method
686 /// chaining style, e.g. `task_rng().gen::<int>()`.
687 ///
688 /// The RNG provided will reseed itself from the operating system
689 /// after generating a certain amount of randomness.
690 ///
691 /// The internal RNG used is platform and architecture dependent, even
692 /// if the operating system random number generator is rigged to give
693 /// the same sequence always. If absolute consistency is required,
694 /// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`.
695 pub fn task_rng() -> @mut TaskRng {
696 let r = local_data::get(TASK_RNG_KEY, |k| k.map(|k| *k));
697 match r {
698 None => {
699 let rng = @mut reseeding::ReseedingRng::new(StdRng::new(),
700 TASK_RNG_RESEED_THRESHOLD,
701 TaskRngReseeder);
702 local_data::set(TASK_RNG_KEY, rng);
703 rng
704 }
705 Some(rng) => rng
706 }
707 }
708
709 // Allow direct chaining with `task_rng`
710 impl<R: Rng> Rng for @mut R {
711 #[inline]
712 fn next_u32(&mut self) -> u32 {
713 (**self).next_u32()
714 }
715 #[inline]
716 fn next_u64(&mut self) -> u64 {
717 (**self).next_u64()
718 }
719
720 #[inline]
721 fn fill_bytes(&mut self, bytes: &mut [u8]) {
722 (**self).fill_bytes(bytes);
723 }
724 }
725
726 /// Generate a random value using the task-local random number
727 /// generator.
728 ///
729 /// # Example
730 ///
731 /// ```rust
732 /// use std::rand::random;
733 ///
734 /// fn main() {
735 /// if random() {
736 /// let x = random();
737 /// println!("{}", 2u * x);
738 /// } else {
739 /// println!("{}", random::<f64>());
740 /// }
741 /// }
742 /// ```
743 #[inline]
744 pub fn random<T: Rand>() -> T {
745 task_rng().gen()
746 }
747
748 #[cfg(test)]
749 mod test {
750 use iter::{Iterator, range};
751 use option::{Option, Some};
752 use super::*;
753
754 #[test]
755 fn test_fill_bytes_default() {
756 let mut r = weak_rng();
757
758 let mut v = [0u8, .. 100];
759 r.fill_bytes(v);
760 }
761
762 #[test]
763 fn test_gen_integer_range() {
764 let mut r = rng();
765 for _ in range(0, 1000) {
766 let a = r.gen_integer_range(-3i, 42);
767 assert!(a >= -3 && a < 42);
768 assert_eq!(r.gen_integer_range(0, 1), 0);
769 assert_eq!(r.gen_integer_range(-12, -11), -12);
770 }
771
772 for _ in range(0, 1000) {
773 let a = r.gen_integer_range(10, 42);
774 assert!(a >= 10 && a < 42);
775 assert_eq!(r.gen_integer_range(0, 1), 0);
776 assert_eq!(r.gen_integer_range(3_000_000u, 3_000_001), 3_000_000);
777 }
778
779 }
780
781 #[test]
782 #[should_fail]
783 fn test_gen_integer_range_fail_int() {
784 let mut r = rng();
785 r.gen_integer_range(5i, -2);
786 }
787
788 #[test]
789 #[should_fail]
790 fn test_gen_integer_range_fail_uint() {
791 let mut r = rng();
792 r.gen_integer_range(5u, 2u);
793 }
794
795 #[test]
796 fn test_gen_f64() {
797 let mut r = rng();
798 let a = r.gen::<f64>();
799 let b = r.gen::<f64>();
800 debug2!("{:?}", (a, b));
801 }
802
803 #[test]
804 fn test_gen_weighted_bool() {
805 let mut r = rng();
806 assert_eq!(r.gen_weighted_bool(0u), true);
807 assert_eq!(r.gen_weighted_bool(1u), true);
808 }
809
810 #[test]
811 fn test_gen_ascii_str() {
812 let mut r = rng();
813 debug2!("{}", r.gen_ascii_str(10u));
814 debug2!("{}", r.gen_ascii_str(10u));
815 debug2!("{}", r.gen_ascii_str(10u));
816 assert_eq!(r.gen_ascii_str(0u).len(), 0u);
817 assert_eq!(r.gen_ascii_str(10u).len(), 10u);
818 assert_eq!(r.gen_ascii_str(16u).len(), 16u);
819 }
820
821 #[test]
822 fn test_gen_vec() {
823 let mut r = rng();
824 assert_eq!(r.gen_vec::<u8>(0u).len(), 0u);
825 assert_eq!(r.gen_vec::<u8>(10u).len(), 10u);
826 assert_eq!(r.gen_vec::<f64>(16u).len(), 16u);
827 }
828
829 #[test]
830 fn test_choose() {
831 let mut r = rng();
832 assert_eq!(r.choose([1, 1, 1]), 1);
833 }
834
835 #[test]
836 fn test_choose_option() {
837 let mut r = rng();
838 let v: &[int] = &[];
839 assert!(r.choose_option(v).is_none());
840
841 let i = 1;
842 let v = [1,1,1];
843 assert_eq!(r.choose_option(v), Some(&i));
844 }
845
846 #[test]
847 fn test_choose_weighted() {
848 let mut r = rng();
849 assert!(r.choose_weighted([
850 Weighted { weight: 1u, item: 42 },
851 ]) == 42);
852 assert!(r.choose_weighted([
853 Weighted { weight: 0u, item: 42 },
854 Weighted { weight: 1u, item: 43 },
855 ]) == 43);
856 }
857
858 #[test]
859 fn test_choose_weighted_option() {
860 let mut r = rng();
861 assert!(r.choose_weighted_option([
862 Weighted { weight: 1u, item: 42 },
863 ]) == Some(42));
864 assert!(r.choose_weighted_option([
865 Weighted { weight: 0u, item: 42 },
866 Weighted { weight: 1u, item: 43 },
867 ]) == Some(43));
868 let v: Option<int> = r.choose_weighted_option([]);
869 assert!(v.is_none());
870 }
871
872 #[test]
873 fn test_weighted_vec() {
874 let mut r = rng();
875 let empty: ~[int] = ~[];
876 assert_eq!(r.weighted_vec([]), empty);
877 assert!(r.weighted_vec([
878 Weighted { weight: 0u, item: 3u },
879 Weighted { weight: 1u, item: 2u },
880 Weighted { weight: 2u, item: 1u },
881 ]) == ~[2u, 1u, 1u]);
882 }
883
884 #[test]
885 fn test_shuffle() {
886 let mut r = rng();
887 let empty: ~[int] = ~[];
888 assert_eq!(r.shuffle(~[]), empty);
889 assert_eq!(r.shuffle(~[1, 1, 1]), ~[1, 1, 1]);
890 }
891
892 #[test]
893 fn test_task_rng() {
894 let mut r = task_rng();
895 r.gen::<int>();
896 assert_eq!(r.shuffle(~[1, 1, 1]), ~[1, 1, 1]);
897 assert_eq!(r.gen_integer_range(0u, 1u), 0u);
898 }
899
900 #[test]
901 fn test_random() {
902 // not sure how to test this aside from just getting some values
903 let _n : uint = random();
904 let _f : f32 = random();
905 let _o : Option<Option<i8>> = random();
906 let _many : ((),
907 (~uint, @int, ~Option<~(@u32, ~(@bool,))>),
908 (u8, i8, u16, i16, u32, i32, u64, i64),
909 (f32, (f64, (f64,)))) = random();
910 }
911
912 #[test]
913 fn test_sample() {
914 let MIN_VAL = 1;
915 let MAX_VAL = 100;
916
917 let mut r = rng();
918 let vals = range(MIN_VAL, MAX_VAL).to_owned_vec();
919 let small_sample = r.sample(vals.iter(), 5);
920 let large_sample = r.sample(vals.iter(), vals.len() + 5);
921
922 assert_eq!(small_sample.len(), 5);
923 assert_eq!(large_sample.len(), vals.len());
924
925 assert!(small_sample.iter().all(|e| {
926 **e >= MIN_VAL && **e <= MAX_VAL
927 }));
928 }
929
930 #[test]
931 fn test_std_rng_seeded() {
932 let s = OSRng::new().gen_vec::<uint>(256);
933 let mut ra: StdRng = SeedableRng::from_seed(s.as_slice());
934 let mut rb: StdRng = SeedableRng::from_seed(s.as_slice());
935 assert_eq!(ra.gen_ascii_str(100u), rb.gen_ascii_str(100u));
936 }
937
938 #[test]
939 fn test_std_rng_reseed() {
940 let s = OSRng::new().gen_vec::<uint>(256);
941 let mut r: StdRng = SeedableRng::from_seed(s.as_slice());
942 let string1 = r.gen_ascii_str(100);
943
944 r.reseed(s);
945
946 let string2 = r.gen_ascii_str(100);
947 assert_eq!(string1, string2);
948 }
949 }
950
951 #[cfg(test)]
952 mod bench {
953 use extra::test::BenchHarness;
954 use rand::*;
955 use sys::size_of;
956
957 #[bench]
958 fn rand_xorshift(bh: &mut BenchHarness) {
959 let mut rng = XorShiftRng::new();
960 do bh.iter {
961 rng.gen::<uint>();
962 }
963 bh.bytes = size_of::<uint>() as u64;
964 }
965
966 #[bench]
967 fn rand_isaac(bh: &mut BenchHarness) {
968 let mut rng = IsaacRng::new();
969 do bh.iter {
970 rng.gen::<uint>();
971 }
972 bh.bytes = size_of::<uint>() as u64;
973 }
974
975 #[bench]
976 fn rand_isaac64(bh: &mut BenchHarness) {
977 let mut rng = Isaac64Rng::new();
978 do bh.iter {
979 rng.gen::<uint>();
980 }
981 bh.bytes = size_of::<uint>() as u64;
982 }
983
984 #[bench]
985 fn rand_std(bh: &mut BenchHarness) {
986 let mut rng = StdRng::new();
987 do bh.iter {
988 rng.gen::<uint>();
989 }
990 bh.bytes = size_of::<uint>() as u64;
991 }
992
993 #[bench]
994 fn rand_shuffle_100(bh: &mut BenchHarness) {
995 let mut rng = XorShiftRng::new();
996 let x : &mut[uint] = [1,..100];
997 do bh.iter {
998 rng.shuffle_mut(x);
999 }
1000 }
1001 }
libstd/rand/mod.rs:486:50-486:50 -trait- definition:
/// the same stream of randomness multiple times.
pub trait SeedableRng<Seed>: Rng {
references:-518: fn from_seed(seed: Seed) -> Self;
574: impl<'self> SeedableRng<&'self [uint]> for StdRng {
626: impl SeedableRng<[u32, .. 4]> for XorShiftRng {
libstd/rand/isaac.rs:
383: impl<'self> SeedableRng<&'self [u64]> for Isaac64Rng {
182: impl<'self> SeedableRng<&'self [u32]> for IsaacRng {
libstd/rand/reseeding.rs:
80: SeedableRng<(Rsdr, S)> for ReseedingRng<R, Rsdr> {
79: impl<S, R: SeedableRng<S>, Rsdr: Reseeder<R>>
libstd/rand/mod.rs:678:24-678:24 -ty- definition:
/// The task-local RNG.
pub type TaskRng = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
references:-682: local_data_key!(TASK_RNG_KEY: @mut TaskRng)
695: pub fn task_rng() -> @mut TaskRng {
libstd/rand/mod.rs:604:60-604:60 -struct- definition:
/// requirements, use a more secure one such as `IsaacRng`.
pub struct XorShiftRng {
references:-652: impl XorShiftRng {
626: impl SeedableRng<[u32, .. 4]> for XorShiftRng {
654: pub fn new() -> XorShiftRng {
643: XorShiftRng {
639: fn from_seed(seed: [u32, .. 4]) -> XorShiftRng {
612: impl Rng for XorShiftRng {
595: pub fn weak_rng() -> XorShiftRng {
libstd/rt/sched.rs:
79: rng: XorShiftRng,
101: fn reset_yield_check(rng: &mut XorShiftRng) -> uint {
858: fn new_sched_rng() -> XorShiftRng {
libstd/rand/mod.rs:532:17-532:17 -fn- definition:
/// appropriate.
pub fn rng() -> StdRng {
references:-libstd/rt/test.rs:
267: let mut rng = rng();
libstd/rand/mod.rs:83:62-83:62 -struct- definition:
/// A value with a particular weight compared to other values
pub struct Weighted<T> {
references:-399: fn weighted_vec<T:Clone>(&mut self, v: &[Weighted<T>]) -> ~[T] {
341: fn choose_weighted<T:Clone>(&mut self, v: &[Weighted<T>]) -> T {
362: fn choose_weighted_option<T:Clone>(&mut self, v: &[Weighted<T>])
libstd/rand/mod.rs:91:30-91:30 -trait- definition:
/// A random number generator
pub trait Rng {
references:-612: impl Rng for XorShiftRng {
562: impl Rng for StdRng {
710: impl<R: Rng> Rng for @mut R {
80: fn rand<R: Rng>(rng: &mut R) -> Self;
487: pub trait SeedableRng<Seed>: Rng {
710: impl<R: Rng> Rng for @mut R {
libstd/rand/distributions.rs:
135: fn rand<R:Rng>(rng: &mut R) -> Exp1 {
30: fn ziggurat<R:Rng>(rng: &mut R,
141: fn zero_case<R:Rng>(rng: &mut R, _u: f64) -> f64 {
85: fn zero_case<R:Rng>(rng: &mut R, u: f64) -> f64 {
79: fn rand<R:Rng>(rng: &mut R) -> StandardNormal {
libstd/rand/isaac.rs:
170: impl Rng for IsaacRng {
365: impl Rng for Isaac64Rng {
libstd/rand/os.rs:
74: impl Rng for OSRng {
libstd/rand/reader.rs:
48: impl<R: Reader> Rng for ReaderRng<R> {
libstd/rand/reseeding.rs:
59: impl<R: Rng, Rsdr: Reseeder<R>> Rng for ReseedingRng<R, Rsdr> {
31: impl<R: Rng, Rsdr: Reseeder<R>> ReseedingRng<R, Rsdr> {
133: impl<R: Rng + Default> Reseeder<R> for ReseedWithDefault {
59: impl<R: Rng, Rsdr: Reseeder<R>> Rng for ReseedingRng<R, Rsdr> {
libstd/rand/rand_impls.rs:
39: fn rand<R: Rng>(rng: &mut R) -> i16 {
173: fn rand<R: Rng>(_: &mut R) -> () { () }
101: fn rand<R: Rng>(rng: &mut R) -> f32 {
32: fn rand<R: Rng>(rng: &mut R) -> i8 {
188: fn rand<R: Rng>(rng: &mut R) -> Option<T> {
21: fn rand<R: Rng>(rng: &mut R) -> int {
92: fn rand<R: Rng>(rng: &mut R) -> u64 {
199: fn rand<R: Rng>(rng: &mut R) -> ~T { ~rng.gen() }
71: fn rand<R: Rng>(rng: &mut R) -> u8 {
46: fn rand<R: Rng>(rng: &mut R) -> i32 {
126: fn rand<R: Rng>(rng: &mut R) -> char {
(157)(115)(204)(157)(157)(53)(78)(157)(157)(157)(85)(60)(157)(157)(157)(157)(143)libstd/rand/mod.rs:694:63-694:63 -fn- definition:
/// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`.
pub fn task_rng() -> @mut TaskRng {
references:-745: task_rng().gen()
libstd/hashmap.rs:
332: let mut r = rand::task_rng();
libstd/rand/mod.rs:544:30-544:30 -struct- definition:
#[cfg(target_word_size="64")]
pub struct StdRng { priv rng: Isaac64Rng }
references:-547: impl StdRng {
673: fn reseed(&mut self, rng: &mut StdRng) {
557: pub fn new() -> StdRng {
574: impl<'self> SeedableRng<&'self [uint]> for StdRng {
558: StdRng { rng: Isaac64Rng::new() }
582: StdRng { rng: SeedableRng::from_seed(unsafe {cast::transmute(seed)}) }
581: fn from_seed(seed: &'self [uint]) -> StdRng {
533: pub fn rng() -> StdRng {
672: impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
562: impl Rng for StdRng {
679: pub type TaskRng = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
libstd/rand/mod.rs:76:55-76:55 -trait- definition:
/// A type that can be randomly generated using an Rng
pub trait Rand {
references:-80: fn rand<R: Rng>(rng: &mut R) -> Self;
244: fn gen_integer_range<T: Rand + Int>(&mut self, low: T, high: T) -> T {
744: pub fn random<T: Rand>() -> T {
198: fn gen<T: Rand>(&mut self) -> T {
217: fn gen_vec<T: Rand>(&mut self, len: uint) -> ~[T] {
libstd/rand/distributions.rs:
133: impl Rand for Exp1 {
78: impl Rand for StandardNormal {
libstd/rand/rand_impls.rs:
153: $( $tyvar : Rand ),*
197: impl<T: Rand> Rand for ~T {
153: $( $tyvar : Rand ),*
154: > Rand for ( $( $tyvar ),* , ) {
124: impl Rand for char {
153: $( $tyvar : Rand ),*
51: impl Rand for i64 {
153: $( $tyvar : Rand ),*
153: $( $tyvar : Rand ),*
153: $( $tyvar : Rand ),*
153: $( $tyvar : Rand ),*
153: $( $tyvar : Rand ),*
171: impl Rand for () {
153: $( $tyvar : Rand ),*
111: impl Rand for f64 {
153: $( $tyvar : Rand ),*
154: > Rand for ( $( $tyvar ),* , ) {
153: $( $tyvar : Rand ),*
153: $( $tyvar : Rand ),*
153: $( $tyvar : Rand ),*
186: impl<T:Rand> Rand for Option<T> {
44: impl Rand for i32 {
153: $( $tyvar : Rand ),*
(153)(58)(154)(153)(153)(153)(141)(83)(90)(153)(153)(153)(153)(37)(154)(153)(153)(153)(153)(154)(153)(153)(154)(153)(153)(153)(153)(153)(153)(153)(154)(76)(153)(30)(153)(153)(186)(153)(153)(153)(19)(153)(153)(153)(202)(153)(153)(153)(97)(202)(153)(69)(154)(153)(153)(153)(153)(197)(154)(153)..3more..
libstd/rand/mod.rs:669:49-669:49 -struct- definition:
/// Controls how the task-local RNG is reseeded.
struct TaskRngReseeder;
references:-672: impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
679: pub type TaskRng = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;