Генераторы псевдослучайных чисел: обзор алгоритмов.

Введение

Генераторы случайных чисел важны во многих областях технических приложений, включая физику, инженерию и математические компьютерные исследования (например, методы Монте-Карло), криптографию и азартные игры (на игровых серверах). Этот список охватывает множество распространенных типов, вне зависимости от их качества или пригодности для конкретной задачи.

генераторы псевдослучайных чисел (PRNG)

Следующие алгоритмы являются генераторами псевдослучайных чисел. GeneratorDateПервые сторонникиReferencesNotesМетод среднего квадрата1946J. von NeumannВ своей первоначальной форме имеет низкое качество и представляет лишь исторический интерес. Генератор Лемера1951D. H. LehmerОдин из самых ранних и наиболее влиятельных алгоритмов. Линейный конгруэнтный генератор (LCG)1958W. E. Thomson; A. RotenbergОбобщение генератора Лемера и исторически наиболее влиятельный и изученный генератор. Генератор Фибоначчи с запаздыванием (LFG)1958G. J. Mitchell и D. P. MooreРегистр сдвигов с линейной обратной связью (LFSR)1965R. C. TauswortheЧрезвычайно влиятельный алгоритм. Также называются генераторами Таусворта. Генератор Вихмана-Хилла1982B. A. Wichmann и D. I. HillКомбинация из трех небольших LCG, подходящая для 16-битных процессоров. Широко используется во многих программах, например, в Excel 2003 и более поздних версиях для функции Excel RAND, и был генератором по умолчанию в языке Python до версии 2.2. Правило 301983S. WolframОснован на клеточных автоматах. Инверсионный конгруэнтный генератор (ICG)1986J. Eichenauer и J. LehnBlum Blum Shub1986M. Blum, L. Blum и M. ShubBlum Blum Shub — это алгоритм ГПСЧ, который считается криптографически безопасным. Его основа основана на простых числах. Генератор Парка-Миллера1988S. K. Park и K. W. MillerКонкретная реализация генератора Лемера, широко используемая, поскольку она включена в C++ как функция minstd_rand0 начиная с C++11. ACORN generator1989 (открыт в 1984) R. S. WikramaratnaАддитивный конгруэнтный генератор случайных чисел. Прост в реализации, быстр, но не широко известен. При соответствующих инициализациях проходит все текущие эмпирические тесты и формально доказано, что сходится. Легко расширяется для произвольной длины периода и улучшает статистические характеристики в более высоких измерениях и с большей точностью. Генератор MIXMAX1991G. K. Savvidy и N. G. Ter Arutyunyan SavvidyЯвляется членом класса матричных линейных конгруэнтных генераторов, обобщением LCG. Обоснование семейства генераторов MIXMAX основано на результатах эргодической теории и классической механики. Добавление с переносом (AWC)1991G. Marsaglia и A. ZamanМодификация генераторов Фибоначчи с запаздыванием. Вычитание с заимствованием (SWB)1991G. Marsaglia и A. ZamanШироко используется, например, для моделирования физики частиц. Максимально периодические обратные величины1992R. A. J. MatthewsМетод, основанный на теории чисел, хотя никогда не использовался в практических приложениях. KISS1993G. MarsagliaПрототипический пример комбинированного генератора. Умножение с переносом (MWC)1994G. Marsaglia; C. KoçДополнительное умножение с переносом (CMWC)1997R. Couture и P. L’EcuyerМерсенн Твистер (MT)1998M. Matsumoto и T. NishimuraТесно связан с LFSR. В реализации MT19937, вероятно, является наиболее часто используемым современным ГПСЧ. Генератор по умолчанию в R и языке Python, начиная с версии 2.3. Xorshift2003G. MarsagliaЭто очень быстрый подтип генераторов LFSR. Марсалья также предложил в качестве улучшения генератор xorwow, в котором выход генератора xorshift добавляется к последовательности Вейля. Генератор xorwow является генератором по умолчанию в библиотеке CURAND интерфейса программирования приложений nVidia CUDA для графических процессоров. Хорошо равнораспределенный линейный генератор с длинным периодом (WELL)2006F. Panneton, P. L'Ecuyer и M. MatsumotoLFSR тесно связан с Мерсенном Твистером, направлен на устранение некоторых его недостатков. Небольшой некриптографический ГПСЧ (JSF)2007Bob JenkinsAdvanced Randomization System (ARS)2011J. Salmon, M. Moraes, R. Dror и D. ShawУпрощенная версия блочного шифра AES, обеспечивающая очень высокую производительность в системах, поддерживающих AES NI. Threefry2011J. Salmon, M. Moraes, R. Dror и D. ShawПериодические генераторы псевдослучайных чисел, основанные на технике бесконечных слов. SplitMix2014G. L. Steele, D. Lea и C. H. FloodОснован на окончательной функции смешивания MurmurHash3. Включен в Java Development Kit 8 и выше. Пермутированный конгруэнтный генератор (PCG)2014M. E. O'NeillМодификация LCG. Генератор случайных битов с циклом (RCB)2016R. CookmanRCB описывается как генератор битовых шаблонов, созданный для преодоления некоторых недостатков Мерсенна Твистера и ограничений коротких периодов/длины битов генераторов сдвига/модуля. ГПСЧ средней квадратной последовательности Вейла (см. также метод среднего квадрата)2017B. WidynskiВариация на оригинальном методе среднего квадрата Джона фон Неймана, этот генератор может быть самым быстрым ГПСЧ, который проходит все статистические тесты. Xoroshiro128+2018D. Blackman, S. VignaМодификация генераторов Xorshift Марсальи, один из самых быстрых генераторов на современных 64-битных процессорах. Связанные генераторы включают xoroshiro128**, xoshiro256+ и xoshiro256**. 64-битный MELG (MELG 64)2018S. Harase, T. KimotoРеализация 64-битных максимально равнораспределенных F2 линейных генераторов с периодом Мерсенна. Squares RNG2020B. WidynskiВерсия на основе счетчика ГПСЧ средней квадратной последовательности Вейла. Подобен Philox по конструкции, но значительно быстрее.

