Integer Overflow

[Fernando Pérez]

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