Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (570) Games in Android Showcase (154) games submitted by our members Games in WIP (618) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Pseudo random number generators  (Read 19129 times) 0 Members and 1 Guest are viewing this topic.
Wiki Duke

?

 « Posted 2012-11-15 16:40:51 »

Note: you are watching revision 4 of this wiki entry. ( view plain diff )
VERY ROUGH WORK IN PROGRESS..NO REAL USEFUL INFORMATION AS OF YET.

### Overview

The purpose of this page is to give an rough overview of how pseudo random number generators (PRNG) work and a rough idea of how to choose ones which are adequate for a game runtime.

### Rules of thumb

• Never use the same instance of a generator in more than one thread.
• Never create static utility methods which call a generator unless single threaded (same as previous).
• XXX

XXX Use different generators if you need a more expensive one for a sub-set of tasks...oh, and don't really worry about any of this stuff if you just don't generate many random numbers.

Everything below this point can (and should) be ignored unless you are generating a large numbers of random numbers per frame OR you tempted to use OR are using a "good" random number generator especially one with a period greater than 264.  Again this page is only dealing with PRNGs for game runtimes where "real" money is not directly involved.

### Introduction

The vast majority of PRNGs all work in the same way.  They take some state-data in the form of a sequence of bits and perform computations which mix the bits.  Notice that hashing and random number generation are very similar. A given generator will have a period which is the number of unique values the state will assume before wrapping around and repeating itself.  Yeah, that was clear.  OK, let's pretend like we're using a 2-bit integer for our state data, so our 2-bit integer can have values of: {0,1,2,3}.  For our random number generator we want to produce some permutation (MathWorld, Wikipedia) of that set which appears random.  The number of permutations of a set with n elements is Factorial[n], so we have 24 choices for our 2-bit integer.  Limiting the set to those that start with '0' (all the remaining are rotations), we have: {0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}.

Now obviously none of the above permutation choices look very random but this is exactly how random number generators work. The problem here is that there just aren't enough unique values that any of the permutations appear random.  Luckily factorials explode and if we were talking about only 8-bits then there would be approximately 8.6x10506 choices and 16-bits is ~5.2x10287193.  Other than some very narrow special cases (like in GLSL, when attempting to avoid using integers) there's no reason to use generators with less than 32-bits.

An implication of this is that the period can be at most 2n, where 'n' is the number of bits.  On this page we will only consider "full period generators" which will have a period of either 2n or 2n-1.  The minus one comes into play for generators for which zero is an invalid state.

This does not imply that PRNGs with longer periods are superior in quality than those that are shorter.

### Period

As mentioned above the period of a PRNG is the length of the sequence that it generates.  Once the period is exhausted, the sequence wraps-around and starts to repeat itself.

For scientific usage long periods are important.  The reason for this is that statistically they will begin show defects if in "single computation" more than sqrt(T) random numbers are used, where T is the period.  Note that the sqrt(T) = T1/2.  Even more important is because one can break a problem across multiple CPUs/servers/whatever to attack a single problem and the longer the period, the lower the probability that the individual computation units will be using overlapping parts of the sequence.

Note the "single computation" part.  There's the mistaken notion in games that one needs a period long enough that it never repeats during gameplay.  Not at all, it simply should be long enough that every single computation has more than enough values to complete.

So what about the period?  Do we need to think in terms of T or sqrt(T)?  The question is more or less moot.  As noted above there's no reason to use a generator with a period shorter than ~232, so you should feel safe if any single problem needs no more than 216 or 65536 random numbers, which seems highly unlikely.  At the opposite end of the spectrum (SEE: url=http://www.java-gaming.org/topics/orders-of-magnitude/27917/view.html]orders of magnitude[/url]) it would take the Cray Titan more than 17 minutes to generate 264 random numbers and an infinite amount of time to generate 2128.  Sticking the sqrt(T) rule of thumb this means you never need a generator with a period greater than 2128.

### Dimensions

Humm...any ideas here kids, other than don't worry about dimensions.  Just don't use a LCG for more than 2.

