Skip to content

Random Functions

Overview

To use randomization techniques, a prerequisite is the ability to generate random numbers quickly. This article introduces common methods for generating random numbers.

Random Numbers and Pseudorandom Numbers

It is meaningless to call a single number a "random number," so in the following discussion, we default to discussing "random sequences." Even when we mention "random numbers," we refer to "an element in a random sequence."

Existing computer operations are deterministic. Therefore, it is impossible to generate truly unpredictable and non‑repeatable random sequences using algorithms alone.

However, in most cases, we do not require such strong randomness. Instead, we only need the generated sequence to possess various statistical characteristics of a random sequence (such as uniform distribution, independence, etc.). Such a sequence is called a pseudorandom number sequence.

Examples of applications of random numbers and pseudorandom numbers in real life and algorithms:

  • Sampling surveys often only require pseudorandom numbers because we are only concerned with statistical characteristics.
  • Network security often requires stronger random numbers (than the pseudorandom numbers mentioned above) because attackers may exploit predictability.
  • Random algorithms used in OI/ICPC generally only require pseudorandom numbers. This is because these algorithms introduce randomness to incorporate probability into complexity analysis, thereby reducing complexity. This essentially still only utilizes the statistical characteristics of random numbers.
  • Certain randomized algorithms (e.g., Moser’s algorithm) rely on entropy‑related properties of random numbers and therefore must use true random numbers.

Implementation

rand

Used to generate pseudorandom numbers. Its drawback is that it is relatively slow. Requires #include<cstdlib>.

Calling rand() returns a random non‑negative integer in [0,RAND_MAX], where RAND_MAX is a macro defined in the standard library. On Linux systems, RAND_MAX equals \(2^{31}-1\). Modulo operation can be used to limit the size of the generated numbers.

Using rand() requires a random seed. The function srand(seed) can be used to change the random seed to seed. Of course, not initializing it is also possible.

If the same program runs twice with the same seed on the same machine and compiler, the random results will be identical.

One option is to use the current system time as the random seed: srand(time(nullptr)).

Warning

On Windows systems, the return value of rand() ranges over \(\left[0,2^{15}\right)\) (i.e., RAND_MAX equals \(2^{15}-1\)). When numbers not less than \(2^{15}\) are needed, it is recommended to use (rand() << 15 | rand()) to generate larger random numbers.

Regarding the randomness of rand() and rand()%n:

  • The C/C++ standard does not specify any quality aspects of the random numbers generated by rand().
  • The implementation of rand() in the GCC compiler guarantees basic properties such as uniform distribution but has obvious defects such as short low‑order period length. (For example, on the author’s machine, the period of the sequence generated by rand()%2 is about \(2\cdot 10^6\).)
  • Even assuming rand() is uniformly random, rand()%n cannot guarantee uniformity because each number in [0,n) may appear a different number of times among 0%n,1%n,...,RAND_MAX%n.

Predefined Random Number Generators

Several special popular algorithms are defined. Unless otherwise specified, they are defined in the header <random>.

Warning

Predefined random number generators are only available starting from the C++11 standard3.

mt19937

A random number generator class with the same utility as rand(). The range of random numbers is the same as the range of unsigned int.

Its advantages are higher quality random numbers (one manifestation is a longer cycle period; other aspects are at least not inferior to rand()) and much faster speed than rand(). Requires #include<random>.

mt19937 is based on a 32‑bit Mersenne Twister, designed by Matsumoto and Nishimura in 19981. To use it, define a random number generator: std::mt19937 myrand(seed). The seed can be omitted; if omitted, a default random seed is used.

mt19937 overloads operator (). When a random number is needed, calling myrand() returns a random number.

Another similar generator is mt19937_64, based on a 64‑bit Mersenne Twister, designed by Matsumoto and Nishimura in 2000. Usage is the same as mt19937, but the random number range is expanded to the range of unsigned long long.

Code Example 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <ctime>
#include <iostream>
#include <random>

using namespace std;

