README.md 4.83 KB
Newer Older
1
# RANLUX Tools
Christoph Conrads's avatar
Christoph Conrads committed
2

Christoph Conrads's avatar
Christoph Conrads committed
3
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/).
4

5 6 7 8 9 10 11
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/).
12

13 14

A ranlux PRNG works as follows:
Christoph Conrads's avatar
Christoph Conrads committed
15
* It draws `p` random values from an add-with-carry (AWC) PRNG or a subtract-with-borrow (SWB) PRNG.
16 17 18 19 20 21 22
* 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`.

Christoph Conrads's avatar
Christoph Conrads committed
23
Valid parameter choices must fulfill certain number theoretical criteria and the search for such parameters is automated by the scripts in this repository.
24 25 26

AWC and SWB PRNGs were introduced in a paper by Marsaglia and Zaman:

Christoph Conrads's avatar
Christoph Conrads committed
27 28 29
> 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:
30

Christoph Conrads's avatar
Christoph Conrads committed
31
> B. Hayes: "The Wheel of Fortune." In: American Scientist, Vol. 81.2 (1993), pp. 114-118. https://core.ac.uk/display/21804963
32

Christoph Conrads's avatar
Christoph Conrads committed
33
Judicously discarding values resolves these issues and this was discussed by Lüscher:
34

Christoph Conrads's avatar
Christoph Conrads committed
35 36 37 38
> 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`.
39
* `cawc` is a complementary AWC generator.
Christoph Conrads's avatar
Christoph Conrads committed
40 41 42 43 44 45 46 47
* `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.
48 49 50 51


# Appendix: Integer Factorization with GMP-ECM

Christoph Conrads's avatar
Christoph Conrads committed
52
GMP-ECM reads the integers to factorize from standard input and it can also parse input like `2^8+1`.
53 54 55 56 57 58 59 60 61

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
```
Christoph Conrads's avatar
Christoph Conrads committed
62
Pass only one number at a time and remember that this program prints in input in hexadecimal. This can be very confusing:
63 64 65 66
```
$ openssl prime 295
127 is not prime
```
Christoph Conrads's avatar
Christoph Conrads committed
67
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):
68 69 70 71 72
```sh
echo 123 | ecm -q -c 107 11e3
echo 123 | ecm -q -c 261 5e4
...
```
Christoph Conrads's avatar
Christoph Conrads committed
73 74 75 76 77
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
78
```
Christoph Conrads's avatar
Christoph Conrads committed
79
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.