### Quality

PRNGs do not attempt to create sequences which appear random. Instead they are attempting to simulate statistical randomness.

For our purposes the main usefulness of having a generator which passes the majority to all of XXXX
XX note uniform distribution
XX Write something somehow convincing about how quality a la. diehard and various crushes shouldn't matter.

### Old Skool

Permutation Polynomials
SEE: GLSL Tricks

Weyl Generators
--STUB AGAIN -- stuck in place since I mentioned them in the GLSL tricks page

This family is based on the equidistribution theorem (properties of irrational numbers). Quality varies widely depending on formulation and precision.  Like permutation polynomials they can be computed purely in floating point and are currently useful on the GPU.

The simplest version looks like:
un = na mod 1 = (un-1+a) mod 1

where:
'a' is a fixed irrational number mod 1.
'n' is the number in the sequence (0,1,2...)

Common variants include nested:
un = n(na mod 1) mod 1

and shuffled nested (where 'm' is a fixed large integer):
vn = m(n(na mod 1) mod 1)+1/2
un = (vn(vn a mod 1)) mod 1

 1  2  3  4  5  6  7  8 `  vec3 weyli(vec3 s, vec3 a)  { return fract(s+a); }            // simple incremental  vec3 weyl(vec3 n, vec3 a)   { return fract(n*a); }            // simple explict  vec3 weyln(vec3 n, vec3 a)  { return fract(n*fract(n*a)); }   // nested  vec3 weylns(vec3 n, vec3 a)                                   // shuffled nested  {    n = m*fract(n*fract(n*a))+0.5;    return fract(n*fract(n*a));  }`

XXXX

Linear Congruent Generators
Linear congruent generators

Mention some mod-power-of-two LCGs here.  Non-power-of-two just ain't worthwhile.  Nor are IHMO sub-cycle generators.

### New kids on the block

Mention some cheap LSFRs here

### Summary

Reference
Blah, blah

Junior Devvie

 « Reply #1 - Posted 2012-11-22 01:18:37 »

How is this table for a replacement to the current table under the period section. Powers of numbers are incomprehensible beyond a certain point. The square root and cubed root doesn't much sense. I don't know what relation the root of the period has to the period. Mathematically you're just showing n, 2^n, 2^(n/2), and 2^(n/3). Rather than show the decimal values, how about showing how long it would take for the prng to repeat itself? This chart shows the period of the rng (rows), how frequently a random number is pulled from the rng, and how long that time would take. I think it's much more applicable to game programmers and is easier to comprehend in terms of scale.

 1 per second 100/s 10000/s 1000000/s 2^8 4m 16s 2s 0s 0s 2^16 18h 12m 16s 10m 55s 6s ~0s 2^32 1c 36y 70d 6h 28m 16s 1y 132d 2h 27m 52s 4d 23h 18m 16s 1h 11m 34s 2^64 5849424173c 55y 26d 7h 16s 58494241c 73y 201d 18m 36s 584942c 41y 268d 11h 2m 35s 5849c 42y 152d 8h 1m 49s

I can think of a scenario that might be a problem: The programmer chooses a random seed, the game runs for an amount of time and goes through a fraction of the rng's period, the game runs again later with another random seed and halfway through hits a state it already had in the previous game. This probably isn't a problem if user interaction can change the order/interpretation of bits taken from the rng, but maybe it's a minor concern if multiplied over a large number of players in an online game.

Depending on how much real-world randomness (player interaction?) influences the game, the probability of the player experiencing deja vu changes. I doubt it's a serious problem for most games though, maybe for a screensaver, but not a game. The butterfly effect could lead to different outcomes whether the player kills a familiar group of monsters in a different order or if he hits the space bar one millisecond later than he previously did, but maybe in a turn based rpg with a very small period rng someone might recognize a pattern and use it to game the AI.
Roquen
 « Reply #2 - Posted 2012-11-22 09:48:30 »

