# RANLUX Tools
ranlux pseudo-random number generators (PRNGs) are a family of high-quality PRNGs with long periods. This git repository contains programs searching for valid ranlux parameters. The code is licensed under the [Mozilla Public License 2.0](https://www.mozilla.org/en-US/MPL/2.0/).
This code requires
* Bash,
* a C++11 compiler,
* a Python3 interpreter,
* Matplotlib and NumPy for Python3,
* a Python2 interpreter, and
* the Python2 module [primefac](https://pypi.org/project/primefac/).
A ranlux PRNG works as follows:
* It draws `p` random values from an add-with-carry (AWC) PRNG or a subtract-with-borrow (SWB) PRNG.
* It returns `r <= p` values and discards the rest.
* Repeat.
Ranlux PRNGs have four parameters and all of them are positive integers:
* Base `b >= 2`, long lag `r`, and short lag `s` with `r > s`.
* Block size `p >= r`.
Valid parameter choices must fulfill certain number theoretical criteria and the search for such parameters is automated by the scripts in this repository.
AWC and SWB PRNGs were introduced in a paper by Marsaglia and Zaman:
> G. Marsaglia, A. Zaman: "A New Class of Random Number Generators." In: The Annals of Applied Probability, Vol. 1.3 (1991), pp. 462-480.
AWC and SWB PRNGs have solid theoretical foundations but they fail empirical random number generator tests and lead to inaccurate results in physics simulations:
> B. Hayes: "The Wheel of Fortune." In: American Scientist, Vol. 81.2 (1993), pp. 114-118. https://core.ac.uk/display/21804963
Judicously discarding values resolves these issues and this was discussed by Lüscher:
> M. Lüscher: "A Portable High-Quality Random Number Generator for Lattice Field Theory Simulations." In: Computer Physics Communications, Vol. 79.1 (1994), pp. 100-110. arXiv:hep-lat/9309020.
The Bash script `find-awc-swb-prngs.sh` finds AWC/SWB parameters and block sizes. The output has to be read as follows:
* `awc` denotes with an add-with-carry PRNG with base `b`, long lag `r`, and short lag `s`.
* `cawc` is a complementary AWC generator.
* `swb` is a subtract-with-borrow PRNG with base `b`, long lag `r`, and short lag `s`. Its recurrence is `x_n = x_{n-r} - x_{n-s} - c`, where `c` is the carry bit.
* `swc` is a subtract-with-borrow PRNG with recurrence `x_n = x_{n-s} - x_{n-r} - c` (note the different order of the terms). This generator is also an SWB but seeing that the C++11 standard library calls the class implementing this generator `subtract_with_carry`, I decided to use the acronym `swc`.
* `t` is the time parameter from Lüscher's chaotic dynamical system discussion of AWC and SWBs PRNGs.
* `log2period` and `log10period` show the base-2 and base-10 logarithm of the period length bounds. **THE PERIOD LENGTHS ARE ONLY APPROXIMATIONS**.
The period lengths are only approximations because I am only superficially familiar with number theory. Moreover, computing the period length requires decomposing large integers into their prime factors. This is a hard problem and in many cases we do not even attempt to factorize numbers. In fact, the prime factorizations hard-coded in `compute-awc-swb-period-length.py` were computed by [GMP-ECM](http://ecm.gforge.inria.fr/).
To compute the block size `p`, we suggest to use the smallest prime number larger than `t * r`, e.g., for the popular 24-bit ranlux, we have `b=2^24`, `r=24`, `s=10`, and `t = 16`. It holds that `t * p = 16 * 24 = 384` so `p = 389`. Note that in practice, prime values larger than `t*p / 4` are often sufficient to pass all empirical random number generator tests.
# Appendix: Integer Factorization with GMP-ECM
GMP-ECM reads the integers to factorize from standard input and it can also parse input like `2^8+1`.
Find all small factors first using Pollard's Rho algorithm:
```sh
ecm -q -pm1 -c 107 11e3
```
Check for prime factors using `openssl prime`, e.g.,
```sh
openssl prime 3
```
Pass only one number at a time and remember that this program prints in input in hexadecimal. This can be very confusing:
```
$ openssl prime 295
127 is not prime
```
Take all non-prime factors and attempt to decompose them using elliptic curve factorization using the parameters found in [Optimal parameters for ECM](https://members.loria.fr/pzimmermann/records/ecm/params.html):
```sh
echo 123 | ecm -q -c 107 11e3
echo 123 | ecm -q -c 261 5e4
...
```
I suggest to prefix the ecm call with `time` because it shows the ecm return value and the return value contains information about the computed factors:
```
$ echo '2^(64*6)-1' | time -p /tmp/ecm/bin/ecm -q -pm1 -c 107 11e3
7341968051412347753761237695 6700417 22253377 65537 ((((2^(64*6)-1)/7341968051412347753761237695)/6700417)/22253377)/65537
Command exited with non-zero status 6
```
Your shell may have a built-in version of `time`. See [man(1) ecm](https://manpages.debian.org/jessie/gmp-ecm/gmp-ecm.1.en.html) for the meaning of the return values; everything else on this website is outdated.