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
low-bit masking) does.

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.

I don't know general ways for wrapping bits, but how about this?

    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  
 
 [ 5 post ] 

 Relevant Pages 

1. Bit Twiddling??

2. Bit twiddling on Parallel port

3. UUDECODE - Bit-twiddling in Arexx

4. SIMD-like bit-twiddling on odd-sized quantities

5. New Mathematical bit-twiddle - stage on of a isPerfectSquare()

6. Crazy bit-twiddle algorithms needed!

7. Bit twiddling functions

8. Bit twiddling functions

9. Byte/Bit Twiddling in Ada

10. Bit Twiddling in IBM (LE) COBOL

11. help - bit twiddling anomoly

12. Bit Twiddling

 

 
Powered by phpBB® Forum Software