This is exactly "counter" to what I'm attempting to say.  Which is, you don't (or rather shouldn't) directly care about how long it takes before the RNG starts to repeating itself.  If you're running through the period multiple times in a single frame...that doesn't directly matter.  Indirectly it might mean you're using an RNG with too short of a period...by which I mean "is too expensive per result", as you shouldn't be using anything with T shorter than 2^32 (again CPU only) of which there are fast good options.  OR it means you're generating tons of random numbers (sticking to 2^32) and generating more than 4x10^9 random numbers per game frame seems a bit excessive.  On the other hand, if a generator isn't going to repeat itself for a very long real-time, then that might again indicate that you're throwing too much processor time on random number generation (assuming T > 2^32 or perhaps 2^64).  Now this is completely counter-intuitive and many people will have trouble accepting this.

The purpose of the table with square and cube roots is (when I come up with some reasonable verbage) to give an idea of scale.  For gaming purposes is insanely unlikely that the cube-root number is useful.  I'm only including it for completeness AND as bound as people will tend to be somewhat paranoid about quality.  Likewise, the square root number is mostly overkill but should be sufficient target for an acceptable programmer comfort zone.  As mentioned above the sqrt & cube-root are rules of thumb from that statistics world about when a generator will start to show statistical defects IN A SINGLE PROBLEM.  So, say one thing you need to do is generator a bunch of random vectors in 3D at some uniform grid positions and do something with those values.  That's an example of a single problem.  Sticking to T=2^32, then sqrt(2^32) = 65536, divide by 3 (number of components/vector) = ~21845, cube root (for 3D) ~= 7281:  So if the uniform grid of vectors is smaller than or equal to 7281x7281x7281...then you should be more than comfortable with the period.  When the RNG moves on to the next problem, then you start anew.  So all you really care about is the scale of the single largest problem.

Junior Devvie

 « Reply #3 - Posted 2012-11-23 19:31:09 »

Never mind. I missed a whole paragraph of text the first time I read it. You already covered everything I thought I was pointing out. I misread that section as just:

Quote
As mentioned above the period of a PRNG is the length of the sequence that it generates.  Once the period is exhausted, the sequence wraps-around and starts to repeat itself.

There's the mistaken notion in games that one needs a period long enough that it never repeats during gameplay.  Not at all, it simply should be long enough that every single computation has more than enough values to complete.  To give a rough idea of 'scale', here's a table of common short periods with its square and cube roots:

I wasn't suggesting that exhausting the entire period of a prng was a practical concern. Just that it was a better example of scales. Ignore it, since it doesn't cover the same things. Maybe a another possibility is to have a chart like this and just make a note that the square root of 2^n is just 2^(n/2) and 2^(n/3) for cube roots.

 Decimal Value Note 2^16 65536 Greater than the number of ____ 2^32 4294967296 Greater than the number of ____ in the ____ 2^n 123456789...012345678 Some note about the scale of this number

I agree with you on everything on the period of a PRNG now, but the presentation on this page could be improved. First, I don't see how roots give a better concept of scale because of the relation between roots and powers. It's like a bad dictionary defining a word in terms of another form of that same word. Second, you need to explain what square roots and cube roots represent and how they should be analyzed. I'm vaguely familiar with the ideas. Enough so that I'm confident that you know what you're talking about, but not familiar enough that I could explain it to another person. Explain what you mean by birthday spacing, what the roots mean from a statistical perspective, and when you would need to be concerned about either T^1, T^(1/2), or T^(1/3) in game programming.
Roquen
 « Reply #4 - Posted 2012-11-24 17:08:53 »

Nice feedback..thanks.  I work on adding the stuff you've mentioned.
Roquen
 « Reply #5 - Posted 2012-11-27 16:19:20 »

Minor updates.  Ripped out some useless distracting junk.  Gone is the table and the mention of cube-root.  Cube root is gone because that rule of thumb seems to only apply to LCGs and lower quality generators and there's about zero chance a game runtime problem being related to birthday spacing.

Why the square root of the period?

My knowledge of number theory, probability and statistic is not sound enough to give an accurate nor convincing response.  My understanding of the reasoning is as follows.  http://en.wikipedia.org/wiki/Ramsey_theory coupled with:
http://en.wikipedia.org/wiki/Pigeonhole_principle
http://en.wikipedia.org/wiki/Birthday_problem

And I believe it's exactly the same notions as why the http://en.wikipedia.org/wiki/Birthday_attack works.

PRNGs are sequences which generated by some method based on the properties of the chosen algebra or algebras.  Examples LCGs are based on the integer mod some-smaller integer.  LSFR are based on 2-adic numbers (or bits).  An XorWOW combines 2-adic with integers.  And (via Ramsey's) once enough 'data' has been seen, then the underlying structure starts to become obvious.

From here: http://en.wikipedia.org/wiki/Birthday_problem#Approximations, we have:

Pr[(n,m)] ~= 1-exp(-m2/2n)

Setting the probability = .5 (50%) and solving for

1-exp(-m2/2n) = 1/2
exp(-m2/2n) = 1/2
-m2/2n = log(1/2)
m2 = -2n log(1/2)
m = sqrt(2*log(2)) sqrt(n)
m ~= 1.17741 sqrt(n)

Tossing away the scale factor (1.17741) gives an additional 17% safety margin...and thus was born the rule-of-thumb (I think).

Or I'm making this harder than it really is and the root is from:
http://en.wikipedia.org/wiki/Law_of_large_numbers and
http://en.wikipedia.org/wiki/Central_limit_theorem.

As far as I'm concerned, folks like George Marsaglia, Pierre L'Ecuyer & Richard Brent have all mentioned this rule of thumb and that's good enough for me.
Roquen
 « Reply #6 - Posted 2014-01-31 15:22:19 »

Hot off the presses:  To any RNG nut cases, I'm so happy I could cry.  A new random number generator almost as fast as a XorShift that (the paper claims) beats WELL1024a or MT19937 (that's the Mersenne Twister) at Crush and BigCrush.  To others...this is FASTER than ThreadLocalRandom and many times faster than Random...both of which are aweful.

SEE: http://xorshift.di.unimi.it.

I'll toss a version into the grabbag later.
jonjava
 « Reply #7 - Posted 2014-02-01 09:05:32 »

Roquen
 « Reply #8 - Posted 2014-02-02 14:52:49 »

https://github.com/roquendm/JGO-Grabbag/blob/master/src/roquen/math/rng/XorStar64.java

Using a few boxes I tossed a couple days worth of CPU time at (half a dozen Crush and tons of SmallCrush) tests and haven't found a fail.  I'll let the experts tear this apart for scientific usage.  Bottom like is this is very fast and performs better at statistical tests than some slower (including much slower) methods do.  On my box it's faster than ThreadLocalRandom, so this is an excellent choice for general game purposes (again excluding gambling.)

For those that care (hopefully you don't) all Crush and SmallCrush tests in the batteries were started with a low hamming weight seed values in an attempt to cause failures.
sebastiano.vigna

Innocent Bystander

 « Reply #9 - Posted 2014-03-18 12:22:13 »

I found by chance this discussion... my 2€¢:

1) The data reported at http://prng.di.unimi.it/ is entirely public and open. You can redo the computation from scratch, or inspect the TestU01 results.
2) It is not very useful to start a xorshift64* generator with low hamming weights because due to the small state space it gets back to normality after very few iterations; the effect would be more pronounced on, say, the Mersenne Twister, which has a horrible escape-from-zeroland time.
3) The whole xorshift* business was started with the idea of replacing ThreadLocalRandom—the biggest ever made mistake by the Java developers. They could have implemented any reasonable new generator with a small state space, and instead they replicated Random and its horrible congruential linear generator: if you want to get scared, https://twitter.com/joshbloch/status/269478731238760448
4) I'll publish soon a slightly different generator with 128 bits of space that beats ThreadLocalRandom on every type of call except nextInt(); you might be interested in that, too.

