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. :think: (and the discovery guy is dead (http://en.wikipedia.org/wiki/George_Marsaglia) so I can't bend
his ear.)
Quote from: http://dmurphy747.wordpress.com/2011/03/23/xorshift-vs-random-performance-in-java/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
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.
What the deuce!
Quote from: Thorin on May 26, 2013, 11:50:20 AM
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 :(
The C code example on Wikipedia didn't look too bad.
http://en.m.wikipedia.org/wiki/Xorshift
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.
Quote from: Tom on May 26, 2013, 09:06:40 PM
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.
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
Looks like a Javascript implementation of this = quite similar to C/C++ (http://en.wikipedia.org/wiki/Xorshift#Example_implementation)...
https://gist.github.com/ne-sachirou/852327
Quote from: Darren Dirt on May 27, 2013, 09:14:34 AM
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.
Quote from: Mr. Analog on May 27, 2013, 09:15:46 AM
Quote from: Darren Dirt on May 27, 2013, 09:14:34 AM
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;
...
"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...
Quote from: http://www.javamex.com/tutorials/random_numbers/xorshift.shtml
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!
Quote
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
::)
Well I'm glad I read my own posts (someone has to)
Quote from: Mr. Analog on May 27, 2013, 09:25:21 AM
::)
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).
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
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.)
I tried it with Chrome but I didn't even think to try it with others!
Interesting!
Also interesting: the "jsperf.com" site itself!
It's basically like a Wiki for testing JS code (esp. comparing Method1 vs Method2) and has a wizard-y interface so if your code depends on jQuery or whatever you have a place to include that or make reference to that requirement -- thus allowing for really easy re-use/cloning of your tests!
Yep, you can actually download and play with the site yourself: https://github.com/mathiasbynens/jsperf.com
And contribute to the scripts.
Pretty cool find if you ask me
Quote from: Darren Dirt on May 27, 2013, 01:29:43 PM
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.)
Not sure, I use FF full time and between releases Chrome and FF keep shifting the javascript performance crown.
I find it interesting when browsers excel at different operations, it really brings the dev thinking out front.
Like you could have really good loop processing in one at a cost to memory vs really good stack management but high CPU... the end result is usually close but totally different ways of solving things.
Quote from: Darren Dirt on May 27, 2013, 01:35:45 PM
Also interesting: the "jsperf.com" site itself!
It's basically like a Wiki for testing JS code (esp. comparing Method1 vs Method2) and has a wizard-y interface
lotsa people are using it for similar things, esp. "which method of grabbing an HTML/DOM element is fastest?
http://jsperf.com/popular#all-time
...also, lol, the devs behind jsperf.com recognize how lazy some developers might be (http://jsperf.com/faq#autorun) 8)
and speaking of lazy...
Quote from: http://www.phpied.com/jsperf-bookmarklet/
These days we're so happy and spoiled with all these amazing tools around us. And yet, when you create a JSPerf test, you have to open all these browsers and run the test everywhere. Even IE. And, when on Mac, IE is usually not readily available. Plus it comes in a bunch versions - from almost-but-not-quite-forgotten IE6, all the way to IE10 The Greatest - and they have different, sometimes contradicting, performance characterics.
To the rescue: The bookmarklet WPT! WebPagetest has: a/ ability to run in a bunch of browsers and b/ an API.
Here's an interesting one: http://jsperf.com/caching-array-length/4#run
It's running through a for loop. In both Chrome 27 and IE 9, the first option (creating length variable inside the for statement and comparing against it instead of the array's length) is the fastest. But what's really interesting is Chrome 27 can do this over 4mil times per second, while IE 9 can do this a little over 0.5mil per second. Chrome is 8 times faster than IE at looping? WOW!
edit: just tried in Firefox 15, it could do 7mil per second!
Firefox 15? If you are going to compare to chrome you should probably get your self into the current release cycle..
I ran the tests on my machine with both browsers and ya the results are interesing, but as a whole FF was king.
http://jsperf.com/xorshift
Chrome 27
Xor 135,788,543 ?6.16% fastest
Math.rand 120,637,416 ?14.02% 17% slower
FF 21
Xor 5,537,393 ?2.54%99% slower (A LOT slower than Chrome)
Math.rand 602,939,076 ?38.85%fastest (crazy fast compared to Chrome)
http://jsperf.com/caching-array-length/4
Chrome
29,093,431 ?12.48% fastest
22,983,414 ?24.46% fastest
20,272,404 ?15.13% 32% slower
24,187,360 ?21.35% fastest
9,902,878 ?15.43% 67% slower
4,801,304 ?4.32% 82% slower
FF (all values best Chrome)
35,768,070 ?2.11%fastest
33,856,985 ?1.24%5% slower
27,761,298 ?5.24%25% slower
33,614,277 ?5.13%fastest
24,514,926 ?1.48%31% slower
11,179,207 ?0.71%68% slower
FF is 2.5x faster at while loops than Chrome.