src/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 //! Utilities for random number generation
  12 //!
  13 //! The key functions are `random()` and `Rng::gen()`. These are polymorphic
  14 //! and so can be used to generate any type that implements `Rand`. Type inference
  15 //! means that often a simple call to `rand::random()` or `rng.gen()` will
  16 //! suffice, but sometimes an annotation is required, e.g. `rand::random::<f64>()`.
  17 //!
  18 //! See the `distributions` submodule for sampling random numbers from
  19 //! distributions like normal and exponential.
  20 //!
  21 //! # Task-local RNG
  22 //!
  23 //! There is built-in support for a RNG associated with each task stored
  24 //! in task-local storage. This RNG can be accessed via `task_rng`, or
  25 //! used implicitly via `random`. This RNG is normally randomly seeded
  26 //! from an operating-system source of randomness, e.g. `/dev/urandom` on
  27 //! Unix systems, and will automatically reseed itself from this source
  28 //! after generating 32 KiB of random data.
  29 //!
  30 //! # Cryptographic security
  31 //!
  32 //! An application that requires an entropy source for cryptographic purposes
  33 //! must use `OsRng`, which reads randomness from the source that the operating
  34 //! system provides (e.g. `/dev/urandom` on Unixes or `CryptGenRandom()` on Windows).
  35 //! The other random number generators provided by this module are not suitable
  36 //! for such purposes.
  37 //!
  38 //! *Note*: many Unix systems provide `/dev/random` as well as `/dev/urandom`.
  39 //! This module uses `/dev/urandom` for the following reasons:
  40 //!
  41 //! -   On Linux, `/dev/random` may block if entropy pool is empty; `/dev/urandom` will not block.
  42 //!     This does not mean that `/dev/random` provides better output than
  43 //!     `/dev/urandom`; the kernel internally runs a cryptographically secure pseudorandom
  44 //!     number generator (CSPRNG) based on entropy pool for random number generation,
  45 //!     so the "quality" of `/dev/random` is not better than `/dev/urandom` in most cases.
  46 //!     However, this means that `/dev/urandom` can yield somewhat predictable randomness
  47 //!     if the entropy pool is very small, such as immediately after first booting.
  48 //!     Linux 3,17 added `getrandom(2)` system call which solves the issue: it blocks if entropy
  49 //!     pool is not initialized yet, but it does not block once initialized.
  50 //!     `OsRng` tries to use `getrandom(2)` if available, and use `/dev/urandom` fallback if not.
  51 //!     If an application does not have `getrandom` and likely to be run soon after first booting,
  52 //!     or on a system with very few entropy sources, one should consider using `/dev/random` via
  53 //!     `ReaderRng`.
  54 //! -   On some systems (e.g. FreeBSD, OpenBSD and Mac OS X) there is no difference
  55 //!     between the two sources. (Also note that, on some systems e.g. FreeBSD, both `/dev/random`
  56 //!     and `/dev/urandom` may block once if the CSPRNG has not seeded yet.)
  57 //!
  58 //! # Examples
  59 //!
  60 //! ```rust
  61 //! use std::rand;
  62 //! use std::rand::Rng;
  63 //!
  64 //! let mut rng = rand::task_rng();
  65 //! if rng.gen() { // random bool
  66 //!     println!("int: {}, uint: {}", rng.gen::<int>(), rng.gen::<uint>())
  67 //! }
  68 //! ```
  69 //!
  70 //! ```rust
  71 //! use std::rand;
  72 //!
  73 //! let tuple = rand::random::<(f64, char)>();
  74 //! println!("{}", tuple)
  75 //! ```
  76 //!
  77 //! ## Monte Carlo estimation of π
  78 //!
  79 //! For this example, imagine we have a square with sides of length 2 and a unit
  80 //! circle, both centered at the origin. Since the area of a unit circle is π,
  81 //! we have:
  82 //!
  83 //! ```notrust
  84 //!     (area of unit circle) / (area of square) = π / 4
  85 //! ```
  86 //!
  87 //! So if we sample many points randomly from the square, roughly π / 4 of them
  88 //! should be inside the circle.
  89 //!
  90 //! We can use the above fact to estimate the value of π: pick many points in the
  91 //! square at random, calculate the fraction that fall within the circle, and
  92 //! multiply this fraction by 4.
  93 //!
  94 //! ```
  95 //! use std::rand;
  96 //! use std::rand::distributions::{IndependentSample, Range};
  97 //!
  98 //! fn main() {
  99 //!    let between = Range::new(-1f64, 1.);
 100 //!    let mut rng = rand::task_rng();
 101 //!
 102 //!    let total = 1_000_000u;
 103 //!    let mut in_circle = 0u;
 104 //!
 105 //!    for _ in range(0u, total) {
 106 //!        let a = between.ind_sample(&mut rng);
 107 //!        let b = between.ind_sample(&mut rng);
 108 //!        if a*a + b*b <= 1. {
 109 //!            in_circle += 1;
 110 //!        }
 111 //!    }
 112 //!
 113 //!    // prints something close to 3.14159...
 114 //!    println!("{}", 4. * (in_circle as f64) / (total as f64));
 115 //! }
 116 //! ```
 117 //!
 118 //! ## Monty Hall Problem
 119 //!
 120 //! This is a simulation of the [Monty Hall Problem][]:
 121 //!
 122 //! > Suppose you're on a game show, and you're given the choice of three doors:
 123 //! > Behind one door is a car; behind the others, goats. You pick a door, say No. 1,
 124 //! > and the host, who knows what's behind the doors, opens another door, say No. 3,
 125 //! > which has a goat. He then says to you, "Do you want to pick door No. 2?"
 126 //! > Is it to your advantage to switch your choice?
 127 //!
 128 //! The rather unintuitive answer is that you will have a 2/3 chance of winning if
 129 //! you switch and a 1/3 chance of winning of you don't, so it's better to switch.
 130 //!
 131 //! This program will simulate the game show and with large enough simulation steps
 132 //! it will indeed confirm that it is better to switch.
 133 //!
 134 //! [Monty Hall Problem]: http://en.wikipedia.org/wiki/Monty_Hall_problem
 135 //!
 136 //! ```
 137 //! use std::rand;
 138 //! use std::rand::Rng;
 139 //! use std::rand::distributions::{IndependentSample, Range};
 140 //!
 141 //! struct SimulationResult {
 142 //!     win: bool,
 143 //!     switch: bool,
 144 //! }
 145 //!
 146 //! // Run a single simulation of the Monty Hall problem.
 147 //! fn simulate<R: Rng>(random_door: &Range<uint>, rng: &mut R) -> SimulationResult {
 148 //!     let car = random_door.ind_sample(rng);
 149 //!
 150 //!     // This is our initial choice
 151 //!     let mut choice = random_door.ind_sample(rng);
 152 //!
 153 //!     // The game host opens a door
 154 //!     let open = game_host_open(car, choice, rng);
 155 //!
 156 //!     // Shall we switch?
 157 //!     let switch = rng.gen();
 158 //!     if switch {
 159 //!         choice = switch_door(choice, open);
 160 //!     }
 161 //!
 162 //!     SimulationResult { win: choice == car, switch: switch }
 163 //! }
 164 //!
 165 //! // Returns the door the game host opens given our choice and knowledge of
 166 //! // where the car is. The game host will never open the door with the car.
 167 //! fn game_host_open<R: Rng>(car: uint, choice: uint, rng: &mut R) -> uint {
 168 //!     let choices = free_doors(&[car, choice]);
 169 //!     rand::sample(rng, choices.into_iter(), 1)[0]
 170 //! }
 171 //!
 172 //! // Returns the door we switch to, given our current choice and
 173 //! // the open door. There will only be one valid door.
 174 //! fn switch_door(choice: uint, open: uint) -> uint {
 175 //!     free_doors(&[choice, open])[0]
 176 //! }
 177 //!
 178 //! fn free_doors(blocked: &[uint]) -> Vec<uint> {
 179 //!     range(0u, 3).filter(|x| !blocked.contains(x)).collect()
 180 //! }
 181 //!
 182 //! fn main() {
 183 //!     // The estimation will be more accurate with more simulations
 184 //!     let num_simulations = 10000u;
 185 //!
 186 //!     let mut rng = rand::task_rng();
 187 //!     let random_door = Range::new(0u, 3);
 188 //!
 189 //!     let (mut switch_wins, mut switch_losses) = (0u, 0u);
 190 //!     let (mut keep_wins, mut keep_losses) = (0u, 0u);
 191 //!
 192 //!     println!("Running {} simulations...", num_simulations);
 193 //!     for _ in range(0, num_simulations) {
 194 //!         let result = simulate(&random_door, &mut rng);
 195 //!
 196 //!         match (result.win, result.switch) {
 197 //!             (true, true) => switch_wins += 1,
 198 //!             (true, false) => keep_wins += 1,
 199 //!             (false, true) => switch_losses += 1,
 200 //!             (false, false) => keep_losses += 1,
 201 //!         }
 202 //!     }
 203 //!
 204 //!     let total_switches = switch_wins + switch_losses;
 205 //!     let total_keeps = keep_wins + keep_losses;
 206 //!
 207 //!     println!("Switched door {} times with {} wins and {} losses",
 208 //!              total_switches, switch_wins, switch_losses);
 209 //!
 210 //!     println!("Kept our choice {} times with {} wins and {} losses",
 211 //!              total_keeps, keep_wins, keep_losses);
 212 //!
 213 //!     // With a large number of simulations, the values should converge to
 214 //!     // 0.667 and 0.333 respectively.
 215 //!     println!("Estimated chance to win if we switch: {}",
 216 //!              switch_wins as f32 / total_switches as f32);
 217 //!     println!("Estimated chance to win if we don't: {}",
 218 //!              keep_wins as f32 / total_keeps as f32);
 219 //! }
 220 //! ```
 221
 222 #![experimental]
 223
 224 use cell::RefCell;
 225 use clone::Clone;
 226 use io::IoResult;
 227 use iter::Iterator;
 228 use mem;
 229 use rc::Rc;
 230 use result::{Ok, Err};
 231 use vec::Vec;
 232
 233 #[cfg(not(target_word_size="64"))]
 234 use core_rand::IsaacRng as IsaacWordRng;
 235 #[cfg(target_word_size="64")]
 236 use core_rand::Isaac64Rng as IsaacWordRng;
 237
 238 pub use core_rand::{Rand, Rng, SeedableRng, Open01, Closed01};
 239 pub use core_rand::{XorShiftRng, IsaacRng, Isaac64Rng, ChaChaRng};
 240 pub use core_rand::{distributions, reseeding};
 241 pub use rand::os::OsRng;
 242
 243 pub mod os;
 244 pub mod reader;
 245
 246 /// The standard RNG. This is designed to be efficient on the current
 247 /// platform.
 248 pub struct StdRng { rng: IsaacWordRng }
 249
 250 impl StdRng {
 251     /// Create a randomly seeded instance of `StdRng`.
 252     ///
 253     /// This is a very expensive operation as it has to read
 254     /// randomness from the operating system and use this in an
 255     /// expensive seeding operation. If one is only generating a small
 256     /// number of random numbers, or doesn't need the utmost speed for
 257     /// generating each number, `task_rng` and/or `random` may be more
 258     /// appropriate.
 259     ///
 260     /// Reading the randomness from the OS may fail, and any error is
 261     /// propagated via the `IoResult` return value.
 262     pub fn new() -> IoResult<StdRng> {
 263         OsRng::new().map(|mut r| StdRng { rng: r.gen() })
 264     }
 265 }
 266
 267 impl Rng for StdRng {
 268     #[inline]
 269     fn next_u32(&mut self) -> u32 {
 270         self.rng.next_u32()
 271     }
 272
 273     #[inline]
 274     fn next_u64(&mut self) -> u64 {
 275         self.rng.next_u64()
 276     }
 277 }
 278
 279 impl<'a> SeedableRng<&'a [uint]> for StdRng {
 280     fn reseed(&mut self, seed: &'a [uint]) {
 281         // the internal RNG can just be seeded from the above
 282         // randomness.
 283         self.rng.reseed(unsafe {mem::transmute(seed)})
 284     }
 285
 286     fn from_seed(seed: &'a [uint]) -> StdRng {
 287         StdRng { rng: SeedableRng::from_seed(unsafe {mem::transmute(seed)}) }
 288     }
 289 }
 290
 291 /// Create a weak random number generator with a default algorithm and seed.
 292 ///
 293 /// It returns the fastest `Rng` algorithm currently available in Rust without
 294 /// consideration for cryptography or security. If you require a specifically
 295 /// seeded `Rng` for consistency over time you should pick one algorithm and
 296 /// create the `Rng` yourself.
 297 ///
 298 /// This will read randomness from the operating system to seed the
 299 /// generator.
 300 pub fn weak_rng() -> XorShiftRng {
 301     match OsRng::new() {
 302         Ok(mut r) => r.gen(),
 303         Err(e) => panic!("weak_rng: failed to create seeded RNG: {}", e)
 304     }
 305 }
 306
 307 /// Controls how the task-local RNG is reseeded.
 308 struct TaskRngReseeder;
 309
 310 impl reseeding::Reseeder<StdRng> for TaskRngReseeder {
 311     fn reseed(&mut self, rng: &mut StdRng) {
 312         *rng = match StdRng::new() {
 313             Ok(r) => r,
 314             Err(e) => panic!("could not reseed task_rng: {}", e)
 315         }
 316     }
 317 }
 318 static TASK_RNG_RESEED_THRESHOLD: uint = 32_768;
 319 type TaskRngInner = reseeding::ReseedingRng<StdRng, TaskRngReseeder>;
 320
 321 /// The task-local RNG.
 322 pub struct TaskRng {
 323     rng: Rc<RefCell<TaskRngInner>>,
 324 }
 325
 326 /// Retrieve the lazily-initialized task-local random number
 327 /// generator, seeded by the system. Intended to be used in method
 328 /// chaining style, e.g. `task_rng().gen::<int>()`.
 329 ///
 330 /// The RNG provided will reseed itself from the operating system
 331 /// after generating a certain amount of randomness.
 332 ///
 333 /// The internal RNG used is platform and architecture dependent, even
 334 /// if the operating system random number generator is rigged to give
 335 /// the same sequence always. If absolute consistency is required,
 336 /// explicitly select an RNG, e.g. `IsaacRng` or `Isaac64Rng`.
 337 pub fn task_rng() -> TaskRng {
 338     // used to make space in TLS for a random number generator
 339     thread_local!(static TASK_RNG_KEY: Rc<RefCell<TaskRngInner>> = {
 340         let r = match StdRng::new() {
 341             Ok(r) => r,
 342             Err(e) => panic!("could not initialize task_rng: {}", e)
 343         };
 344         let rng = reseeding::ReseedingRng::new(r,
 345                                                TASK_RNG_RESEED_THRESHOLD,
 346                                                TaskRngReseeder);
 347         Rc::new(RefCell::new(rng))
 348     })
 349
 350     TaskRng { rng: TASK_RNG_KEY.with(|t| t.clone()) }
 351 }
 352
 353 impl Rng for TaskRng {
 354     fn next_u32(&mut self) -> u32 {
 355         self.rng.borrow_mut().next_u32()
 356     }
 357
 358     fn next_u64(&mut self) -> u64 {
 359         self.rng.borrow_mut().next_u64()
 360     }
 361
 362     #[inline]
 363     fn fill_bytes(&mut self, bytes: &mut [u8]) {
 364         self.rng.borrow_mut().fill_bytes(bytes)
 365     }
 366 }
 367
 368 /// Generates a random value using the task-local random number generator.
 369 ///
 370 /// `random()` can generate various types of random things, and so may require
 371 /// type hinting to generate the specific type you want.
 372 ///
 373 /// # Examples
 374 ///
 375 /// ```rust
 376 /// use std::rand;
 377 ///
 378 /// let x = rand::random();
 379 /// println!("{}", 2u * x);
 380 ///
 381 /// let y = rand::random::<f64>();
 382 /// println!("{}", y);
 383 ///
 384 /// if rand::random() { // generates a boolean
 385 ///     println!("Better lucky than good!");
 386 /// }
 387 /// ```
 388 #[inline]
 389 pub fn random<T: Rand>() -> T {
 390     task_rng().gen()
 391 }
 392
 393 /// Randomly sample up to `amount` elements from an iterator.
 394 ///
 395 /// # Example
 396 ///
 397 /// ```rust
 398 /// use std::rand::{task_rng, sample};
 399 ///
 400 /// let mut rng = task_rng();
 401 /// let sample = sample(&mut rng, range(1i, 100), 5);
 402 /// println!("{}", sample);
 403 /// ```
 404 pub fn sample<T, I: Iterator<T>, R: Rng>(rng: &mut R,
 405                                          mut iter: I,
 406                                          amount: uint) -> Vec<T> {
 407     let mut reservoir: Vec<T> = iter.by_ref().take(amount).collect();
 408     for (i, elem) in iter.enumerate() {
 409         let k = rng.gen_range(0, i + 1 + amount);
 410         if k < amount {
 411             reservoir[k] = elem;
 412         }
 413     }
 414     return reservoir;
 415 }
 416
 417 #[cfg(test)]
 418 mod test {
 419     use prelude::*;
 420     use super::{Rng, task_rng, random, SeedableRng, StdRng, sample};
 421     use iter::order;
 422
 423     struct ConstRng { i: u64 }
 424     impl Rng for ConstRng {
 425         fn next_u32(&mut self) -> u32 { self.i as u32 }
 426         fn next_u64(&mut self) -> u64 { self.i }
 427
 428         // no fill_bytes on purpose
 429     }
 430
 431     #[test]
 432     fn test_fill_bytes_default() {
 433         let mut r = ConstRng { i: 0x11_22_33_44_55_66_77_88 };
 434
 435         // check every remainder mod 8, both in small and big vectors.
 436         let lengths = [0, 1, 2, 3, 4, 5, 6, 7,
 437                        80, 81, 82, 83, 84, 85, 86, 87];
 438         for &n in lengths.iter() {
 439             let mut v = Vec::from_elem(n, 0u8);
 440             r.fill_bytes(v.as_mut_slice());
 441
 442             // use this to get nicer error messages.
 443             for (i, &byte) in v.iter().enumerate() {
 444                 if byte == 0 {
 445                     panic!("byte {} of {} is zero", i, n)
 446                 }
 447             }
 448         }
 449     }
 450
 451     #[test]
 452     fn test_gen_range() {
 453         let mut r = task_rng();
 454         for _ in range(0u, 1000) {
 455             let a = r.gen_range(-3i, 42);
 456             assert!(a >= -3 && a < 42);
 457             assert_eq!(r.gen_range(0i, 1), 0);
 458             assert_eq!(r.gen_range(-12i, -11), -12);
 459         }
 460
 461         for _ in range(0u, 1000) {
 462             let a = r.gen_range(10i, 42);
 463             assert!(a >= 10 && a < 42);
 464             assert_eq!(r.gen_range(0i, 1), 0);
 465             assert_eq!(r.gen_range(3_000_000u, 3_000_001), 3_000_000);
 466         }
 467
 468     }
 469
 470     #[test]
 471     #[should_fail]
 472     fn test_gen_range_panic_int() {
 473         let mut r = task_rng();
 474         r.gen_range(5i, -2);
 475     }
 476
 477     #[test]
 478     #[should_fail]
 479     fn test_gen_range_panic_uint() {
 480         let mut r = task_rng();
 481         r.gen_range(5u, 2u);
 482     }
 483
 484     #[test]
 485     fn test_gen_f64() {
 486         let mut r = task_rng();
 487         let a = r.gen::<f64>();
 488         let b = r.gen::<f64>();
 489         debug!("{}", (a, b));
 490     }
 491
 492     #[test]
 493     fn test_gen_weighted_bool() {
 494         let mut r = task_rng();
 495         assert_eq!(r.gen_weighted_bool(0u), true);
 496         assert_eq!(r.gen_weighted_bool(1u), true);
 497     }
 498
 499     #[test]
 500     fn test_gen_ascii_str() {
 501         let mut r = task_rng();
 502         assert_eq!(r.gen_ascii_chars().take(0).count(), 0u);
 503         assert_eq!(r.gen_ascii_chars().take(10).count(), 10u);
 504         assert_eq!(r.gen_ascii_chars().take(16).count(), 16u);
 505     }
 506
 507     #[test]
 508     fn test_gen_vec() {
 509         let mut r = task_rng();
 510         assert_eq!(r.gen_iter::<u8>().take(0).count(), 0u);
 511         assert_eq!(r.gen_iter::<u8>().take(10).count(), 10u);
 512         assert_eq!(r.gen_iter::<f64>().take(16).count(), 16u);
 513     }
 514
 515     #[test]
 516     fn test_choose() {
 517         let mut r = task_rng();
 518         assert_eq!(r.choose(&[1i, 1, 1]).map(|&x|x), Some(1));
 519
 520         let v: &[int] = &[];
 521         assert_eq!(r.choose(v), None);
 522     }
 523
 524     #[test]
 525     fn test_shuffle() {
 526         let mut r = task_rng();
 527         let empty: &mut [int] = &mut [];
 528         r.shuffle(empty);
 529         let mut one = [1i];
 530         r.shuffle(&mut one);
 531         let b: &[_] = &[1];
 532         assert_eq!(one.as_slice(), b);
 533
 534         let mut two = [1i, 2];
 535         r.shuffle(&mut two);
 536         assert!(two == [1, 2] || two == [2, 1]);
 537
 538         let mut x = [1i, 1, 1];
 539         r.shuffle(&mut x);
 540         let b: &[_] = &[1, 1, 1];
 541         assert_eq!(x.as_slice(), b);
 542     }
 543
 544     #[test]
 545     fn test_task_rng() {
 546         let mut r = task_rng();
 547         r.gen::<int>();
 548         let mut v = [1i, 1, 1];
 549         r.shuffle(&mut v);
 550         let b: &[_] = &[1, 1, 1];
 551         assert_eq!(v.as_slice(), b);
 552         assert_eq!(r.gen_range(0u, 1u), 0u);
 553     }
 554
 555     #[test]
 556     fn test_random() {
 557         // not sure how to test this aside from just getting some values
 558         let _n : uint = random();
 559         let _f : f32 = random();
 560         let _o : Option<Option<i8>> = random();
 561         let _many : ((),
 562                      (uint,
 563                       int,
 564                       Option<(u32, (bool,))>),
 565                      (u8, i8, u16, i16, u32, i32, u64, i64),
 566                      (f32, (f64, (f64,)))) = random();
 567     }
 568
 569     #[test]
 570     fn test_sample() {
 571         let min_val = 1i;
 572         let max_val = 100i;
 573
 574         let mut r = task_rng();
 575         let vals = range(min_val, max_val).collect::<Vec<int>>();
 576         let small_sample = sample(&mut r, vals.iter(), 5);
 577         let large_sample = sample(&mut r, vals.iter(), vals.len() + 5);
 578
 579         assert_eq!(small_sample.len(), 5);
 580         assert_eq!(large_sample.len(), vals.len());
 581
 582         assert!(small_sample.iter().all(|e| {
 583             **e >= min_val && **e <= max_val
 584         }));
 585     }
 586
 587     #[test]
 588     fn test_std_rng_seeded() {
 589         let s = task_rng().gen_iter::<uint>().take(256).collect::<Vec<uint>>();
 590         let mut ra: StdRng = SeedableRng::from_seed(s.as_slice());
 591         let mut rb: StdRng = SeedableRng::from_seed(s.as_slice());
 592         assert!(order::equals(ra.gen_ascii_chars().take(100),
 593                               rb.gen_ascii_chars().take(100)));
 594     }
 595
 596     #[test]
 597     fn test_std_rng_reseed() {
 598         let s = task_rng().gen_iter::<uint>().take(256).collect::<Vec<uint>>();
 599         let mut r: StdRng = SeedableRng::from_seed(s.as_slice());
 600         let string1 = r.gen_ascii_chars().take(100).collect::<String>();
 601
 602         r.reseed(s.as_slice());
 603
 604         let string2 = r.gen_ascii_chars().take(100).collect::<String>();
 605         assert_eq!(string1, string2);
 606     }
 607 }
 608
 609 #[cfg(test)]
 610 static RAND_BENCH_N: u64 = 100;
 611
 612 #[cfg(test)]
 613 mod bench {
 614     extern crate test;
 615     use prelude::*;
 616
 617     use self::test::Bencher;
 618     use super::{XorShiftRng, StdRng, IsaacRng, Isaac64Rng, Rng, RAND_BENCH_N};
 619     use super::{OsRng, weak_rng};
 620     use mem::size_of;
 621
 622     #[bench]
 623     fn rand_xorshift(b: &mut Bencher) {
 624         let mut rng: XorShiftRng = OsRng::new().unwrap().gen();
 625         b.iter(|| {
 626             for _ in range(0, RAND_BENCH_N) {
 627                 rng.gen::<uint>();
 628             }
 629         });
 630         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 631     }
 632
 633     #[bench]
 634     fn rand_isaac(b: &mut Bencher) {
 635         let mut rng: IsaacRng = OsRng::new().unwrap().gen();
 636         b.iter(|| {
 637             for _ in range(0, RAND_BENCH_N) {
 638                 rng.gen::<uint>();
 639             }
 640         });
 641         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 642     }
 643
 644     #[bench]
 645     fn rand_isaac64(b: &mut Bencher) {
 646         let mut rng: Isaac64Rng = OsRng::new().unwrap().gen();
 647         b.iter(|| {
 648             for _ in range(0, RAND_BENCH_N) {
 649                 rng.gen::<uint>();
 650             }
 651         });
 652         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 653     }
 654
 655     #[bench]
 656     fn rand_std(b: &mut Bencher) {
 657         let mut rng = StdRng::new().unwrap();
 658         b.iter(|| {
 659             for _ in range(0, RAND_BENCH_N) {
 660                 rng.gen::<uint>();
 661             }
 662         });
 663         b.bytes = size_of::<uint>() as u64 * RAND_BENCH_N;
 664     }
 665
 666     #[bench]
 667     fn rand_shuffle_100(b: &mut Bencher) {
 668         let mut rng = weak_rng();
 669         let x : &mut[uint] = &mut [1,..100];
 670         b.iter(|| {
 671             rng.shuffle(x);
 672         })
 673     }
 674 }