Ciao!
Roquen
 « Reply #10 - Posted 2014-03-18 12:58:29 »

Wow, I think this is the first time the author of something popped-out-of-nowhere to comment on a comment of mine...if you follow me.  I very jazzed by your RNG because it's damn cheap and I can't find any statistical holes for sampling sizes of interest here.

Quote
2) It is not very useful to start a xorshift64* generator with low hamming weights because due to the small state space it gets back to normality after very few iterations; the effect would be more pronounced on, say, the Mersenne Twister, which has a horrible escape-from-zeroland time.
I always like to attempt to poke holes in thing myself and choosing low hamming weighs seemed liked like the most likely to produce failures.

Quote
3) The whole xorshift* business was started with the idea of replacing ThreadLocalRandom—the biggest ever made mistake by the Java developers. They could have implemented any reasonable new generator with a small state space, and instead they replicated Random and its horrible congruential linear generator: if you want to get scared, https://twitter.com/joshbloch/status/269478731238760448
Uggh.  Additionally the non-randomness is coming from the seeding process since the generators are never moving through the sequence.

Quote
4) I'll publish soon a slightly different generator with 128 bits of space that beats ThreadLocalRandom on every type of call except nextInt(); you might be interested in that, too.
I'm curious to look at it, but from a practical standpoint a 2^64-1 period is way larger than a game runtime needs and the sampling sizes are small enough that even if some statistical randomness test were important the 64-bit version should be more than good enough.  That's why I was running SmallCrush tests rather than Crush.  Well unless somehow a java version of the 128-bit version was faster than the 64-bit.  Is the 128 bits of state stored as two 64-bit data data chunks?

