SF patch 658251: Install a C implementation of the Mersenne Twister as the

core generator for random.py.

1 files changed, 528 insertions, 0 deletions

diff --git a/Modules/_randommodule.c b/Modules/_randommodule.c
new file mode 100644
index 0000000..35f10a5
--- /dev/null
+++ b/Modules/_randommodule.c
@@ -0,0 +1,528 @@
+/* Random objects */
+
+/* ------------------------------------------------------------------
+   The code in this module was based on a download from:
+	  http://www.math.keio.ac.jp/~matumoto/MT2002/emt19937ar.html
+
+   It was modified in 2002 by Raymond Hettinger as follows:
+
+	* the principal computational lines untouched except for tabbing.
+
+	* renamed genrand_res53() to random_random() and wrapped
+	  in python calling/return code.
+
+	* genrand_int32() and the helper functions, init_genrand()
+	  and init_by_array(), were declared static, wrapped in
+	  Python calling/return code.  also, their global data
+	  references were replaced with structure references.
+
+	* unused functions from the original were deleted.
+	  new, original C python code was added to implement the
+	  Random() interface.
+
+   The following are the verbatim comments from the original code:
+
+   A C-program for MT19937, with initialization improved 2002/1/26.
+   Coded by Takuji Nishimura and Makoto Matsumoto.
+
+   Before using, initialize the state by using init_genrand(seed)
+   or init_by_array(init_key, key_length).
+
+   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
+   All rights reserved.
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions
+   are met:
+
+     1. Redistributions of source code must retain the above copyright
+	notice, this list of conditions and the following disclaimer.
+
+     2. Redistributions in binary form must reproduce the above copyright
+	notice, this list of conditions and the following disclaimer in the
+	documentation and/or other materials provided with the distribution.
+
+     3. The names of its contributors may not be used to endorse or promote
+	products derived from this software without specific prior written
+	permission.
+
+   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+   Any feedback is very welcome.
+   http://www.math.keio.ac.jp/matumoto/emt.html
+   email: matumoto@math.keio.ac.jp
+*/
+
+/* ---------------------------------------------------------------*/
+
+#include "Python.h"
+#include <time.h>		// for seeding to current time
+
+/* Period parameters -- These are all magic.  Don't change. */
+#define N 624
+#define M 397
+#define MATRIX_A 0x9908b0dfUL	/* constant vector a */
+#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
+#define LOWER_MASK 0x7fffffffUL /* least significant r bits */
+
+typedef struct {
+	PyObject_HEAD
+	unsigned long state[N];
+	int index;
+} RandomObject;
+
+static PyTypeObject Random_Type;
+
+#define RandomObject_Check(v)	   ((v)->ob_type == &Random_Type)
+
+
+/* Random methods */
+
+
+/* generates a random number on [0,0xffffffff]-interval */
+static unsigned long
+genrand_int32(RandomObject *self)
+{
+	unsigned long y;
+	static unsigned long mag01[2]={0x0UL, MATRIX_A};
+	/* mag01[x] = x * MATRIX_A  for x=0,1 */
+	unsigned long *mt;
+
+	mt = self->state;
+	if (self->index >= N) { /* generate N words at one time */
+		int kk;
+
+		for (kk=0;kk<N-M;kk++) {
+			y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
+			mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
+		}
+		for (;kk<N-1;kk++) {
+			y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
+			mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
+	}
+		y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
+		mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
+
+		self->index = 0;
+	}
+
+    y = mt[self->index++];
+    y ^= (y >> 11);
+    y ^= (y << 7) & 0x9d2c5680UL;
+    y ^= (y << 15) & 0xefc60000UL;
+    y ^= (y >> 18);
+    return y;
+}
+
+/* random_random is the function named genrand_res53 in the original code;
+ * generates a random number on [0,1) with 53-bit resolution; note that
+ * 9007199254740992 == 2**53; I assume they're spelling "/2**53" as
+ * multiply-by-reciprocal in the (likely vain) hope that the compiler will
+ * optimize the division away at compile-time.  67108864 is 2**26.  In
+ * effect, a contains 27 random bits shifted left 26, and b fills in the
+ * lower 26 bits of the 53-bit numerator.
+ * The orginal code credited Isaku Wada for this algorithm, 2002/01/09.
+ */
+static PyObject *
+random_random(RandomObject *self)
+{
+	unsigned long a=genrand_int32(self)>>5, b=genrand_int32(self)>>6;
+    	return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
+}
+
+/* initializes mt[N] with a seed */
+static void
+init_genrand(RandomObject *self, unsigned long s)
+{
+	int mti;
+	unsigned long *mt;
+
+	mt = self->state;
+	mt[0]= s & 0xffffffffUL;
+	for (mti=1; mti<N; mti++) {
+		mt[mti] =
+		(1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
+		/* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
+		/* In the previous versions, MSBs of the seed affect   */
+		/* only MSBs of the array mt[]. 		       */
+		/* 2002/01/09 modified by Makoto Matsumoto	       */
+		mt[mti] &= 0xffffffffUL;
+		/* for >32 bit machines */
+	}
+	self->index = mti;
+	return;
+}
+
+/* initialize by an array with array-length */
+/* init_key is the array for initializing keys */
+/* key_length is its length */
+static PyObject *
+init_by_array(RandomObject *self, unsigned long init_key[], unsigned long key_length)
+{
+	unsigned int i, j, k;	/* was signed in the original code. RDH 12/16/2002 */
+	unsigned long *mt;
+
+	mt = self->state;
+	init_genrand(self, 19650218UL);
+	i=1; j=0;
+	k = (N>key_length ? N : key_length);
+	for (; k; k--) {
+		mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
+			 + init_key[j] + j; /* non linear */
+		mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+		i++; j++;
+		if (i>=N) { mt[0] = mt[N-1]; i=1; }
+		if (j>=key_length) j=0;
+	}
+	for (k=N-1; k; k--) {
+		mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
+			 - i; /* non linear */
+		mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+		i++;
+		if (i>=N) { mt[0] = mt[N-1]; i=1; }
+	}
+
+    mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
+    Py_INCREF(Py_None);
+    return Py_None;
+}
+
+/*
+ * The rest is Python-specific code, neither part of, nor derived from, the
+ * Twister download.
+ */
+
+static PyObject *
+random_seed(RandomObject *self, PyObject *args)
+{
+	PyObject *result = NULL;	/* guilty until proved innocent */
+	PyObject *masklower = NULL;
+	PyObject *thirtytwo = NULL;
+	PyObject *n = NULL;
+	unsigned long *key = NULL;
+	unsigned long keymax;		/* # of allocated slots in key */
+	unsigned long keyused;		/* # of used slots in key */
+
+	PyObject *arg = NULL;
+
+	if (!PyArg_UnpackTuple(args, "seed", 0, 1, &arg))
+		return NULL;
+
+	if (arg == NULL || arg == Py_None) {
+		time_t now;
+
+		time(&now);
+		init_genrand(self, (unsigned long)now);
+		Py_INCREF(Py_None);
+		return Py_None;
+	}
+	/* If the arg is an int or long, use its absolute value; else use
+	 * the absolute value of its hash code.
+	 */
+	if (PyInt_Check(arg) || PyLong_Check(arg))
+		n = PyNumber_Absolute(arg);
+	else {
+		long hash = PyObject_Hash(arg);
+		if (hash == -1)
+			goto Done;
+		n = PyLong_FromUnsignedLong((unsigned long)hash);
+	}
+	if (n == NULL)
+		goto Done;
+
+	/* Now split n into 32-bit chunks, from the right.  Each piece is
+	 * stored into key, which has a capacity of keymax chunks, of which
+	 * keyused are filled.  Alas, the repeated shifting makes this a
+	 * quadratic-time algorithm; we'd really like to use
+	 * _PyLong_AsByteArray here, but then we'd have to break into the
+	 * long representation to figure out how big an array was needed
+	 * in advance.
+	 */
+	keymax = 8; 	/* arbitrary; grows later if needed */
+	keyused = 0;
+	key = (unsigned long *)PyMem_Malloc(keymax * sizeof(*key));
+	if (key == NULL)
+		goto Done;
+
+	masklower = PyLong_FromUnsignedLong(0xffffffffU);
+	if (masklower == NULL)
+		goto Done;
+	thirtytwo = PyInt_FromLong(32L);
+	if (thirtytwo == NULL)
+		goto Done;
+	while (PyObject_IsTrue(n)) {
+		PyObject *newn;
+		PyObject *pychunk;
+		unsigned long chunk;
+
+		pychunk = PyNumber_And(n, masklower);
+		if (pychunk == NULL)
+			goto Done;
+		chunk = PyLong_AsUnsignedLong(pychunk);
+		Py_DECREF(pychunk);
+		if (chunk == (unsigned long)-1 && PyErr_Occurred())
+			goto Done;
+		newn = PyNumber_Rshift(n, thirtytwo);
+		if (newn == NULL)
+			goto Done;
+		Py_DECREF(n);
+		n = newn;
+		if (keyused >= keymax) {
+			unsigned long bigger = keymax << 1;
+			if ((bigger >> 1) != keymax) {
+				PyErr_NoMemory();
+				goto Done;
+			}
+			key = (unsigned long *)PyMem_Realloc(key,
+						bigger * sizeof(*key));
+			if (key == NULL)
+				goto Done;
+			keymax = bigger;
+		}
+		assert(keyused < keymax);
+		key[keyused++] = chunk;
+	}
+
+	if (keyused == 0)
+		key[keyused++] = 0UL;
+	result = init_by_array(self, key, keyused);
+Done:
+	Py_XDECREF(masklower);
+	Py_XDECREF(thirtytwo);
+	Py_XDECREF(n);
+	PyMem_Free(key);
+	return result;
+}
+
+static PyObject *
+random_getstate(RandomObject *self)
+{
+	PyObject *state;
+	PyObject *element;
+	int i;
+
+	state = PyTuple_New(N+1);
+	if (state == NULL)
+		return NULL;
+	for (i=0; i<N ; i++) {
+		element = PyInt_FromLong((long)(self->state[i]));
+		if (element == NULL)
+			goto Fail;
+		PyTuple_SET_ITEM(state, i, element);
+	}
+	element = PyInt_FromLong((long)(self->index));
+	if (element == NULL)
+		goto Fail;
+	PyTuple_SET_ITEM(state, i, element);
+	return state;
+
+Fail:
+	Py_DECREF(state);
+	return NULL;
+}
+
+static PyObject *
+random_setstate(RandomObject *self, PyObject *state)
+{
+	int i;
+	long element;
+
+	if (!PyTuple_Check(state)) {
+		PyErr_SetString(PyExc_TypeError,
+			"state vector must be a tuple");
+		return NULL;
+	}
+	if (PyTuple_Size(state) != N+1) {
+		PyErr_SetString(PyExc_ValueError,
+			"state vector is the wrong size");
+		return NULL;
+	}
+
+	for (i=0; i<N ; i++) {
+		element = PyInt_AsLong(PyTuple_GET_ITEM(state, i));
+		if (element == -1 && PyErr_Occurred())
+			return NULL;
+		self->state[i] = (unsigned long)element;
+	}
+
+	element = PyInt_AsLong(PyTuple_GET_ITEM(state, i));
+	if (element == -1 && PyErr_Occurred())
+		return NULL;
+	self->index = (int)element;
+
+	Py_INCREF(Py_None);
+	return Py_None;
+}
+
+/*
+Jumpahead should be a fast way advance the generator n-steps ahead, but
+lacking a formula for that, the next best is to use n and the existing
+state to create a new state far away from the original.
+
+The generator uses constant spaced additive feedback, so shuffling the
+state elements ought to produce a state which would not be encountered
+(in the near term) by calls to random().  Shuffling is normally
+implemented by swapping the ith element with another element ranging
+from 0 to i inclusive.  That allows the element to have the possibility
+of not being moved.  Since the goal is to produce a new, different
+state, the swap element is ranged from 0 to i-1 inclusive.  This assures
+that each element gets moved at least once.
+
+To make sure that consecutive calls to jumpahead(n) produce different
+states (even in the rare case of involutory shuffles), i+1 is added to
+each element at position i.  Successive calls are then guaranteed to
+have changing (growing) values as well as shuffled positions.
+
+Finally, the self->index value is set to N so that the generator itself
+kicks in on the next call to random().	This assures that all results
+have been through the generator and do not just reflect alterations to
+the underlying state.
+*/
+
+static PyObject *
+random_jumpahead(RandomObject *self, PyObject *n)
+{
+	long i, j;
+	PyObject *iobj;
+	PyObject *remobj;
+	unsigned long *mt, tmp;
+
+	if (!PyInt_Check(n) && !PyLong_Check(n)) {
+		PyErr_Format(PyExc_TypeError, "jumpahead requires an "
+			     "integer, not '%s'",
+			     n->ob_type->tp_name);
+		return NULL;
+	}
+
+	mt = self->state;
+	for (i = N-1; i > 1; i--) {
+		iobj = PyInt_FromLong(i);
+		if (iobj == NULL)
+			return NULL;
+		remobj = PyNumber_Remainder(n, iobj);
+		Py_DECREF(iobj);
+		if (remobj == NULL)
+			return NULL;
+		j = PyInt_AsLong(remobj);
+		Py_DECREF(remobj);
+		if (j == -1L && PyErr_Occurred())
+			return NULL;
+		tmp = mt[i];
+		mt[i] = mt[j];
+		mt[j] = tmp;
+	}
+
+	for (i = 0; i < N; i++)
+		mt[i] += i+1;
+
+	self->index = N;
+	Py_INCREF(Py_None);
+	return Py_None;
+}
+
+static PyObject *
+random_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
+{
+	RandomObject *self;
+	PyObject *tmp;
+
+	self = (RandomObject *)type->tp_alloc(type, 0);
+	if (self == NULL)
+		return NULL;
+	tmp = random_seed(self, args);
+	if (tmp == NULL) {
+		Py_DECREF(self);
+		return NULL;
+	}
+	Py_DECREF(tmp);
+	return (PyObject *)self;
+}
+
+static PyMethodDef random_methods[] = {
+	{"random",	(PyCFunction)random_random,  METH_NOARGS,
+		PyDoc_STR("random() -> x in the interval [0, 1).")},
+	{"seed",	(PyCFunction)random_seed,  METH_VARARGS,
+		PyDoc_STR("seed([n]) -> None.  Defaults to current time.")},
+	{"getstate",	(PyCFunction)random_getstate,  METH_NOARGS,
+		PyDoc_STR("getstate() -> tuple containing the current state.")},
+	{"setstate",	  (PyCFunction)random_setstate,  METH_O,
+		PyDoc_STR("setstate(state) -> None.  Restores generator state.")},
+	{"jumpahead",	(PyCFunction)random_jumpahead,	METH_O,
+		PyDoc_STR("jumpahead(int) -> None.  Create new state from "
+			  "existing state and integer.")},
+	{NULL,		NULL}		/* sentinel */
+};
+
+PyDoc_STRVAR(random_doc,
+"Random() -> create a random number generator with its own internal state.");
+
+static PyTypeObject Random_Type = {
+	PyObject_HEAD_INIT(NULL)
+	0,				/*ob_size*/
+	"_random.Random",		/*tp_name*/
+	sizeof(RandomObject),		/*tp_basicsize*/
+	0,				/*tp_itemsize*/
+	/* methods */
+	0,				/*tp_dealloc*/
+	0,				/*tp_print*/
+	0,				/*tp_getattr*/
+	0,				/*tp_setattr*/
+	0,				/*tp_compare*/
+	0,				/*tp_repr*/
+	0,				/*tp_as_number*/
+	0,				/*tp_as_sequence*/
+	0,				/*tp_as_mapping*/
+	0,				/*tp_hash*/
+	0,				/*tp_call*/
+	0,				/*tp_str*/
+	PyObject_GenericGetAttr,	/*tp_getattro*/
+	0,				/*tp_setattro*/
+	0,				/*tp_as_buffer*/
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,	/*tp_flags*/
+	random_doc,			/*tp_doc*/
+	0,				/*tp_traverse*/
+	0,				/*tp_clear*/
+	0,				/*tp_richcompare*/
+	0,				/*tp_weaklistoffset*/
+	0,				/*tp_iter*/
+	0,				/*tp_iternext*/
+	random_methods, 		/*tp_methods*/
+	0,				/*tp_members*/
+	0,				/*tp_getset*/
+	0,				/*tp_base*/
+	0,				/*tp_dict*/
+	0,				/*tp_descr_get*/
+	0,				/*tp_descr_set*/
+	0,				/*tp_dictoffset*/
+	0,				/*tp_init*/
+	PyType_GenericAlloc,		/*tp_alloc*/
+	random_new,			/*tp_new*/
+	_PyObject_Del,			/*tp_free*/
+	0,				/*tp_is_gc*/
+};
+
+PyDoc_STRVAR(module_doc,
+"Module implements the Mersenne Twister random number generator.");
+
+PyMODINIT_FUNC
+init_random(void)
+{
+	PyObject *m;
+
+	if (PyType_Ready(&Random_Type) < 0)
+		return;
+	m = Py_InitModule3("_random", NULL, module_doc);
+	Py_INCREF(&Random_Type);
+	PyModule_AddObject(m, "Random", (PyObject *)&Random_Type);
+}