[Python-checkins] python/nondist/sandbox/twister _random.c,1.23,1.24 test_random.py,1.8,1.9
tim_one@users.sourceforge.net
tim_one@users.sourceforge.net
Sun, 29 Dec 2002 02:50:25 -0800
Update of /cvsroot/python/python/nondist/sandbox/twister
In directory sc8-pr-cvs1:/tmp/cvs-serv29441
Modified Files:
_random.c test_random.py
Log Message:
random_seed(): I believe all the error paths are refcount-correct now.
Reworked to grow the key vector directly, instead of indirecting thru
PyList_Append, then a second pass to fill key. Alas, it's a quadratic-
time algorithm (now and before), due to repeated shifting of a long by
32. We should expose enough of the long implementation so that
_PyLong_AsByteArray can become a generally useful function (that would
do the job in linear time).
Index: _random.c
===================================================================
RCS file: /cvsroot/python/python/nondist/sandbox/twister/_random.c,v
retrieving revision 1.23
retrieving revision 1.24
diff -C2 -d -r1.23 -r1.24
*** _random.c 29 Dec 2002 09:39:14 -0000 1.23
--- _random.c 29 Dec 2002 10:50:23 -0000 1.24
***************
*** 68,71 ****
--- 68,72 ----
#include "Python.h"
+ #include "longintrepr.h"
#include <time.h> // for seeding to current time
***************
*** 208,219 ****
{
PyObject *result = NULL; /* guilty until proved innocent */
- unsigned long *key;
- unsigned long keylength;
- unsigned long seed;
- unsigned int i;
- PyObject *split = NULL;
PyObject *masklower = NULL;
PyObject *thirtytwo = NULL;
PyObject *n = NULL;
PyObject *arg = NULL;
--- 209,218 ----
{
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;
***************
*** 230,234 ****
return Py_None;
}
!
if (PyInt_Check(arg) || PyLong_Check(arg))
n = PyNumber_Absolute(arg);
--- 229,235 ----
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);
***************
*** 242,247 ****
goto Done;
! split = PyList_New(0);
! if (split == NULL)
goto Done;
--- 243,258 ----
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;
***************
*** 253,267 ****
goto Done;
while (PyObject_IsTrue(n)) {
- PyObject *little;
PyObject *newn;
! int err;
! little = PyNumber_And(n, masklower);
! if (little == NULL)
goto Done;
! assert(PyLong_Check(little));
! err = PyList_Append(split, little);
! Py_DECREF(little);
! if (err == -1)
goto Done;
newn = PyNumber_Rshift(n, thirtytwo);
--- 264,277 ----
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);
***************
*** 270,297 ****
Py_DECREF(n);
n = newn;
! }
!
! if (PyList_Size(split) == 0)
! PyList_Append(split, PyLong_FromLong(0L));
!
! keylength = PyList_Size(split);
! key = (unsigned long *) PyMem_Malloc(keylength * sizeof(unsigned long));
! if (key == NULL)
! goto Done;
! for (i=0; i<keylength ; i++) {
! seed = PyLong_AsUnsignedLong(PyList_GET_ITEM(split, i));
! if (seed == -1 && PyErr_Occurred()) {
! PyMem_FREE(key);
! goto Done;
}
! key[i] = seed;
}
! result = init_by_array(self, key, keylength);
! PyMem_Free(key);
Done:
Py_XDECREF(masklower);
Py_XDECREF(thirtytwo);
Py_XDECREF(n);
! Py_XDECREF(split);
return result;
}
--- 280,307 ----
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;
}
Index: test_random.py
===================================================================
RCS file: /cvsroot/python/python/nondist/sandbox/twister/test_random.py,v
retrieving revision 1.8
retrieving revision 1.9
diff -C2 -d -r1.8 -r1.9
*** test_random.py 29 Dec 2002 09:39:14 -0000 1.8
--- test_random.py 29 Dec 2002 10:50:23 -0000 1.9
***************
*** 118,122 ****
self.assertEqual(round(a-e, 14), 0)
! def test_strong_referenceImplementation(self):
# Like test_referenceImplementation, but checks for exact bit-level
# equality. This should pass on any box where C double contains
--- 118,122 ----
self.assertEqual(round(a-e, 14), 0)
! def test_strong_reference_implementation(self):
# Like test_referenceImplementation, but checks for exact bit-level
# equality. This should pass on any box where C double contains
***************
*** 140,143 ****
--- 140,152 ----
for a, e in zip(actual, expected):
self.assertEqual(long(ldexp(a, 53)), e)
+
+ def test_long_seed(self):
+ # This is most interesting to run in debug mode, just to make sure
+ # nothing blows up. Under the covers, a dynamically resized array
+ # is allocated, consuming space proportional to the number of bits
+ # in the seed. Unfortunately, that's a quadratic-time algorithm,
+ # so don't make this horribly big.
+ seed = (1L << (10000 * 8)) - 1 # about 10K bytes
+ self.gen.seed(seed)
class TestModule(unittest.TestCase):