DX Random Number Generators

DX Random Number Generators

DX Random Number Generator, proposed first by Deng and Xu (2003), is a system of multiple recursive generators of modulus p and order k where all nonzero coefficients of the recurrence are equal. DX generators includes FMRG (Fast MRG), proposed by Deng and Lin (2000) as a special case. The advantage of this kind of generator is that a single multiplication is needed to compute the recurrence, so the generator would run faster than the general case.

We have several papers published recently regarding DX generators:

Deng, L. Y. (2005), “Efficient and Portable Multiple Recursive Generators of Large Order’’, ACM Transactions on Modeling and Computer Simulation, Vol. 15, No. 1, pages 1-13.
- Found and listed DX-47, DX-643 and DX-1597 generators with p=2³¹-1.
- The period of the DX-1597 generators is 10¹⁴⁹⁰³.
- Extend the DX RNG to a wider class and drastically increase the upper limit for multipliers coefficients.
- C code supplements.
Deng, L. Y. (2004), `` Generalized Mersenne Prime Number and Its Application to Random Number Generation’’, in ``Monte Carlo and Quasi-Monte Carlo Methods 2002 (H. Niederreiter, ed.), Springer-Verlag, pages 167-180.
- Proposed an efficient search algorithm to overcome the two major bottlenecks for the conditions given by Knuth (1998).
- Avoid the difficult problem of factoring (p^k-1) with consideration of a GMP for which (p^k-1)/(p-1) is a prime number.
- Provide an early exit strategy for non-primitive polynomial, speed up the search time by more than 1000 folds for a large order of MRG,
- Found and listed DX-k generators with k from 101 upto 1511 for general p=2³¹-c, where p is chosen that (p^k-1)/(p-1) is a prime.
- The period of the DX-1511 generators is 10^14100.5.
- Proposed an automatic generation of lots of efficient and maximum period MRGs from a DX generator given.
Deng, L. Y. and H. Q. Xu (2003), “A System of High-dimensional, Efficient, Long-cycle and Portable Uniform Random Number Generators’’, ACM Transactions on Modeling and Computer Simulation, Vol. 13, No. 4, pages 299-309.
- Proposed DX RNG extending the FMRG proposed by Deng and Lin (2000).
- Found and listed DX-102 and DX-120 generators with p=2³¹-1.
- The period of DX-120 generators is 10^1120..
- C code supplements.
Deng, L. Y. and Dennis K. J. Lin (2000), “ Random number generation for the new century”, American Statistician, Vol 54, No. 2, pages 145-150.
- Proposed FMRG which is a maximal period MRG with minimal number terms of nonzero coefficient.
- FMRG is alomst as efficient as the classical LCG.

Other links to DX generators:

Jean-Louis Foulley, of INRA-SGQA, wrote a note and APL implementation of DX-1597 as proposed in Deng (2005): Multiple Recursive Random Generators and their APL programmes, Technical report, INRA-SGQA, 14pp, 2005. You can download either zip file (note and APL program), pdf file of the note,, or APL program file that is directly usable under the DyalogAPL software.]