Was thinking this while watching Casey get random numbers from random.org today.
Powershell:
Powershell:
1 2 3 | 1..4096 | % {
[String]::Format("0x{0:x8}",
[Convert]::ToUInt32((Get-Random -Minimum 1 -Maximum ([UInt32]::MaxValue)))) }
|
Or one could still use a browser, but just write this in the location bar:
1 | javascript:alert(Math.round(Math.random()*4096)); |
I've actually been interested in the topic of random number generators ever since we started talking about doing procedural generation and have been doing a bit of research on the topic. It seems to me as though the class of pseudo-random number generators that are the fastest, and thus most useful for games, are something called XORshift generators, which at their core function through the use of the exclusive-or bitwise operation(not surprisingly).
I wish I could say I understood the mathematics behind it better so as to give a better explanation, but this class of generators depends upon a number of bits of state (in the form of one or more 64 bit integer values in this particular implementation), and as long as all of these individual values are nonzero, the generator should be non-repeating over a maximum interval of 2^(bits of state)-1, I guess depending upon the initial seed values. Take this explanation with a grain of salt, as I'm quite sure I don't really understand it. Anyway, the really cool thing is that working examples of these generators are available in the public domain thanks to a fellow named Sebastiano Vigna, who's website I stumbled upon (thank you Google). I'm still trying to understand his paper, but I thought I might share his website with everyone in light of this topic:
His website:
http://vigna.di.unimi.it/
The XORshift page:
http://xorshift.di.unimi.it/
I don't know if as they are they are suitable for use in a game as-is, but just by virtue of their completion time being on the order of single-digit nanoseconds I think it's something to take a look at and work on moving forward. In addition, as a way to pay forward the kindness he is doing everyone by making these available to the public domain, it wouldn't be the worst thing in the world to try to find an implementation that passes a more extensive battery of tests than the ones currently implemented and make him aware of it if we do.
EDIT:whoops, said not-or instead of exclusive-or
I wish I could say I understood the mathematics behind it better so as to give a better explanation, but this class of generators depends upon a number of bits of state (in the form of one or more 64 bit integer values in this particular implementation), and as long as all of these individual values are nonzero, the generator should be non-repeating over a maximum interval of 2^(bits of state)-1, I guess depending upon the initial seed values. Take this explanation with a grain of salt, as I'm quite sure I don't really understand it. Anyway, the really cool thing is that working examples of these generators are available in the public domain thanks to a fellow named Sebastiano Vigna, who's website I stumbled upon (thank you Google). I'm still trying to understand his paper, but I thought I might share his website with everyone in light of this topic:
His website:
http://vigna.di.unimi.it/
The XORshift page:
http://xorshift.di.unimi.it/
I don't know if as they are they are suitable for use in a game as-is, but just by virtue of their completion time being on the order of single-digit nanoseconds I think it's something to take a look at and work on moving forward. In addition, as a way to pay forward the kindness he is doing everyone by making these available to the public domain, it wouldn't be the worst thing in the world to try to find an implementation that passes a more extensive battery of tests than the ones currently implemented and make him aware of it if we do.
EDIT:whoops, said not-or instead of exclusive-or
Edited by Ruy Calderon
on
Yes, XorShift is pretty good PSRNG. It is very easy to implement it, takes little amount of code, and quality of random numbers is very good.
Another good one is Mersenne Twister. There exists SIMD optimized (SSE2) version that runs faster than vanilla Merssene Twister: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/ It takes more code to implement it, but performance is good. And it's period is much bigger than XorShift, if you really need such large periods.
Another good one is Mersenne Twister. There exists SIMD optimized (SSE2) version that runs faster than vanilla Merssene Twister: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/ It takes more code to implement it, but performance is good. And it's period is much bigger than XorShift, if you really need such large periods.
I've heard of the Marsenne Twister, but was unaware of the details, much less the existence of a SIMD optimized version. Thanks for the link! It seems to me as though the larger periodicity might make it more useful for world-gen as that is less time dependent than an in-game implementation. For larger world-sizes it might even be mandatory. I don't know, I'm still very new to all of this down-n-dirty stuff, I'm certainly excited to start testing all of these things out though!
For more on PRNGs, read this article:
Random Number Generation - Chris Lomont (pdf)
It also contains implementation of WELL512, newer, simpler and generally better algorithm by (among others) the fellow behind mersenne twister.
Random Number Generation - Chris Lomont (pdf)
It also contains implementation of WELL512, newer, simpler and generally better algorithm by (among others) the fellow behind mersenne twister.
The PCG algorithm seems to be very good, "better" in a statistical sense than XorShift and Mersenne. Also better in code size and space requirements. It also has some cool features like multiple streams. Implementation is tiny, a few lines of code. Its only new (paper released in 2014) so it hasn't been scrutinized as much as other generators.
The paper is fairly easy to read (for a math/comp-sci paper), definitely worth having a look, or even giving it some serious time to study it.
The paper is fairly easy to read (for a math/comp-sci paper), definitely worth having a look, or even giving it some serious time to study it.
I was planning to try PCGs on the stream, since previously I usually used LCGs which are crappy but fast, and having read about PCGs recently (thanks to Melissa O'Neill as well!), I felt like they looked like they were similarly in terms of speed but significantly better in terms of quality. But I haven't tried them out yet.
- Casey
- Casey
Thanks for sharing those resources on PRNs, very interesting.
I'm curious if anyone else watched the talk by Melissa O'Neill linked above? She mentions it is possible to write a program that takes no input but produces a different (did she say random?) result each time it is run. The only things I can think of would be relying on uninitialized variables or taking the address of something and counting on address space layout randomization (ASLR).
Does anyone else have any ideas?
I'm curious if anyone else watched the talk by Melissa O'Neill linked above? She mentions it is possible to write a program that takes no input but produces a different (did she say random?) result each time it is run. The only things I can think of would be relying on uninitialized variables or taking the address of something and counting on address space layout randomization (ASLR).
Does anyone else have any ideas?
There's the random number instruction on the CPU, there's timing-based randomization (see how many CPU cycles it takes to come back from sleep, etc.), etc...
- Casey
- Casey
rathersleepy
I'm curious if anyone else watched the talk by Melissa O'Neill linked above? She mentions it is possible to write a program that takes no input but produces a different (did she say random?) result each time it is run.
She specifically said "no input" and that this includes the time, so I'm guessing that explicitly getting the time isn't it.
My guess is that it's a multi-threaded (or multi-processing) program which exploits race conditions or the scheduler in some way. For example, you could spawn 10 threads which generate 1000 numbers using a shared PRNG, then use the 998th number returned by thread #3.