int main() {
  mt19937 myrand(time(nullptr));
  cout << myrand() << endl;
  return 0;
}

minstd_rand0

The linear congruential algorithm was discovered by Lewis, Goodman, and Miller in 1969 and adopted by Park and Miller in 1988 as the "minimal standard."

The calculation formula is as follows, where \(A,C,M\) are predefined constants.

\[ s_i\equiv s_{i-1}\times A+C\mod{M} \]

minstd_rand() is a newer "minimal standard" recommended by Park, Miller, and Stockmeyer in 1993.

For minstd_rand0(), \(s\) is a 32‑bit unsigned integer, \(A\) is 16807, \(C\) is 0, and \(M\) is 2147483647.

For minstd_rand(), \(s\) is a 32‑bit unsigned integer, \(A\) is 48271, \(C\) is 0, and \(M\) is 2147483647.

random_shuffle

Used to randomly shuffle a specified sequence. Requires #include<algorithm>.

Pass the pointers or iterators of the specified interval (left‑closed, right‑open): std::random_shuffle(first, last) or std::random_shuffle(first, last, myrand).

The internal random number generator defaults to rand(). A custom random number generator can also be passed.

Regarding the randomness of random_shuffle:

  • The C++ standard requires random_shuffle to select uniformly at random among all possible permutations, but the GCC2 compiler does not strictly enforce this.
  • One reason for the randomness defect in GCC’s random_shuffle is that it uses rand()%n. As mentioned earlier, this does not generate uniformly random integers.
  • Another reason is the limited range of rand(). If the length of the passed interval exceeds RAND_MAX, certain permutations become impossible to generate4.
Warning

random_shuffle was deprecated in the C++14 standard and removed in the C++17 standard.

shuffle

Same utility as random_shuffle. Requires #include<algorithm>.

The difference is that a custom random number generator must be used: std::shuffle(first, last, myrand).

The shuffle implementation in GCC2 complies with the C++ standard requirement, i.e., it selects uniformly at random among all possible permutations.

Below is a data generator written using rand() and random_shuffle(). It generates random small data for 「ZJOI2012」灾难.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>

int a[100];

int main() {
  srand(time(nullptr));
  int n = rand() % 99 + 1;
  for (int i = 1; i <= n; i++) a[i] = i;
  std::cout << n << '\n';
  for (int i = 1; i <= n; i++) {
    std::random_shuffle(a + 1, a + i);
    int cnt = rand() % i;
    for (int j = 1; j <= cnt; j++) std::cout << a[j] << ' ';
    std::cout << 0 << '\n';
  }
}

Below is the same data generator written using mt19937 and shuffle().

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>

int a[100];

int main() {
  std::mt19937 rng(time(nullptr));
  int n = rng() % 99 + 1;
  for (int i = 1; i <= n; i++) a[i] = i;
  std::cout << n << '\n';
  for (int i = 1; i <= n; i++) {
    std::shuffle(a + 1, a + i, rng);
    int cnt = rng() % i;
    for (int j = 1; j <= cnt; j++) std::cout << a[j] << ' ';
    std::cout << 0 << '\n';
  }
}

Below is an implementation that randomly permutes the first ten positive integers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>

int main() {
  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  std::random_device rd;
  std::mt19937 g(rd());

  std::shuffle(v.begin(), v.end(), g);

  std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\n";
}

Non‑deterministic Uniform Integer Random Number Generator

random_device is a hardware‑based uniform random number generator that can generate random numbers quickly until the entropy pool is exhausted. This class is defined in C++11 and requires the random header. Because performance degrades sharply after the entropy pool is exhausted, it is recommended to use this method to generate seeds for pseudorandom number generators like mt19937 rather than generating directly.

random_device is a non‑deterministic uniform random bit generator, although if non‑deterministic random number generation is not supported, implementations are allowed to use a pseudorandom number engine. The author has not yet received reports that NOIP judging machines do not support hardware‑based uniform random number generation. However, for conservative reasons, it is recommended to use this algorithm to generate random seeds.

