Home Original page

Integer Overflow

Ursus Horibilis ursus_horibilis at hotmail.com
Tue Nov 27 13:24:08 EST 2001 
"Fernando Pérez" <fperez528 at yahoo.com> wrote in message
news:9u0jor$2li$1 at peabody.colorado.edu...
> Ursus Horibilis wrote:
>
> > Is there a way to force the Python run time system to
ignore
> > integer overflows?  I was trying to write a 32-bit Linear
> > Congruential Pseudo Random Number Generator and got
clobbered
> > the first time an integer product or sum went over the
32-bit
> > limit.
>
> well, you can always put the relevant parts in a try:..except
block, but I
> suspect that will kill the speed you need for a rng.

Yes, I did put the computation in a try-block and you're right,
it killed the speed, but worse, it also didn't store the
low-order 32-bits of the computation.

> If it's just an academic
> algorithm exercise

It's not.  Such computations are routinely used in algorithms
like PRNG's and cryptography.

> 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:

signed char a = 127; /* in binary = 01111111 */

a = a * 2;   /* Because of sign, a = (-2) */

a = a * 2;  /*  Because of sign, a = (-4) */

a = a + 128; /* Sign bit gets inverted, a = 124 */


> Are you relying on this 'feature' in your
> algorithm? I'm just curious about to whether asking to ignore
an overflow
> without triggering an exception is a design feature or a flaw
of the way you
> are doing things.

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.

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?
More information about the Python-list mailing list