Объяснение алгоритма Mersenne Twister

Question

Я ищу для создания генератора случайных чисел Mersenne Twister в проекте. Однако, поскольку это для встроенного приложения, я позже буду оптимизировать код для моей архитектуры. Тем не менее, я могу найти небольшую документацию о том, как работает код, и я почти уверен, что это не пыль и волшебство. Есть ли хорошая документация, которую я, возможно, не замечаю? Блок-схемы были бы хороши. Если нет, я был бы признателен, если бы кто-нибудь мог дать мне пошаговое объяснение алгоритма. Благодаря!

Answer 1

Для фактического объяснения потребуется сначала несколько лет, чтобы получить математическую степень, но я могу дать вам свою версию основного кода состояния с ojrandlib, что проще, чем большинство из того, что вы найдете в сети , Моя структура g сохраняет состояние генератора: g->state является сам вектор состояния МТ, g->buf представляет собой выходной буфер из возвращенных случайных битов:

int i, j, k, n = g->statesize; 
uint32_t y, m, *s = g->state, *bp = g->buf + g->bufsize; 

for (i = 0; i < n; ++i) { 
    j = i + 1;  if (j >= n) j -= n; 
    k = i + 397; if (k >= n) k -= n; 

    m = (s[j] & 1) ? 0x9908b0df : 0; 
    s[i] = m^s[k]^(((s[i] & 0x80000000) | (s[j] & 0x7FFFFFFF)) >> 1); 
} 
for (i = 0; i < n; ++i) { 
    y = s[i]^(s[i] >> 11); 
    y ^= (y << 7) & 0x9d2c5680U; 
    y ^= (y << 15) & 0xefc60000U; 
    *--bp = y^(y >> 18); 
} 

Answer 2

Есть целый ряд статей по алгоритму позади генератора Мерсенн Twister случайных чисел перечисленные на Mersenne Twister site. Вы также можете найти сжатое объяснение в Википедии.