MIXMAX generator

{{COI|date=April 2016}}

{{Infobox Algorithm

|class=pseudorandom number generator

|image=Mixmax_rplot.png

|caption=A pseudorandom number generator.

|data=Array

|time=O(n)

|best-time=O(n)

|average-time=O(n)

|space=O(n)

|optimal=Yes

}}

The MIXMAX generator is a family of pseudorandom number generators (PRNG) and is based on Anosov C-systems (Anosov diffeomorphism) and Kolmogorov K-systems (Kolmogorov automorphism). It was introduced in a 1986 preprint by G. Savvidy and N. Ter-Arutyunyan-Savvidy and published in 1991.{{cite journal |doi=10.1016/0021-9991(91)90015-D|title=On the Monte Carlo simulation of physical systems|journal=Journal of Computational Physics|volume=97|issue=2|pages=566|year=1991|last1=Savvidy|first1=G.K|last2=Ter-Arutyunyan-Savvidy|first2=N.G|bibcode=1991JCoPh..97..566S}}

A fast implementation in C/C++ of the generator was developed by Konstantin Savvidy.{{cite journal |first=K. |last=Savvidy |date=2015 |arxiv=1403.5355|title=The MIXMAX Random Number Generator |journal=Computer Physics Communications |volume=196 |pages=161–165 |doi= 10.1016/j.cpc.2015.06.003 |bibcode=2015CoPhC.196..161S |s2cid=16908633 }} It is genuine 64-bit generator. The period of the generator is $10^\{4389\}$ and the Kolmogorov entropy is $8679.2$ for the matrix size $N\; =\; 240$.{{cite journal |first1=K. |last1=Savvidy |first2=G. |last2=Savvidy |date=2015 |arxiv=1510.06274|title=Spectrum and Entropy of C-systems MIXMAX Random Number Generator |journal=Chaos, Solitons and Fractals |volume=91 |pages=33–38 |doi= 10.1016/j.chaos.2016.05.003 |bibcode=2016CSF....91...33S |s2cid=119291387 }} That generator occupies less than 2 kb, and if a smaller generator state is required, a N = 17 version with less than 200 bytes memory requirement also exists.

The generator works on most 64-bit systems, including 64-bit Linux flavors and Intel Mac. It has also been tested on PPC and ARM architectures. The latest version also runs on 32-bit systems and on Windows. The generator is equally usable with C++ programs,{{cite web|url=https://www.boost.org/doc/libs/1_76_0/boost/random/mixmax.hpp |title=boost|publisher=proj-www.boost.org}} has been chosen as the default generator in CLHEP{{cite web|url=http://proj-clhep.web.cern.ch/proj-clhep/ |title=CLHEP|publisher=proj-clhep.web.cern.ch}} for use in Geant4{{cite web|url=https://gitlab.cern.ch/CLHEP/CLHEP/blob/develop/Random/src/MixMaxRng.cc|title=Geant4 |date=15 December 2022 |publisher=proj-clhep.web.cern.ch}} and there exists a ROOT interface {{cite web|url=https://root.cern.ch/doc/master/classTRandom.html|title=ROOT - ROOT::Math::MixMaxEngine Class|publisher=root.cern.ch|access-date=2016-04-09}} and a PYTHIA interface. {{cite web|url=http://home.thep.lu.se/~bierlich/misc/keyword-manual/RandomNumbers.html|title=PYTHIA - PYTHIA::Random::MixMaxRndm class|publisher=thep.lu.se|access-date=2022-01-01}} It has been recently tested extensively on very wide variety of platforms, as part of the CLHEP/Geant4 release. EU-funded MIXMAX project {{cite web|url=https://ec.europa.eu/research-and-innovation/en/projects/success-stories/all/fastest-random-number-generator-could-cut-energy-bills|title= Fastest random number generator could cut energy bills|publisher= commission.europa.eu/index_en}}

An analysis by L’Ecuyer, Wambergue and Bourceret,{{Cite web |first1=Pierre |last1=L’Ecuyer |first2=Paul |last2=Wambergue |first3=Erwan |last3=Bourceret |date=September 22, 2017 |title=Spectral Analysis of the MIXMAX Random Number Generators |url=http://www.iro.umontreal.ca/~lecuyer/myftp/papers/mixmax-lattice.pdf}} see also,{{Cite journal |first1=N. |last1=Martirosyan |first2=K. |last2=Savvidy |first3=G. |last3=Savvidy |date=Nov 19, 2018 |title= Spectral Test of the MIXMAX Random Number Generator |journal=Chaos, Solitons and Fractals |volume=118 |pages=242–248 |doi= 10.1016/j.chaos.2018.11.024| arxiv=1806.05243|s2cid=51687163 }} showed that MIXMAX generators has a lattice structure when the produced random numbers are considered in n - dimensional space larger than the dimension N of the matrix generator, and only in that high dimensions n > N they lie on a set of parallel hyperplanes and determined the maximum distance between the covering hyperplanes.