# 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