That's So Random

[Darren Dirt]

http://en.wikipedia.org/wiki/Xorshift

examples:
http://demesos.blogspot.ca/2011/09/replacing-java-random-generator.html
http://www.javamex.com/tutorials/random_numbers/xorshift.shtml

I don't get how it works.    (and the discovery guy is dead so I can't bend his ear.)

While there are many possible Xorshift generators, the simplest one I found for 64 bit numbers was here.  It?s incredibly short!

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}
This is a full period generator that will generate all bit patterns except for 0.  The period is 2^64-1

#WhatWitchcraftIsThis

[Thorin]

Okay, there's a TV show the kids watch called That's So Random, and when I saw the title I thought that was what this thread was going to discuss.

The actual subject matter of this thread is way more interesting!

Yeah, random number generators are pretty much witchcraft. Especially important is how random they really are. It seems weird to use a cryptography function to come up with a random number for a dice roller, but the cryptography functions are the closest to true randomness.

[Mr. Analog]

What the deuce!

[Tom]

Okay, there's a TV show the kids watch called That's So Random, and when I saw the title I thought that was what this thread was going to discuss.

For some reason I thought of "That's So Raven".

Hmm, two shifts and a rotate. Interesting. Sadly C/C++ don't have a rotate operator

[Lazybones]

The C code example on Wikipedia didn't look too bad.

http://en.m.wikipedia.org/wiki/Xorshift

[Tom]

Yeah, its not bad, but requires you to implement your own rotate with a couple extra shifts and stuff.

Interesting thing, x86 has rotate ops. So if you were inclined, a little bit of inline ASM would get you a fairly short version of that code.

[Darren Dirt]

Yeah, its not bad, but requires you to implement your own rotate with a couple extra shifts and stuff.

Interesting thing, x86 has rotate ops. So if you were inclined, a little bit of inline ASM would get you a fairly short version of that code.

AFAIK that's part of the reason that kind of code is what gets passed around for the super-fast alternative to the standard Java random -- because modern processors do some stuff internally that can be taken advantage via rotate/shift.

[Mr. Analog]

Man, all of a sudden I am reminded of this thread which has come in handy over the years (for me anyway):

http://forums.righteouswrath.com/index.php/topic,5031.msg32110.html#msg32110

[Darren Dirt]

Looks like a Javascript implementation of this = quite similar to C/C++...

https://gist.github.com/ne-sachirou/852327

[Mr. Analog]

Looks like a Javascript implementation of this = quite similar to C/C++...

https://gist.github.com/ne-sachirou/852327

Yep I put it together after Fraga in '07 because the random number generator they were using wasn't.

[Darren Dirt]

Looks like a Javascript implementation of this = quite similar to C/C++...

https://gist.github.com/ne-sachirou/852327

Yep I put it together after Fraga in '07 because the random number generator they were using wasn't.

LOL -- I was referencing to the linked github,  when I mentioned the Javascript implementation.

Spoiler

...
function Xor128(x,   // @param Number:
                y,   // @param Number:
                z,   // @param Number:
                w) { // @param Number:
    this.x = (x ? x >>> 0 : 123456789);
    this.y = (y ? y >>> 0 : 362436069);
    this.z = (z ? z >>> 0 : 521288629);
    this.w = (w ? w >>> 0 : 88675123);
}


function Xor128_init() {
    //return new Xor128(floor(random() * 1000000000000));
    return new Xor128(Date.now());
}
Xor128.init = Xor128_init;


function next() { // @return Number:
    var me = this, x = me.x, w = me.w,
        t = x ^ (x << 11);
   
    me.x = me.y = me.z = w;
    return me.w = (w ^ (w >> 19)) ^ (t ^ (t >> 8 ));
}
Xor128.prototype.next = next;
...

[close]

"LOL" cuz I didn't realize that your "rand.txt" was ALSO Javascript... Only AFTER your reply above did I visit the old-thread link you provided, and I'm having a look at "rand.txt" now. Maybe not a good idea first thing in the morning, especially pre-caffeine.



Oh, and in case it asn't obvious...

Needless to say, XORShift on its own is not cryptographically secure: it is relatively trivial for somebody observing a couple of numbers generated to deduce (at worst by trial and error) the shift values used, and hence predict future numbers.

but still, even in JAVASCRIPT the XORShift is faster than the built-in (not by the insane factor foundin Java though!)
http://jsperf.com/xorshift <-- test it yourself!

Testing in Chrome 27.0.1453.94 on Windows XP

Xorshift
149,416,304
?5.75%
fastest

Math.random
135,973,282
?14.55%
16% slower

[Mr. Analog]

Well I'm glad I read my own posts (someone has to)

[Darren Dirt]

Well I'm glad I read my own posts (someone has to)

I read your posts, bro. 

Sorry for the misunderstanding -- I was saying that my post re. Javascript was in response to something I had found independent of your old thread, and also I had the tab already open in my browser to read the old thread but just had not yet, then when you said what you did I decided to skim it and noticed there is an attached HTML file including Javascript -- but THAT is what I had not examined at all yet (at the time of posting) (and as of now, too -- lunchtime probably).

[Mr. Analog]

NP it's cool stuff man, I love it so much. I guess I was turned on to using hashing to help generate something more random-y

[Darren Dirt]

yeah Math Is Fun.


and btw from the above link ( @ jsperf.com ) did anyone else do a "test" in their web browser?

I'm curious if anyone has Firefox, I wonder if (unlike the other browsers) with FF it is indeed WAY SLOWER with Xorshift than the built-in (which might mean that either FF's Javascript engine sucks for shifts/rotates, or that its built-in random is wicked smaht.)