MIXMAX generator
 | A major contributor to this article appears to have a close connection with its subject. (April 2016) |
| MIXMAX generator | |
|---|---|
 | |
| Class | pseudorandom number generator |
| Data structure | Array |
| Worst-case performance | O(n) |
| Best-case performance | O(n) |
| Average performance | O(n) |
| Worst-case space complexity | 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.[1]
The first realization of MIXMAX generator as a Fortran code, as well the first statistical tests were performed by Norayr Akopov. [2] The abbreviation MIXMAX for the created generator was first introduced in this article.
A fast implementation in C/C++ of the generator was developed by Konstantin Savvidy.[3] The generator outputs numbers in the interval [1 . . 261]. The period of the generator is and the Kolmogorov entropy is for the matrix size .[4] 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,[5] has been chosen as the default generator in CLHEP[6] for use in Geant4[7] and there exists a ROOT interface [8] and a PYTHIA interface. [9] It has been recently tested extensively on very wide variety of platforms, as part of the CLHEP/Geant4 release. EU-funded MIXMAX project [10]
An analysis by L’Ecuyer, Wambergue and Bourceret,[11] see also,[12] 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.
The generator multiplies a vector on the Galois field with 261 − 1 elements by a matrix on the same field, and coordinates of the vector are returned, incremented to obtain the target range. In view of the failures with collision tests reported by L’Ecuyer, Wambergue and Bourceret and subsequent failures on PractRand[13] tests, the currently published generator has been patched: the first coordinate of the vector is never used, and the MIXMAX256 generator has been decimated so to emit one output each three (i.e., two outputs on three are discarded).
Being linear on the base Galois field, all MIXMAX variants fail the modular rank and the modular linear-complexity tests[14]. This statistical bias can surface unexpectedly in linear-algebra computations[14], similarly to what happens with generators that are linear on the two-element Galois field.[15] This linearity is not contradicted by the chaoticity of the associated dynamical systems, as the points with a chaotic trajectory are those with irrational coordinates, whereas MIXMAX is based on the linear trajectory of rational points, which have a periodic behavior.
References
[edit]- ↑ Savvidy, G.K; Ter-Arutyunyan-Savvidy, N.G (1991). "On the Monte Carlo simulation of physical systems". Journal of Computational Physics. 97 (2): 566–572. Bibcode:1991JCoPh..97..566S. doi:10.1016/0021-9991(91)90015-D.
- ↑ Akopov, N.Z.; Savvidy, G.K; Ter-Arutyunyan-Savvidy, N.G (1991). "Matrix generator of pseudorandom numbers". Journal of Computational Physics. 97 (2): 573–579. Bibcode:1991JCoPh..97..566S. doi:10.1016/0021-9991(91)90016-E.
- ↑ Savvidy, K. (2015). "The MIXMAX Random Number Generator". Computer Physics Communications. 196: 161–165. arXiv:1403.5355. Bibcode:2015CoPhC.196..161S. doi:10.1016/j.cpc.2015.06.003. S2CID 16908633.
- ↑ Savvidy, K.; Savvidy, G. (2015). "Spectrum and Entropy of C-systems MIXMAX Random Number Generator". Chaos, Solitons and Fractals. 91: 33–38. arXiv:1510.06274. Bibcode:2016CSF....91...33S. doi:10.1016/j.chaos.2016.05.003. S2CID 119291387.
- ↑ "boost". proj-www.boost.org.
- ↑ "CLHEP". proj-clhep.web.cern.ch.
- ↑ "Geant4". proj-clhep.web.cern.ch. 15 December 2022.
- ↑ "ROOT - ROOT::Math::MixMaxEngine Class". root.cern.ch. Retrieved 2016-04-09.
- ↑ "PYTHIA - PYTHIA::Random::MixMaxRndm class". thep.lu.se. Retrieved 2022-01-01.
- ↑ "Fastest random number generator could cut energy bills". commission.europa.eu/index_en. January 2015.
- ↑ L’Ecuyer, Pierre; Wambergue, Paul; Bourceret, Erwan (September 22, 2017). "Spectral Analysis of the MIXMAX Random Number Generators" (PDF).
- ↑ Martirosyan, N.; Savvidy, K.; Savvidy, G. (Nov 19, 2018). "Spectral Test of the MIXMAX Random Number Generator". Chaos, Solitons and Fractals. 118: 242–248. arXiv:1806.05243. doi:10.1016/j.chaos.2018.11.024. S2CID 51687163.
- ↑ Doty-Humphrey, Chris. "PractRand". pracrand.sourceforge.net. Retrieved 2026-07-28.
- 1 2 Vigna, Sebastiano (2026-06-21). "Modular Rank and Linear-Complexity Tests for Pseudorandom Number Generators". arXiv:2606.22684 [cs.DS].
- ↑ Vigna, Sebastiano (2025-06-19). "It is high time we let go of the Mersenne Twister". arXiv:1910.06437 [cs.DS].
External links
[edit]- The open source MIXMAX C/C++ source code on hepforge.org
- William L. Dunn, J. Kenneth Shultis, (2022). Exploring Monte Carlo Methods, 2nd edition, Elsevier Science, ISBN 978-0-12-819739-4.