Bit-twiddling
Author Message
Bit-twiddling

I'm translating a numerical algorithm from C to Python, but have run
into a problem in that the algorithm seems to rely on the fact that
shifting, addition and multiplication all 'wrap' when the result
exceeds 32 bits.

Since the python equivalents do not, does there exist a common
workaround for this?

For example, I'd like

mt[0]= seed & 0xffffffff
for mti in range(1,n):
mt[mti]=(69069 * mt[mti-1]) & 0xffffffff

to never put anything that doesn't fit in an unsigned long in the mt
list.

Any ideas?

--Lars M.

Sun, 13 Jan 2002 03:00:00 GMT
Bit-twiddling
[Lars Marius Garshol]

Quote:
> I'm translating a numerical algorithm from C to Python, but have run
> into a problem in that the algorithm seems to rely on the fact that
> shifting, addition and multiplication all 'wrap' when the result
> exceeds 32 bits.

> Since the Python equivalents do not,

int left shift in Python is end-off and 0-fill and non-complaining (same as
in C); int right shift in Python is sign-extending (and undefined in C for
negative signed ints).  Python int + and * do gripe about overflow.

Quote:
> does there exist a common workaround for this?

The only easy workaround is to use longs, converting to int only when
necessary or expedient.  C defines unsigned int arithmetic to act "as if"
modulo the wordsize, and that's what long Python arithmetic (followed by

Quote:
> For example, I'd like

>     mt[0]= seed & 0xffffffff
>     for mti in range(1,n):
>         mt[mti]=(69069 * mt[mti-1]) & 0xffffffff

> to never put anything that doesn't fit in an unsigned long in the mt
> list.

Provided that seed was a long to begin with, this code almost works as is.
You just need to append "L" to the literals (for 69069 that isn't necessary,
it just avoids the repeated expense of runtime widening; for 0xffffffff it
*is* necessary on a 32-bit machine, else 0xffffffff == -1 gets widened
to -1L and then the masking doesn't accomplish anything (i & -1L == i for
all long i)).

The elements of mt are then all longs, but each one's *value* fits in a
32-bit C unsigned long:  numerically, it computes the same values as would
the C code.

if-you're-really-after-random-numbers-see-ivan-frohne-ly y'rs  - tim

Sun, 13 Jan 2002 03:00:00 GMT
Bit-twiddling

|
| I'm translating a numerical algorithm from C to Python, but have run
| into a problem in that the algorithm seems to rely on the fact that
| shifting, addition and multiplication all 'wrap' when the result
| exceeds 32 bits.
|
| Since the Python equivalents do not, does there exist a common
| workaround for this?
|
| For example, I'd like
|
|     mt[0]= seed & 0xffffffff
|     for mti in range(1,n):
|         mt[mti]=(69069 * mt[mti-1]) & 0xffffffff
|
| to never put anything that doesn't fit in an unsigned long in the mt
| list.

mt[0] = seed & 0x100000000L
for mti in range(1, n):
mt[mti] = (69069L * mt[mti-1]) % 0x100000000L

--

Mon, 14 Jan 2002 03:00:00 GMT
Bit-twiddling

* Tim Peters
|
| Provided that seed was a long to begin with, this code almost works
| as is.  You just need to append "L" to the literals (for 69069 that
| isn't necessary, it just avoids the repeated expense of runtime
| widening; for 0xffffffff it *is* necessary on a 32-bit machine, else
| 0xffffffff == -1 gets widened to -1L and then the masking doesn't
| accomplish anything (i & -1L == i for all long i)).

Aha! I knew that 0xffffffff didn't work, but I had no idea that the
trick was to define it as a long. Thanks!

| The elements of mt are then all longs, but each one's *value* fits
| in a 32-bit C unsigned long: numerically, it computes the same
| values as would the C code.

Indeed it does. Thanks again!

Based on this advice I took a stab at the rest of the algorithm and
now it actually works! Wheee! So if anyone wants a string of random
numbers with a period of 2**199937-1 and equi-distributed in 623
dimensions, just let me know. :-)

| if-you're-really-after-random-numbers-see-ivan-frohne-ly y'rs  - tim

I guessed that you would recognize the algorithm. :)

I wasn't really after random numbers as much as I was after some easy
diversion. This turned out to not be that easy for someone with a bit
(hah!) less than the necessary maths and C background. :(

Anyway, I see that Frohne uses the code I use above, except that his
69069 is L. But as you say that makes no difference. He doesn't use
the same code for number generation, though.

If I need more diversion I'll try to turn the C code into an extension
module as my first-ever extension module. Should be educational, at
least.

--Lars M.

Mon, 14 Jan 2002 03:00:00 GMT
Bit-twiddling

Quote:
> Based on this advice I took a stab at the rest of the algorithm and
> now it actually works! Wheee! So if anyone wants a string of random
> numbers with a period of 2**199937-1 and equi-distributed in 623
> dimensions, just let me know. :-)

> | if-you're-really-after-random-numbers-see-ivan-frohne-ly y'rs  - tim

I have a new version of the Mersenne Twister just around the corner
that uses the Numeric module if it's available.  This makes it almost
as fast as whrandom.

To get a right shift for ordinary integers that always shifts in high-order
zeros, this
works (x is an ordinary 32-bit signed integer):

x >> 1 & 0x7FFFFFFF  #  Logical right shift 1
x >> 2 & 0x3FFFFFFF  #  Logical right shift 2
.....
x >> 11 & 0x001FFFFF  # Logical right shift 11

etc.

--Ivan Frohne

Mon, 14 Jan 2002 03:00:00 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages