我读过“梅森扭曲器的计算复杂度是 O(p2)，其中 p 是多项式的次数”。
生成 2 个 n 随机数所需的时间是生成 n 随机数的两倍，因此 Mersenne Twister 的时间复杂度为 O(1)，这意味着生成单个随机数需要恒定的时间；请注意，这可能是摊销的复杂性，因为 Mersenne Twister 通常会计算一批随机数，然后一次分配一个随机数，直到该批次被消耗，此时它会计算更多。您引用的谷歌搜索说的是同样的事情，尽管它试图更精确地确定该常数。计算复杂度通常指时间复杂度，尽管在某些情况下它也可以指空间复杂度。
如果您查看原始论文中
generategenerate这是 Mersenne Twister 的一个版本，它不会计算一批 624 个字的新状态。它为每次调用计算状态中的一个新单词。这对于实时 DSP 或嵌入式系统来说要好得多。我认为 Knuth 制作了一个比原始函数更好的初始化函数（这里重命名为
seed_initial_state()请记住，在大小为
NNMN-MN-1我将可调用函数、状态数组、状态数组索引和其他变量的名称更改为更简单的名称。最坏情况下的执行时间成本要好得多，因为将批处理分配到每个迭代的基础上。这对于实时性更好并且非常紧凑。
/*
A C-program for MT19937: Integer version (1999/10/28)
random_uint32() generates one pseudorandom unsigned integer (32bit)
which is uniformly distributed among 0 to 2^32 - 1 for each
call. seed_initial_state(seed) sets initial values to the working area
of 624 words. Before random_uint32(), seed_initial_state(seed) must be
called once. (seed is any 32-bit integer.)
Coded by Takuji Nishimura, considering the suggestions by
Topher Cooper and Marc Rieffel in July-Aug. 1997.
Formatting modifications for streamlined performance and
better readability by Robert Bristow-Johnson April 26th 2024
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later
version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General
Public License along with this library; if not, write to the
Free Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA
Copyright (C) 1997, 1999 Makoto Matsumoto and Takuji Nishimura.
Any feedback is very welcome. For any question, comments,
see http://www.math.keio.ac.jp/matumoto/emt.html or email
[email protected]
REFERENCE
M. Matsumoto and T. Nishimura,
"Mersenne Twister: A 623-Dimensionally Equidistributed Uniform
Pseudo-Random Number Generator",
ACM Transactions on Modeling and Computer Simulation,
Vol. 8, No. 1, January 1998, pp 3--30.
*/
#include <stdint.h>
// Period parameters
#define N 624
#define M 397 // not used directly in this version
#define K 227 // redefined from N-M
#define MATRIX_A 0x9908b0df // constant vector A
#define UPPER_MASK 0x80000000 // most significant w-r bits
#define LOWER_MASK 0x7fffffff // least significant r bits
// Tempering parameters
#define TEMPERING_MASK_B 0x9d2c5680
#define TEMPERING_MASK_C 0xefc60000
#define TEMPERING_SHIFT_U(x) (x >> 11)
#define TEMPERING_SHIFT_S(x) (x << 7)
#define TEMPERING_SHIFT_T(x) (x << 15)
#define TEMPERING_SHIFT_L(x) (x >> 18)
typedef struct
{
uint32_t state_array[N]; // the array for the state vector
int state_index; // index into state vector array
} mt_state;
uint32_t random_uint32(mt_state* state)
{
uint32_t* state_array = &(state->state_array[0]);
int n = state->state_index;
uint32_t x = state_array[n]; // get state from N iterations ago
int k = n - (N-1); // point to state N-1 iterations ago
if (k < 0) k += N; // modulo N circular indexing
uint32_t y = (x&UPPER_MASK) | (state_array[k]&LOWER_MASK);
uint32_t z = y >> 1;
if (y & 0x00000001) z ^= MATRIX_A;
k = n - K; // point to state K iterations ago
if (k < 0) k += N; // modulo N circular indexing
state_array[n++] = state_array[k] ^ z; // update new state
if (n >= N) n = 0; // modulo N circular indexing
state->state_index = n;
x ^= TEMPERING_SHIFT_U(x);
x ^= TEMPERING_SHIFT_S(x) & TEMPERING_MASK_B;
x ^= TEMPERING_SHIFT_T(x) & TEMPERING_MASK_C;
x ^= TEMPERING_SHIFT_L(x);
return x;
}
/*
seed_initial_state(&state, 4357); a default initial seed
Initializing the state_array from a seed
*/
void seed_initial_state(mt_state* state, uint32_t seed)
{
uint32_t* state_array = &(state->state_array[0]);
for (int n=0; n<N; n++)
{
state_array[n] = seed & 0xffff0000;
seed = 69069*seed + 1;
state_array[n] |= (seed >> 16) & 0x0000ffff;
seed = 69069*seed + 1;
}
state->state_index = 0;
}
/*
Initialization by "seed_initial_state()" is an example. Theoretically,
there are 2^19937-1 possible states as an intial state.
This function allows to choose any of 2^19937-1 ones.
Essential bits in "seed_array[]" is following 19937 bits:
(seed_array[0]&UPPER_MASK), seed_array[1], ..., seed_array[N-1].
(seed_array[0]&LOWER_MASK) is discarded.
Theoretically,
(seed_array[0]&UPPER_MASK), seed_array[1], ..., seed_array[N-1]
can take any values except all zeros.
*/
void set_initial_state(mt_state* state, uint32_t *seed_array)
{ // the length of seed_array[] must be at least N
uint32_t* state_array = &(state->state_array[0]);
for (int n=0; n<N; n++)
{
state_array[n] = seed_array[n];
}
state->state_index = 0;
}
/* This main() outputs first 1000 generated numbers.
main()
{
mt_state state;
seed_initial_state(&state, 4357);
for (int i=0; i<1000; i++)
{
printf("%10lu ", random_uint32());
if (i%5==4) printf("\n");
}
}
*/