The following algorithms are pseudorandom number generators. GeneratorDateFirst proponentsReferencesNotesMiddle square method1946J. von NeumannIn its original form, it is of poor quality and of historical interest only. Lehmer generator1951D. H. LehmerOne of the very earliest and most influential designs. Linear congruential generator (LCG)1958W. E. Thomson; A. Rotenberg A generalisation of the Lehmer generator and historically the most influential and studied generator. Lagged Fibonacci generator (LFG)1958G. J. Mitchell and D. P. MooreLinear feedback shift register (LFSR)1965R. C. TauswortheA hugely influential design. Also called Tausworthe generators. Wichmann–Hill generator1982B. A. Wichmann and D. I. HillA combination of three small LCGs, suited to 16 bit CPUs. Widely used in many programs, e. g. it is used in Excel 2003 and later versions for the Excel function RAND and it was the default generator in the language Python up to version 2.2. Rule 301983S. WolframBased on cellular automata. Inversive congruential generator (ICG)1986J. Eichenauer and J. LehnBlum Blum Shub1986M. Blum, L. Blum and M. ShubBlum Blum Shub is a PRNG algorithm that is considered cryptographically secure. Its base is based on prime numbers. Park Miller generator1988S. K. Park and K. W. MillerA specific implementation of a Lehmer generator, widely used because it is included in C++ as the function minstd rand0 from C++11 onwards. ACORN generator1989 (discovered 1984) R. S. WikramaratnaThe Additive Congruential Random Number generator. Simple to implement, fast, but not widely known. With appropriate initialisations, passes all current empirical test suites, and is formally proven to converge. Easy to extend for arbitrary period length and improved statistical performance over higher dimensions and with higher precision. MIXMAX generator1991G. K. Savvidy and N. G. Ter Arutyunyan SavvidyIt is a member of the class of matrix linear congruential generator, a generalisation of LCG. The rationale behind the MIXMAX family of generators relies on results from ergodic theory and classical mechanics. Add with carry (AWC)1991G. Marsaglia and A. ZamanA modification of Lagged Fibonacci generators. Subtract with borrow (SWB)1991G. Marsaglia and A. Zaman widely used e. g. for particle physics simulations. Maximally periodic reciprocals1992R. A. J. MatthewsA method with roots in number theory, although never used in practical applications. KISS1993G. MarsagliaPrototypical example of a combination generator. Multiply with carry (MWC)1994G. Marsaglia; C. KoçComplementary multiply with carry (CMWC)1997R. Couture and P. L’EcuyerMersenne Twister (MT)1998M. Matsumoto and T. NishimuraClosely related with LFSRs. In its MT19937 implementation is probably the most commonly used modern PRNG. Default generator in R and the Python language starting from version 2.3. Xorshift2003G. MarsagliaIt is a very fast sub type of LFSR generators. Marsaglia also suggested as an improvement the xorwow generator, in which the output of a xorshift generator is added with a Weyl sequence. The xorwow generator is the default generator in the CURAND library of the nVidia CUDA application programming interface for graphics processing units. Well equidistributed long period linear (WELL)2006F. Panneton, P. L'Ecuyer and M. MatsumotoA LFSR closely related with Mersenne Twister, aiming at remedying some of its shortcomings. A small noncryptographic PRNG (JSF) 2007Bob JenkinsAdvanced Randomization System (ARS)2011J. Salmon, M. Moraes, R. Dror and D. ShawA simplified version of the AES block cipher, leading to very fast performance on systems supporting the AES NI. Threefry2011J. Salmon, M. Moraes, R. Dror and D. ShawAperiodic pseudorandom number generators based on infinite words technique. SplitMix2014G. L. Steele, D. Lea and C. H. FloodBased upon the final mixing function of MurmurHash3. Included in Java Development Kit 8 and above. Permuted Congruential Generator (PCG)2014M. E. O'NeillA modification of LCG. Random Cycle Bit Generator (RCB)2016R. CookmanRCB is described as a bit pattern generator made to overcome some of the shortcomings with Mersenne Twister and short periods/bit length restriction of shift/modulo generators. Middle Square Weyl Sequence RNG (see also middle square method)2017B. WidynskiA variation on John von Neumann's original middle square method, this generator may be the fastest RNG that passes all the statistical tests. Xoroshiro128+2018D. Blackman, S. VignaA modification of Marsaglia's Xorshift generators, one of the fastest generators on modern 64 bit CPUs. Related generators include xoroshiro128**, xoshiro256+ and xoshiro256**.64 bit MELG (MELG 64)2018S. Harase, T. KimotoAn implementation of 64 bit maximally equidistributed F2 linear generators with Mersenne prime period. Squares RNG2020B. WidynskiA counter based version of Middle Square Weyl Sequence RNG. Similar to Philox in design but significantly faster.