Integer Overflow
Fernando Pérez
fperez528 at yahoo.com
Mon Nov 26 13:30:51 CET 2001
Ursus Horibilis wrote:
>> If it's just an academic
>> algorithm exercise
>
> It's not. Such computations are routinely used in algorithms
> like PRNG's and cryptography.
>
Ok. Then, I suspect you'll end up writing it in C. I took a quick look at
Numeric's randomarray module, and it's basically a python wrapper around a C
module, ranlib.
>> Out of curiosity, though: I've never written a rng myself. In
> C, an integer
>> overflow silently goes to 0.
>
> No. In C, an integer overflow silently throws away the
> high-order bits, leaving the low-order bits just as they would
> be if you had a larger field. As an illustration, assume we
> are working with 8-bit integers instead of 32-bit. Then here's
> what happens with integer overflows:
>
Right. I haven't written C in a while, and I typically do floating point
stuff. Thanks for the reminder.
> The algorithm relys on the ability to ignore the fact that
> overflow has occurred and continue with the computation using
> the low-order bits. This is not my algorithm; it's as old as
> computer science, and then some.
Well, unfortunately it does seem like Python's builtin handling of ints just
precludes this. The alternative would be to operate with longs and mask off
2^32, but again speed goes out the window.
>
> Here is how we implement one particular 32-bit Linear
> Congruential Pseudo Random Number Generator in C:
>
> unsigned int Lcprng(unsigned int *seed)
> {
> *seed = 29 * (*seed) + 13;
> return (*seed);
> }
>
> How do you do this in Python?
Dunno. From what I can tell, you can't explicitly. On the other hand,
wrapping simple C functions for use from python is *very* easy. Take a look
at SWIG for details.
Cheers,
f
More information about the Python-list
mailing list