Integer Overflow
Ursus Horibilis
ursus_horibilis at hotmail.com
Tue Nov 27 19:24:08 CET 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