From 1c2dcd1125d4a542a7b4b291e8de1f3b3cdc86a0 Mon Sep 17 00:00:00 2001 From: Gertjan van den Burg Date: Thu, 30 Jul 2015 18:48:58 +0200 Subject: By passing numbers between R and C as doubles we can avoid the limitations of the R integer type. This allows us to create a uniform RNG. --- Makefile | 3 +- README.md | 13 ++------ SyncRNG.R | 4 +-- syncrng.c | 104 ++++++++++++++++++++++++++++++++++---------------------------- 4 files changed, 63 insertions(+), 61 deletions(-) diff --git a/Makefile b/Makefile index da2d612..a057166 100644 --- a/Makefile +++ b/Makefile @@ -14,5 +14,4 @@ R: clean: rm -rf build - rm -f *.so *.o - rm *.pyc + rm -f *.so *.o *.pyc diff --git a/README.md b/README.md index 4d4c244..ac9a83e 100644 --- a/README.md +++ b/README.md @@ -52,18 +52,11 @@ You'll notice that the random numbers are indeed the same. Notes ----- -Since R is not capable of reliably handling integers larger than `2^32 - 1`, -the random numbers are internally capped at this value (using a bitwise and -with `0x7FFFFFF`), this influences the quality of the random numbers. The -random numbers are no longer uniformly distributed on `[0, 2^32 -1]`. For the -intended use of SyncRNG this is not a problem, but it is a compromise worth -considering when using SyncRNG. SyncRNG should definitely not be used for any -cryptographic purposes. +The random numbers are uniformly distributed on `[0, 2^32 - 1]`. TODO ---- -Future versions may include a random number generator that does not need -capping, and is uniform. It may also provide easier system-wide installation -through an R package and a Python module. +It may be easier to provide system-wide installation through an R package and +a Python module. diff --git a/SyncRNG.R b/SyncRNG.R index 23be4d2..1849d89 100644 --- a/SyncRNG.R +++ b/SyncRNG.R @@ -11,13 +11,13 @@ SyncRNG <- setRefClass('SyncRNG', initialize=function(..., seed=0) { seed <<- seed tmp <- .Call('R_syncrng_seed', - as.integer(seed)) + as.numeric(seed)) state <<- tmp[1:4] callSuper(...) }, randi=function() { tmp <- .Call('R_syncrng_rand', - as.integer(state)) + as.numeric(state)) state <<- tmp[1:4] return(tmp[5]) }, diff --git a/syncrng.c b/syncrng.c index deb9439..668c39e 100644 --- a/syncrng.c +++ b/syncrng.c @@ -15,9 +15,9 @@ * * @details * This generates random numbers according to the process described in [1]. As - * an additional step, the state variables are capped to 0x7FFFFFFF using a - * bitwise and. This is to overcome limitations of R. On return, the state - * variables are updated. + * an additional step, the resulting random number is capped to 0xFFFFFFFF + * using a bitwise and. This is done to yield the range [0, 2^32-1]. On + * return, the state variables are updated. * * [1]: @article{l1996maximally, * title={Maximally equidistributed combined Tausworthe generators}, @@ -34,7 +34,7 @@ * * @return a generated random number */ -int lfsr113(int **state) +unsigned long lfsr113(unsigned long **state) { unsigned long z1, z2, z3, z4, b; @@ -57,11 +57,12 @@ int lfsr113(int **state) b = (z1 ^ z2 ^ z3 ^ z4); - (*state)[0] = z1 & 0x7FFFFFFF; - (*state)[1] = z2 & 0x7FFFFFFF; - (*state)[2] = z3 & 0x7FFFFFFF; - (*state)[3] = z4 & 0x7FFFFFFF; - b = b & 0x7FFFFFFF; + (*state)[0] = z1; + (*state)[1] = z2; + (*state)[2] = z3; + (*state)[3] = z4; + + b = b & 0xFFFFFFFF; return(b); } @@ -72,32 +73,36 @@ int lfsr113(int **state) * @details * This function seeds the state array using a supplied seed value. As noted * in [1] (see lfsr113()), the values of z1, z2, z3, and z4 should be larger - * than 1, 7, 15, and 127 respectively. Here too the state variables are - * capped at 0x7FFFFFF. + * than 1, 7, 15, and 127 respectively. * * @param[in] seed user supplied seed value for the RNG * @param[out] state state of the RNG */ -void lfsr113_seed(unsigned long seed, int **state) +void lfsr113_seed(unsigned long seed, unsigned long **state) { unsigned long z1 = 2, z2 = 8, z3 = 16, z4 = 128; - z1 = (z1 * (seed + 1)) & 0x7FFFFFFF; - z2 = (z2 * (seed + 1)) & 0x7FFFFFFF; - z3 = (z3 * (seed + 1)) & 0x7FFFFFFF; - z4 = (z4 * (seed + 1)) & 0x7FFFFFFF; + z1 = (z1 * (seed + 1)); + z2 = (z2 * (seed + 1)); + z3 = (z3 * (seed + 1)); + z4 = (z4 * (seed + 1)); + + z1 = (z1 > 1) ? z1 : z1 + 1; + z2 = (z2 > 7) ? z2 : z2 + 7; + z3 = (z3 > 15) ? z3 : z3 + 15; + z4 = (z4 > 127) ? z4 : z4 + 127; if (*state == NULL) { - (*state) = malloc(sizeof(int)*4); + (*state) = malloc(sizeof(unsigned long)*4); } - (*state)[0] = (int) z1; - (*state)[1] = (int) z2; - (*state)[2] = (int) z3; - (*state)[3] = (int) z4; + (*state)[0] = z1; + (*state)[1] = z2; + (*state)[2] = z3; + (*state)[3] = z4; } #ifdef TARGETPYTHON @@ -109,13 +114,14 @@ void lfsr113_seed(unsigned long seed, int **state) static PyObject *syncrng_seed(PyObject *self, PyObject *args) { - int seed, *state = NULL; + unsigned long seed, *state = NULL; - if (!PyArg_ParseTuple(args, "i", &seed)) + if (!PyArg_ParseTuple(args, "k", &seed)) return NULL; lfsr113_seed(seed, &state); - PyObject *pystate = Py_BuildValue("[i, i, i, i]", + + PyObject *pystate = Py_BuildValue("[k, k, k, k]", state[0], state[1], state[2], state[3]); free(state); return pystate; @@ -123,7 +129,7 @@ static PyObject *syncrng_seed(PyObject *self, PyObject *args) static PyObject *syncrng_rand(PyObject *self, PyObject *args) { - int i, value, numints, *localstate; + unsigned long i, value, numints, *localstate; PyObject *listObj; PyObject *intObj; @@ -132,18 +138,18 @@ static PyObject *syncrng_rand(PyObject *self, PyObject *args) return NULL; // we're just assuming you would never pass more than 4 values - localstate = malloc(sizeof(int)*5); + localstate = malloc(sizeof(unsigned long)*5); numints = PyList_Size(listObj); for (i=0; i