Кіріспе
Псевдослучайный сан генераторы
Мерсенн Твистер – 1997 жылы Такудзи Нисимура (西村 拓士) және басқа да әзірлеушілер жасаған жалпы мақсаттағы псевдослучайный сан генераторы (PRNG). Оның атауы период ұзындығы ретінде Мерсенн санының таңдалуынан шыққан. Мерсенн Твистер ескі PRNG-ларда табылган көптеген кемшіліктерді түзету үшін арнайы құрастырылған. Мерсенн Твистер алгоритмінің ең көп қолданылатын нұсқасы Мерсенн санына негізделген. Оның стандартты іске асырылуы, MT19937, 32 биттік сөз ұзындығын қолданады. 64 биттік сөз ұзындығын пайдаланатын тағы бір іске асырылу бар (бес түрі бар), MT19937 64; ол басқа тізбек жасайды.
Бастапқылау
Мерсенн твистерін іске асыру үшін қажетті күй – әрқайсысы w биттен тұратын n мәндік массив. Массивті инициализациялау үшін w биттік тұқымдық мән тұқымдық мәнге орнатылып, содан кейін i-ден j-ға дейін келесідей орнатылады:
Алгоритмнің бірінші генерирлейтін мәні , емес , негізінде құралады. f тұрақтысы генератор үшін тағы бір параметр болып табылады, бірақ ол алгоритмнің тікелей бөлігі емес. MT19937 үшін f мәні 1812433253. MT19937 64 үшін f мәні 6364136223846793005. Оны Мацумото және Нишимура, сондай-ақ Марико Хагита мен Муцуо Сайто бірлесіп жасады. Ол eCRYPT желісінің eSTREAM жобасына ұсынылды. Негізгі сызықтық рекурренттік операциялар MT-ден кеңейтілген, ал параметрлер көптеген жіптердің рекурсияны параллель түрде есептеуіне мүмкіндік береді, сонымен қатар жад жүктемесін азайту үшін күй кеңістігін бөліседі. Мақалада MT-ге қарағанда жақсартылған тең таралу және ескі (2008 жылғы) GPU-да (Nvidia GTX260, 192 ядросы бар) 5 × 107 кездейсоқ 32 биттік бүтін сан үшін 4,7 мс өнімділік көрсетіледі. SFMT (SIMD-ге бағытталған жылдам Мерсенн твистері) – 2006 жылы ұсынылған Мерсенн твистерінің түрі, ол 128 биттік SIMD-де жұмыс істегенде жылдам болу үшін жасалған. Бұл Мерсенн твистерінен шамамен екі есе жылдам. Оның v биттік дәлдіктегі тең таралу қасиеттері MT-ге қарағанда жақсы, бірақ WELL ("Жақсы тең таратылған ұзақ кезеңді сызықтық")-ден нашар. Ол бастапқы күйден нөлдік артықтан MT-ге қарағанда жылдам қалпына келеді, бірақ WELL-ге қарағанда баяу. Ол 2607 − 1-ден 2216091 − 1-ге дейінгі әртүрлі кезеңдерді қолдайды. Intel SSE2 және PowerPC AltiVec SFMT-мен үйлесімді. Ол сондай-ақ PlayStation 3-те Cell BE-мен ойындарда қолданылады. TinyMT – 2011 жылы Сайто және Мацумото ұсынған Мерсенн твистерінің түрі. TinyMT тек 127 бит күй кеңістігін пайдаланады, бұл түпнұсқаның 2,5 КБ-ға қарағанда айтарлықтай азайту. Алайда, оның кезеңі түпнұсқадан әлдеқайда қысқа, сондықтан авторлар оны тек жад шектеулі жағдайларда ғана ұсынады.
The first value the algorithm then generates is based on , not on The constant f forms another parameter to the generator, though not part of the algorithm proper. The value for f for MT19937 is 1812433253. The value for f for MT19937 64 is 6364136223846793005. It was developed by Matsumoto and Nishimura alongside Mariko Hagita and Mutsuo Saito. It has been submitted to the eSTREAM project of the eCRYPT network. The basic linear recurrence operations are extended from MT and parameters are chosen to allow many threads to compute the recursion in parallel, while sharing their state space to reduce memory load. The paper claims improved equidistribution over MT and performance on an old (2008 era) GPU (Nvidia GTX260 with 192 cores) of 4.7 ms for 5×107 random 32 bit integers. The SFMT (SIMD oriented Fast Mersenne Twister) is a variant of Mersenne Twister, introduced in 2006, designed to be fast when it runs on 128 bit SIMD. It is roughly twice as fast as Mersenne Twister. It has a better equidistribution property of v bit accuracy than MT but worse than WELL ("Well Equidistributed Long period Linear"). It has quicker recovery from zero excess initial state than MT, but slower than WELL. It supports various periods from 2607 − 1 to 2216091 − 1. Intel SSE2 and PowerPC AltiVec are supported by SFMT. It is also used for games with the Cell BE in the PlayStation 3. TinyMT is a variant of Mersenne Twister, proposed by Saito and Matsumoto in 2011. TinyMT uses just 127 bits of state space, a significant decrease compared to the original's 2.5 KiB of state. However, it has a period of , far shorter than the original, so it is only recommended by the authors in cases where memory is at a premium.
Баламалар
Альтернативті генератор, WELL ("Well Equidistributed Long period Linear") жылдам қалпына келтіру, теңдей кездейсоқтық және шамамен бірдей жылдамдық ұсынады. Марсаглияның xorshift генераторлары мен түрлері LFSR класындағы ең жылдамдары болып табылады. 64 биттік MELG ("64 биттік Мерсендік ең үлкен кезеңді максималды тең таратылған сызықтық генераторлар") k таралу қасиеттері тұрғысынан толықтай оңтайландырылған. ACORN отбасы (1989 жылы жарияланған) – тағы бір k таратылған PRNG, ол MT-ге ұқсас есептеу жылдамдығын көрсетіп, қазіргі (2019) TestU01 критерийлерінің барлығын қанағаттандыратын жақсырақ статистикалық қасиеттерге ие; тиісті параметрлерді таңдағанда ACORN кез келген ұзақтықтағы кезеңге және дәлдікке қол жеткізе алады. PCG отбасы – заманауи ұзақ кезеңді генератор, жақсы кэш локалдығымен және қазіргі талдау әдістерімен анықтауға болатын азырақ бұрмалаушылыққа ие.