P.S. If you're ever bored you could peek at the wiki-ish page at the top and give any comments that come to mind.
Roquen
 « Reply #11 - Posted 2014-07-30 07:47:51 »

I like this Sebastiano Vigna person.  New paper, shorter dependency chain generator and higher quality.  What's not to like?

https://github.com/roquendm/JGO-Grabbag/blob/master/src/roquen/math/rng/XorPlus128.java
Riven
« League of Dukes »

« JGO Overlord »

Medals: 953
Projects: 4
Exp: 16 years

 « Reply #12 - Posted 2014-07-30 08:00:22 »

I like this Sebastiano Vigna person.  New paper, shorter dependency chain generator and higher quality.  What's not to like?

https://github.com/roquendm/JGO-Grabbag/blob/master/src/roquen/math/rng/XorPlus128.java

 1  2  3 `    long s0 = data0;        data0  = s0;`

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Mike

« JGO Spiffy Duke »

Medals: 143
Projects: 1
Exp: 6 years

Java guru wannabe

 « Reply #13 - Posted 2014-07-30 19:29:04 »

Just in case data0 was changed by another thread? Sometimes people write funny code

Mike

My current game, Minecraft meets Farmville and goes online
State of Fortune | Discussion thread @ JGO
Roquen
 « Reply #14 - Posted 2014-07-31 06:59:17 »

If you're thinking the two data elements should be a ring-buffer:  you're right.  And if you're thinking those signed shifts should be unsigned:  you're right.  3 bugs in 3 lines of code:  go me!   Fixed.
Pages: [1]
 ignore  |  Print

 Riven (23 views) 2015-04-16 10:48:47 Duke0200 (36 views) 2015-04-16 01:59:01 Fairy Tailz (27 views) 2015-04-14 20:13:12 Riven (29 views) 2015-04-12 21:36:37 bus hotdog (46 views) 2015-04-10 02:39:32 CopyableCougar4 (47 views) 2015-04-10 00:51:04 BurntPizza (48 views) 2015-04-06 22:06:58 ags1 (51 views) 2015-04-02 10:58:48 Riven (49 views) 2015-04-01 18:27:05 ags1 (66 views) 2015-03-31 10:55:12
 BurntPizza 24x theagentd 21x wessles 15x 65K 12x Rayvolution 12x kingroka123 11x alwex 10x KevinWorkman 9x kevglass 8x ra4king 8x phu004 8x Hanksha 7x SHC 7x Olo 7x Ecumene 7x chrislo27 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org