Reference code is as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <map>
#include <random>
#include <string>

int main() {
  std::random_device rd;
  std::map<int, int> hist;
  std::uniform_int_distribution<int> dist(0, 9);
  for (int n = 0; n < 20000; ++n) {
    ++hist[dist(rd)];  // Note: for demonstration only: once the entropy pool is exhausted,
                       // many random_device implementations degrade sharply in performance.
                       // For practical use, random_device is typically only used to
                       // seed pseudorandom number generators like mt19937.
  }
  for (auto p : hist) {
    std::cout << p.first << " : " << std::string(p.second / 100, '*') << '\n';
  }
}

Possible output is as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
0 : ********************
1 : *******************
2 : ********************
3 : ********************
4 : ********************
5 : *******************
6 : ********************
7 : ********************
8 : *******************
9 : ********************

Random Number Distributions

Here we introduce generating random numbers that appear according to a certain probability, such as uniform distribution, Bernoulli distribution, binomial distribution, geometric distribution, standard normal (Gaussian) distribution.

For specific class names, refer to the list in Pseudorandom number generation – Random number distributions.

Implementation

The following program simulates a six‑sided die.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <iostream>
#include <random>

int main() {
  std::random_device rd;   // will be used to obtain a seed for the random number engine
  std::mt19937 gen(rd());  // standard mersenne_twister_engine seeded with rd()
  std::uniform_int_distribution<> dis(1, 6);

  for (int n = 0; n < 10; ++n)
    // use dis to transform the random unsigned int generated by gen into an int in [1, 6]
    std::cout << dis(gen) << ' ';
  std::cout << '\n';
}

Other Implementation Methods

Sometimes we need to implement our own random number generators. Below are some commonly used random number generation methods.

Linear Congruential Random Number Generator

Use the following formula to generate a random sequence \(\{R_i\}\):

\[ R_{i+1} = (A \times R_i + B) \bmod P \]

where \(A,B,P\) are constants.

This method is easy to implement, but the generated random sequence has a relatively short period (maximum period is \(P\), but in most cases it is shorter than \(P\)).

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

struct myrand {
  int A, B, P, x;

  myrand(int A, int B, int P) {
    this->A = A;
    this->B = B;
    this->P = P;
  }

  // generate the next random number in the sequence
  int next() { return x = (A * x + B) % P; }
};

myrand rnd(3, 5, 97);  // initialize a random number generator

int main() {
  int x = rnd.next();
  cout << x << endl;
  return 0;
}

Lagged Fibonacci Random Number Generator

Use the following formula to generate a random sequence \(\{R_i\}\) (where \(0 < j < k\)):

\[ R_i \equiv R_{i-j} \star R_{i-k} \bmod P \]

Here \(P\) is usually a power of two (commonly \(2^{32}\) or \(2^{64}\)), and \(\star\) denotes a binary operator, which can be addition, subtraction, multiplication, or XOR.

Compared to traditional linear congruential random number generators, this method has a longer period, but randomness is more affected by initial conditions.

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
using namespace std;

struct myrand {
  vector<unsigned> vec;
  int l, j, k, cur;

  myrand(int l, int j, int k) {
    this->l = l;
    this->j = j;
    this->k = k;
    cur = 0;
    for (int i = 0; i < l; i++) {
      vec.push_back(rand());  // first generate the first few elements of the sequence using other methods
    }
  }

  unsigned next() {
    vec[cur] = vec[(cur - j + l) % l] * vec[(cur - k + l) % l];
    // using unsigned type here automatically implements modulo 2^32
    return vec[cur++];
  }
};

myrand rnd(11, 4, 7);

int main() {
  unsigned x = rnd.next();
  cout << x << endl;
  return 0;
}

References and Notes

  1. Mersenne Twister algorithm ↩

  2. Version GCC 9.2.0 ↩↩

  3. Pseudorandom number generation - cppreference.com ↩

  4. Don't use rand(): a guide to random number generators in C++ ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用