Ways to do 32-bit arithmetics?
Hi: I am porting some benchmarks to Pharo, which rely on a deterministic random number generator that uses 32 bit values. In order to have properly comparable results across platforms, it needs to generated the same sequence of numbers. So, I am looking for efficient ways to implement it, any ideas? I am a little at a loss, with SmallInts and Long Ints, how to get the proper 32-bit values, and how to apply the correct shifts, especially the right shift can be problematic. Code examples below. Thanks Stefan In Java it looks like this: private static int seed; // Robert Jenkins' 32 bit integer hash function. public static int random() { seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff; seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff; seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff; seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff; seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff; seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff; return seed; } In SOM Smalltalk, it looks like this: JenkinsRandom = ( ---- | seed | seed: val = ( seed := val ) "Robert Jenkins' 32 bit integer hash function." random = ( seed := ((seed + 2127912214 "0x7ed55d16") + (seed as32BitUnsignedValue << 12) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3345072700 "0xc761c23c") bitXor: (seed as32BitUnsignedValue >>> 19)) as32BitSignedValue. seed := ((seed + 374761393 "0x165667B1") + (seed as32BitUnsignedValue << 5) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 3550635116 "0xd3a2646c") bitXor: (seed as32BitUnsignedValue << 9) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 4251993797 "0xfd7046c5") + (seed as32BitUnsignedValue << 3) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3042594569 "0xb55a4f09") bitXor: (seed as32BitUnsignedValue >>> 16)) as32BitSignedValue. ^ seed ) ) -- Stefan Marr INRIA Lille - Nord Europe http://stefan-marr.de/research/
There is ThirtyTwoBitRegister â I represent a 32-bit register. An instance of me can hold any non-negative integer in the range [0..(2^32 - 1)]. Operations are performed on my contents in place, like a hardware register, and results are always modulo 2^32. This class is primarily meant for use by the SecureHashAlgorithm class. "
On 03 Apr 2015, at 16:15, Stefan Marr <smalltalk@stefan-marr.de> wrote:
Hi:
I am porting some benchmarks to Pharo, which rely on a deterministic random number generator that uses 32 bit values.
In order to have properly comparable results across platforms, it needs to generated the same sequence of numbers.
So, I am looking for efficient ways to implement it, any ideas? I am a little at a loss, with SmallInts and Long Ints, how to get the proper 32-bit values, and how to apply the correct shifts, especially the right shift can be problematic.
Code examples below.
Thanks Stefan
In Java it looks like this:
private static int seed;
// Robert Jenkins' 32 bit integer hash function. public static int random() { seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff; seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff; seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff; seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff; seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff; seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff; return seed; }
In SOM Smalltalk, it looks like this:
JenkinsRandom = ( ---- | seed |
seed: val = ( seed := val )
"Robert Jenkins' 32 bit integer hash function." random = ( seed := ((seed + 2127912214 "0x7ed55d16") + (seed as32BitUnsignedValue << 12) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3345072700 "0xc761c23c") bitXor: (seed as32BitUnsignedValue >>> 19)) as32BitSignedValue. seed := ((seed + 374761393 "0x165667B1") + (seed as32BitUnsignedValue << 5) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 3550635116 "0xd3a2646c") bitXor: (seed as32BitUnsignedValue << 9) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 4251993797 "0xfd7046c5") + (seed as32BitUnsignedValue << 3) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3042594569 "0xb55a4f09") bitXor: (seed as32BitUnsignedValue >>> 16)) as32BitSignedValue. ^ seed ) )
-- Stefan Marr INRIA Lille - Nord Europe http://stefan-marr.de/research/
Hi Stefan, if seed is Andes with 16rffffffff when it is initialized then the Java code can be used to generate the next value and the sign conversion only applied once to yield the next value. That would eliminate lots of conversions and make the code readable, right? Eliot (phone) On Apr 3, 2015, at 7:15 AM, Stefan Marr <smalltalk@stefan-marr.de> wrote:
Hi:
I am porting some benchmarks to Pharo, which rely on a deterministic random number generator that uses 32 bit values.
In order to have properly comparable results across platforms, it needs to generated the same sequence of numbers.
So, I am looking for efficient ways to implement it, any ideas? I am a little at a loss, with SmallInts and Long Ints, how to get the proper 32-bit values, and how to apply the correct shifts, especially the right shift can be problematic.
Code examples below.
Thanks Stefan
In Java it looks like this:
private static int seed;
// Robert Jenkins' 32 bit integer hash function. public static int random() { seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff; seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff; seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff; seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff; seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff; seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff; return seed; }
In SOM Smalltalk, it looks like this:
JenkinsRandom = ( ---- | seed |
seed: val = ( seed := val )
"Robert Jenkins' 32 bit integer hash function." random = ( seed := ((seed + 2127912214 "0x7ed55d16") + (seed as32BitUnsignedValue << 12) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3345072700 "0xc761c23c") bitXor: (seed as32BitUnsignedValue >>> 19)) as32BitSignedValue. seed := ((seed + 374761393 "0x165667B1") + (seed as32BitUnsignedValue << 5) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 3550635116 "0xd3a2646c") bitXor: (seed as32BitUnsignedValue << 9) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 4251993797 "0xfd7046c5") + (seed as32BitUnsignedValue << 3) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3042594569 "0xb55a4f09") bitXor: (seed as32BitUnsignedValue >>> 16)) as32BitSignedValue. ^ seed ) )
-- Stefan Marr INRIA Lille - Nord Europe http://stefan-marr.de/research/
Hi Eliot:
On 03 Apr 2015, at 16:47, Eliot Miranda <eliot.miranda@gmail.com> wrote:
if seed is Andes with 16rffffffff when it is initialized then the Java code can be used to generate the next value and the sign conversion only applied once to yield the next value. That would eliminate lots of conversions and make the code readable, right?
Sorry, I donât understand you. In the Java code the `0xffffffff` is redundant/superfluous. Itâs there because I ported the code from JavaScript. The important part is that Java has signed 32bit integers. So, it works as expected out of the box. The SOM version shows the explicit operations you need if you donât have any knowledge about the underlying integer representation. In most SOM implementations, integers happen to be represented as 64bit values, that overflow into some form of big/large integer representations. The sign-related operations are necessary to get the correct shift and overflow semantics. I guess I could implement it easily on a 64-bit Spur image, but I havenât looked into that yet. Marcusâ comment looks also useful, but it is going to be very slow⦠Best regards Stefan -- Stefan Marr INRIA Lille - Nord Europe http://stefan-marr.de/research/
Hi Stefan, the point is that the code uses only 32 bits. The java code ands by 16rffffffff on each update to seed, and even if that's not necessary because seed is declared as int, it does show that we can discard bits above 3/ after each update. Therefore any use of seed in a left shift does not need alteration because high bits will be lost. The only case is in a right shift, where the sign bit will be propagated. So (assuming ^ & defined as bitXor: and bitAnd: ; I'm on my phone, and that >>> is arithmetic shift right) I believe that this will work: seed := ((seed + 16r7ed55d16) + (seed << 12)) & 16rffffffff. seed := ((seed ^ 16rc761c23c) ^ (seed as32BitSignedValue >>> 19)) & 16rffffffff. seed := ((seed + 16r165667b1) + (seed << 5)) & 16rffffffff. seed := ((seed + 16rd3a2646c) ^ (seed << 9)) & 16rffffffff. seed := ((seed + 16rfd7046c5) + (seed << 3)) & 16rffffffff. seed := ((seed ^ 16rb55a4f09) ^ (seed as32BitSignedValue >>> 16)) & 16rffffffff. ^ seed as32BitSignedValue Eliot (phone) On Apr 3, 2015, at 8:04 AM, Stefan Marr <smalltalk@stefan-marr.de> wrote:
Hi Eliot:
On 03 Apr 2015, at 16:47, Eliot Miranda <eliot.miranda@gmail.com> wrote:
if seed is Andes with 16rffffffff when it is initialized then the Java code can be used to generate the next value and the sign conversion only applied once to yield the next value. That would eliminate lots of conversions and make the code readable, right?
Sorry, I donât understand you.
In the Java code the `0xffffffff` is redundant/superfluous. Itâs there because I ported the code from JavaScript. The important part is that Java has signed 32bit integers. So, it works as expected out of the box.
The SOM version shows the explicit operations you need if you donât have any knowledge about the underlying integer representation. In most SOM implementations, integers happen to be represented as 64bit values, that overflow into some form of big/large integer representations.
The sign-related operations are necessary to get the correct shift and overflow semantics.
I guess I could implement it easily on a 64-bit Spur image, but I havenât looked into that yet.
Marcusâ comment looks also useful, but it is going to be very slowâ¦
Best regards Stefan
-- Stefan Marr INRIA Lille - Nord Europe http://stefan-marr.de/research/
Hi:
On 03 Apr 2015, at 17:44, Eliot Miranda <eliot.miranda@gmail.com> wrote:
seed := ((seed + 16r7ed55d16) + (seed << 12)) & 16rffffffff. seed := ((seed ^ 16rc761c23c) ^ (seed as32BitSignedValue >>> 19)) & 16rffffffff. seed := ((seed + 16r165667b1) + (seed << 5)) & 16rffffffff. seed := ((seed + 16rd3a2646c) ^ (seed << 9)) & 16rffffffff. seed := ((seed + 16rfd7046c5) + (seed << 3)) & 16rffffffff. seed := ((seed ^ 16rb55a4f09) ^ (seed as32BitSignedValue >>> 16)) & 16rffffffff. ^ seed as32BitSignedValue
Ok, my implementation looks now like this: random "Robert Jenkins' 32 bit integer hash function." seed := ((seed + 16r7ed55d16) + (seed << 12)). seed := ((seed bitXor: 16rc761c23c) bitXor: ((seed bitAnd: 16rffffffff) >> 19)). seed := ((seed + 16r165667B1) + (seed << 5)). seed := ((seed + 16rd3a2646c) bitXor: (seed << 9)). seed := ((seed + 16rfd7046c5) + (seed << 3)). seed := self as32BitSigned: ((seed bitXor: 16rb55a4f09) bitXor: ((seed bitAnd: 16rffffffff) >> 16)). ^ seed as32BitSigned: val | r | r := val bitAnd: 16rffffffff. (r bitAnd: 16r80000000) = 0 ifTrue: [ ^ r ]. ^ (16r100000000 - r) * -1 The #as32BitSigned: looks a little naive, but didnât have any better idea. And Andres, the random number generator is a given, I canât just change it. Best regards Stefan -- Stefan Marr INRIA Lille - Nord Europe http://stefan-marr.de/research/
On Mon, Apr 6, 2015 at 3:01 AM, Stefan Marr <smalltalk@stefan-marr.de> wrote:
Hi:
On 03 Apr 2015, at 17:44, Eliot Miranda <eliot.miranda@gmail.com> wrote:
seed := ((seed + 16r7ed55d16) + (seed << 12)) & 16rffffffff. seed := ((seed ^ 16rc761c23c) ^ (seed as32BitSignedValue >>> 19)) & 16rffffffff. seed := ((seed + 16r165667b1) + (seed << 5)) & 16rffffffff. seed := ((seed + 16rd3a2646c) ^ (seed << 9)) & 16rffffffff. seed := ((seed + 16rfd7046c5) + (seed << 3)) & 16rffffffff. seed := ((seed ^ 16rb55a4f09) ^ (seed as32BitSignedValue >>> 16)) & 16rffffffff. ^ seed as32BitSignedValue
Ok, my implementation looks now like this:
random "Robert Jenkins' 32 bit integer hash function." seed := ((seed + 16r7ed55d16) + (seed << 12)). seed := ((seed bitXor: 16rc761c23c) bitXor: ((seed bitAnd: 16rffffffff) >> 19)). seed := ((seed + 16r165667B1) + (seed << 5)). seed := ((seed + 16rd3a2646c) bitXor: (seed << 9)). seed := ((seed + 16rfd7046c5) + (seed << 3)). seed := self as32BitSigned: ((seed bitXor: 16rb55a4f09) bitXor: ((seed bitAnd: 16rffffffff) >> 16)). ^ seed
as32BitSigned: val | r | r := val bitAnd: 16rffffffff. (r bitAnd: 16r80000000) = 0 ifTrue: [ ^ r ]. ^ (16r100000000 - r) * -1
The #as32BitSigned: looks a little naive, but didnât have any better idea.
And Andres, the random number generator is a given, I canât just change it.
On Sat, Apr 4, 2015 at 2:49 PM, Andres Valloud < avalloud@smalltalk.comcastbiz.net> wrote:
Lagged Fibonacci RNGs are much more Smalltalk friendly, I'd use those.
Or maybe you can substitute a Lagged Fibonacci RNGs back into the Java (If a more favourable comparison ends up being needed). cheers -ben
On Fri, 3 Apr 2015, Stefan Marr wrote:
Hi Eliot:
On 03 Apr 2015, at 16:47, Eliot Miranda <eliot.miranda@gmail.com> wrote:
if seed is Andes with 16rffffffff when it is initialized then the Java code can be used to generate the next value and the sign conversion only applied once to yield the next value. That would eliminate lots of conversions and make the code readable, right?
Sorry, I donât understand you.
In the Java code the `0xffffffff` is redundant/superfluous. Itâs there because I ported the code from JavaScript. The important part is that Java has signed 32bit integers. So, it works as expected out of the box.
The SOM version shows the explicit operations you need if you donât have any knowledge about the underlying integer representation. In most SOM implementations, integers happen to be represented as 64bit values, that overflow into some form of big/large integer representations.
The sign-related operations are necessary to get the correct shift and overflow semantics.
I guess I could implement it easily on a 64-bit Spur image, but I havenât looked into that yet.
Marcusâ comment looks also useful, but it is going to be very slowâ¦
It's still the fastest option within a 32-bit image (way faster than LargeInteger operations). Of course you could just use Nativeboost if it's for Pharo. Levente
Best regards Stefan
-- Stefan Marr INRIA Lille - Nord Europe http://stefan-marr.de/research/
Ah, you also need the sign conversion applied to the uses of seed in right shifts, but that's still a simplification. Eliot (phone) On Apr 3, 2015, at 7:15 AM, Stefan Marr <smalltalk@stefan-marr.de> wrote:
Hi:
I am porting some benchmarks to Pharo, which rely on a deterministic random number generator that uses 32 bit values.
In order to have properly comparable results across platforms, it needs to generated the same sequence of numbers.
So, I am looking for efficient ways to implement it, any ideas? I am a little at a loss, with SmallInts and Long Ints, how to get the proper 32-bit values, and how to apply the correct shifts, especially the right shift can be problematic.
Code examples below.
Thanks Stefan
In Java it looks like this:
private static int seed;
// Robert Jenkins' 32 bit integer hash function. public static int random() { seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff; seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff; seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff; seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff; seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff; seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff; return seed; }
In SOM Smalltalk, it looks like this:
JenkinsRandom = ( ---- | seed |
seed: val = ( seed := val )
"Robert Jenkins' 32 bit integer hash function." random = ( seed := ((seed + 2127912214 "0x7ed55d16") + (seed as32BitUnsignedValue << 12) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3345072700 "0xc761c23c") bitXor: (seed as32BitUnsignedValue >>> 19)) as32BitSignedValue. seed := ((seed + 374761393 "0x165667B1") + (seed as32BitUnsignedValue << 5) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 3550635116 "0xd3a2646c") bitXor: (seed as32BitUnsignedValue << 9) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 4251993797 "0xfd7046c5") + (seed as32BitUnsignedValue << 3) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3042594569 "0xb55a4f09") bitXor: (seed as32BitUnsignedValue >>> 16)) as32BitSignedValue. ^ seed ) )
-- Stefan Marr INRIA Lille - Nord Europe http://stefan-marr.de/research/
Hang on. It looks like their random number generator is based on a Jenkins' 32 bit hash function* such that the operation is: seed := some initial value. and then Random>>next seed := seed jenkinsHash. ^seed But who said Jenkins' hash function is a good RNG when used that way? I'd be interested to know if there was a proper citation, when I wrote the hash book I didn't see any such thing. Did I miss the reference? Am I reading the code right? Lagged Fibonacci RNGs are much more Smalltalk friendly, I'd use those. Andres. *: it would have been nicer for the code to say *which* Jenkins hash function, I suspect lookup3 but I didn't verify so... On 4/3/15 7:15 , Stefan Marr wrote:
Hi:
I am porting some benchmarks to Pharo, which rely on a deterministic random number generator that uses 32 bit values.
In order to have properly comparable results across platforms, it needs to generated the same sequence of numbers.
So, I am looking for efficient ways to implement it, any ideas? I am a little at a loss, with SmallInts and Long Ints, how to get the proper 32-bit values, and how to apply the correct shifts, especially the right shift can be problematic.
Code examples below.
Thanks Stefan
In Java it looks like this:
private static int seed;
// Robert Jenkins' 32 bit integer hash function. public static int random() { seed = ((seed + 0x7ed55d16) + (seed << 12)) & 0xffffffff; seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff; seed = ((seed + 0x165667b1) + (seed << 5)) & 0xffffffff; seed = ((seed + 0xd3a2646c) ^ (seed << 9)) & 0xffffffff; seed = ((seed + 0xfd7046c5) + (seed << 3)) & 0xffffffff; seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff; return seed; }
In SOM Smalltalk, it looks like this:
JenkinsRandom = ( ---- | seed |
seed: val = ( seed := val )
"Robert Jenkins' 32 bit integer hash function." random = ( seed := ((seed + 2127912214 "0x7ed55d16") + (seed as32BitUnsignedValue << 12) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3345072700 "0xc761c23c") bitXor: (seed as32BitUnsignedValue >>> 19)) as32BitSignedValue. seed := ((seed + 374761393 "0x165667B1") + (seed as32BitUnsignedValue << 5) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 3550635116 "0xd3a2646c") bitXor: (seed as32BitUnsignedValue << 9) as32BitSignedValue) as32BitSignedValue. seed := ((seed + 4251993797 "0xfd7046c5") + (seed as32BitUnsignedValue << 3) as32BitSignedValue) as32BitSignedValue. seed := ((seed bitXor: 3042594569 "0xb55a4f09") bitXor: (seed as32BitUnsignedValue >>> 16)) as32BitSignedValue. ^ seed ) )
participants (6)
-
Andres Valloud -
Ben Coman -
Eliot Miranda -
Levente Uzonyi -
Marcus Denker -
Stefan Marr