A 64bit XorShift is now used to generate random numbers in DWScript, and there is a now a separate random number generator per-execution, which is auto-randomized when an execution is created.
Previously, the RTL random generator was used, this was “okay” when you had only one script using random numbers at a time, but multiple scripts running at the same time would interfere (Randomize calls would affect each others f.i.), and Random isn’t really thread-safe.
Performance fo XorShift is roughly comparable to the Delphi RTL’s linear congruential generator, but with much better statistical random properties and a very long period, without the overhead of a Mersenne Twister. For those interested in the mathematical details, see “XorShift RNGs” paper by G. Marsagalia.
As an illustration of the improved random properties, consider filling a bitmap with “random” RGB colors for each pixel:
var x, y : Integer;
for x := 0 to bmp.Width-1 do
for y := 0 to bmp.Height-1 do
bmp.Pixel[x, y] := RandomInt($1000000);
Using the Delphi built-in Random, you’ll get something like the image below (generated at 512×512, then halved and downgraded to 4bpp for web consumption)
Delphi RTL Random
Oooh… the horizontal scratch lines! Not so random after all… I don’t know if the Delphi LCG is as biased as RANDU, but visibly, it is probably not something you want to rely upon too much.
And now, the same but with the XorShift implementation now used in DWS:
DWScript XorShift Random
The XorShift implementation is very simple, fast, and doesn’t require much memory: a single 64bit value is enough to get good random, use two if you want longer periods that won’t have a chance to loop before the universe ends.
Last but not least, 64bit XorShift may be fast in 32bit binaries, but it practically walks on water in 64bit binaries 😉
It is all pseduo random, and you have simply changed the appearance of your pseduo random, not made it in any way better.
Tho we find it hard to believe, but in a truely random scenario, it is actually possible to hit 18 red lights in a row. I know, I did it the other night. Streaks are possible and common – eliminating them actually removes randomness more than it introduces it.
Of course, you could hunt out the windows cryptographically secure pseduorandom number generator available since XP win32 an incorporate it to increase your entropy. ( http://en.wikipedia.org/wiki/CSPRNG )
It has statistically better properties than the LCG (check the papers on the subject).
You can hit 18 zeroes in a row in a series of XorShifted-Random(2) too.
What you may be referring to is that you can’t hit 18 times the same 64bit value with a 64bit xorshift… but you can with a 256 bit ones IIRC. The probability of that is however in the pseudo-random and true-random world monstrously lower than that of hitting 18 red lights in a row (whose worst case is 1/262000, and likely much more probable in practice since the red lights are neither equiprobable nor truly decoupled).
It’s however just not comparable in terms of computational complexity, and was still flawed before SP3… and may still be (just the issue hasn’t been made public yet). So after all, I’m with Marsaglia: as long as the statistical properties are good and it’s fast, it’s good.
I’ve tried this and it always gives me a horizontal line(D7, Win xp sp3 – had this vm running)… unless you call Randomize in both loops, you will(at least I did) always get a horizontal line, somewhere above half of the screen, even so(by calling randomize in both loops) I still managed to get that in 1 out of 5 times, which raises one of the past experiences when I had to generate large amounts of “random” data, and I was wondering why the randomness is not so random… now I friggin’ know!
Pretty disappointed…
You call Randomize every time before getting random value? It is a mistake. Randomize sets the seed (starting point) of RNG, and setting (probably) the same seed results in getting the same “random” value.
@Igor
I know randomize should not be called more than once, the reason I did that, was just for testing[!] and it was the most “random” of all, in my tests at least, feel free to argue.
@Eric
Statistically better? So your random number generator fits a particular pattern better? Uh, you might want to check your definition of random.
And actually, in a true random number generator, it should be possible to get the same value for long runs – true randomness not just allows it, but demands it happen eventually.
As for the quality of the csprng, that is why you try not to rely on a SINGLE source of entropy – but rather as many as possible melded together.
Well, yes, and FWIW, all known “true random generators” are only qualified so after study of their statistical properties, so I’m not sure what you’re trying to say.
There have already been multiple natural sources of “true” random in history that were later uncovered through study of their statistical properties to have one bias or an other, be it spectroscopic or sensitivity to external environment. So any “true” random source is only “true” as long as its known statistical properties are saying so.
God didn’t take the time to neatly label things with “Random” when they were, and “not Random” when they were not, so it always comes down to being a qualifier after mathematical/statistical study.
That’s only true to the extent your sources of entropy are truly independent, and don’t exhibit resonance or coupling properties. The history of cryptography is full of “more is better” assumptions that were later proven incorrect.
Anyway, that’s irrelevant to a built-in Random(), whose purpose is not cryptographic (as cryptography involves more than entropy considerations).
This reminded me an implementation (in asm) by G. Adam Stanislav, back in 1998, based on the book The Art of Electronics, Second Edition, by Paul Horowitz and Winfield Hill. On that time, I’ve tested the Delphi random and VS C++ random functions against this one. I was really surprised that the illustration generated based on the “common” library’s was not random at all, producing much more lines than this ones used by you. But I’ve never tested them against chi-squared test (http://en.wikipedia.org/wiki/Chi_square_test). And that was before Xorshift was discovered. Just wondering did you have tested it?
If anyone are interested in see the asm file with comments, look for Whiz Kid Technomagic Random Number Generator. I find it here in a relevant forum topic. http://www.asmcommunity.net/board/index.php?topic=633.0
@EMB
For a criticism of XorShift vs Chi-squared (and other tests), you can have a look at this paper: http://www.iro.umontreal.ca/~panneton/Xorshift.html
The paper glosses on some aspects though (such as performance or usage purpose), but it’s quite interesting. In short, it’s not the Holy Grail, and it has weaknesses like every PRNG, but it’s light in amount of code, memory & setup, still exhibits much better properties than the RTL’s LCG, which makes it valuable for a default random generator.
For special purpose generators (cryptography, etc.), I doubt anyone will (should) be relying on anything but on dedicated RNG code anyway, for which they control the algorithms, the keys, etc.
Thanks for the link. I’m starting to read it now.
@C Johnson
Relevant http://dilbert.com/strips/comic/2001-10-25/