OSDev.wiki

Random Number Generator: Difference between revisions

Page Discussion

Random Number Generator (view source)

Revision as of 18:22, 6 September 2021

615 bytes added ,  2 years ago
→‎Mersenne Twister: Replace implementation
[unchecked revision][unchecked revision]
VisualWikitext
(→‎Wichmann-Hill: Link the original paper)
(→‎Mersenne Twister: Replace implementation)
Line 187:
The Mersenne Twister is an incredibly popular PRNG and is available on most platforms; for example, it is part of the set of generators required by the C++11 standard library. An implementation of the 64-bit MT-19937 version in C is as follows:
 
Implementation according to Wikipedia:
<source lang="c">▼
// MT-19937-64. Declare mt_seed and mt_rand extern in some header
// Based on mt19937ar.c found here: http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/CODES/mt19937ar.c
 
▲<source lang="c">
#include <stddef.h>
#include <stdint.h>
#include <assert.h>
 
#ifdef USE32
#define W 64▼
typedef uint32_t word_t;
#define N 312▼
#define MSTATE_SIZE 156 624
#define RMIDDLE 31 397
#define INIT_SHIFT 30
#define INIT_FACT 1812433253
#define TWIST_MASK 0x9908b0df
#define SHIFT1 11
#define MASK1 0xffffffff
▲#define WSHIFT2 64 7
#define MASK2 0x9d2c5680
#define SHIFT3 15
#define MASK3 0xefc60000
#define SHIFT4 18
#else
typedef uint64_t word_t;
▲#define NSTATE_SIZE 312
#define MIDDLE 156
#define SINIT_SHIFT 17 62▼
#define TWIST_MASK 0xb5026f5aa96619e9
#define FINIT_FACT 6364136223846793005▼
#define TSHIFT1 37 29▼
#define MASK1 0x5555555555555555
#define LSHIFT2 43 17▼
#define MASK2 0x71d67fffeda60000
#define SHIFT3 37
#define MASK3 0xfff7eee000000000
#define SHIFT4 43
#endif
 
#define ALOWER_MASK 0xB5026F5AA96619E9ULL 0x7fffffff
#define UUPPER_MASK 29 (~(word_t)LOWER_MASK)
static word_t state[STATE_SIZE];
#define D 0x5555555555555555ULL
static unsigned intsize_t index = NSTATE_SIZE + 1;▼
▲#define S 17
#define B 0x71D67FFFEDA60000ULL
▲#define T 37
#define C 0xFFF7EEE000000000ULL
▲#define L 43
▲#define F 6364136223846793005
 
static void mt_twistseed(void)word_t {s)▼
#define MASK_LOW ((1ULL << R) - 1)
{
#define MASK_UPP (~MASK_LOW)
index = STATE_SIZE;
state[0] = seeds;▼
for (unsigned intsize_t i = 1; i < NSTATE_SIZE; i++i) {▼
state[i] = F(INIT_FACT * (state[i - 1] ^ (state[i - 1] >> (W - 2INIT_SHIFT))) + i;▼
}▼
 
static uint64_tvoid state[N];twist(void)
{
▲static unsigned int index = N + 1;
for (unsigned intsize_t i = 0; i < NSTATE_SIZE; i++i) {▼
 
}{▼
▲static void mt_twist(void) {
word_t x = (state[i] =& UPPER_MASK) | (state[(i + M1) % NSTATE_SIZE] ^& xaLOWER_MASK);▼
▲ for (unsigned int i = 0; i < N; ++i) {
uint64_t x = (state[i]x &>> MASK_UPP1) +^ (state[(ix +& 1)? %TWIST_MASK N] &: MASK_LOW0);
uint64_t xastate[i] = xstate[(i >>+ 1MIDDLE) % STATE_SIZE] ^ x;
if (x & 1) {▼
xa ^= A;
}
▲ state[i] = state[(i + M) % N] ^ xa;
}
index = 0;
}
 
static word_t mt_random(void)
void mt_seed(uint64_t seed) {
{
▲ state[0] = seed;
if (index >= N;STATE_SIZE)
▲ }{
▲ for (unsigned int i = 1; i < N; ++i) {
assert(index == STATE_SIZE || !"Generator never seeded");
▲ state[i] = F * (state[i - 1] ^ (state[i - 1] >> (W - 2))) + i;
▲ if twist(x & 1) {;
}
▲}
 
word_t y = state[index];
uint64_t mt_rand(void) {
ify ^= (indexy >=> NSHIFT1) {& MASK1;
y if^= (indexy ><< NSHIFT2) {& MASK2;
y ^= (y << SHIFT3) & mt_seed(5489)MASK3;
y ^= y >> }SHIFT4;
mt_twist();
▲ }
 
uint64_t y = state[index]++;
yreturn ^= (y >> U) & D;
}</source>▼
y ^= (y << S) & B;
 
y ^= (y << T) & C;
Some implementations automatically seed the generator with seed 5489, but this will (obviously) lead to the same outputs at every initialization.
y ^= y >> L;
 
++index;
return y;
}
▲</source>
 
It outperforms all PRNGs listed above, but it is rather slow due to its large state size. It also has problems in some statistical areas. See [https://arxiv.org/abs/1910.06437 "It is high time we let go of the Mersenne Twister"].
Anonymous user
Retrieved from "https://osdev.wiki/wiki/Special:MobileDiff/25187"