Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (120)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Random Number Generator  (Read 8045 times)
0 Members and 1 Guest are viewing this topic.
Offline DrHalfway
« Posted 2012-10-23 23:04:02 »

Hello JGO Community

While browsing around these forums, lately i've encountered alot of posts about Random numbers and random number generators. I'm here today to share a piece of code that we use very successful in our engine for fast and efficient random number generation. The source code is mainly thanks to Matthew Jackson who is collaborating with me in making the engine into a reality. Without further ado, here is the source, it is a 63 bit random number generator.

- Basic Feature List

~ ability to get and set the current seed
~ ability to get random numbers between min and max (long)
~ ability to get random numbers between min and max (float)

- Source

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
/**
 * @author Matthew Jackson - Original Author
 * @author David Arayan (DrHalfway) - Modifications to code
 * @version 1.0 - Used as part of HalfWay Game Engine Math Library
 */

public class Random {
   private long seed;
   
   /**
    * Default Constructor which generates the seed based on system time.
    */

   public Random(){
         seed = System.nanoTime();
   }
   
   /**
    *
    * @param seed The value to start the random number generator.
    * A seed value of 0 generates a random seed based on system time
    * which is the same as the default constructor.
    *
    */

   public Random(long seed){
      if (seed == 0){
         seed = System.nanoTime();
      }
      this.seed = seed;
   }
   
   /**
    * Uses an XORShift to produce a 63 bit random number.
    * Java's variables are all signed so the 64th bit is lost.
         * Period is 2^64 - 1 (thanks Roquen)
    * @return A pseudo-random 63 bit number
    */

   private long rand() {
        seed ^= (seed << 13);
        seed ^= (seed >>> 7);
        seed ^= (seed << 17);
        //return Math.abs(seed - 1);
                  return seed;
   }
   
   /**
    * Allows the user to assign a min and max value for the numbers
    * they want returned.
    * @param min Minimum value to be returned (Can be negative)
    * @param max Maximum value to be returned (Can be negative)
    * @return A long random value between min and max
    */

   public long rand(long min, long max ){
      if(min > max){
         return rand(max,min);
      }
      if (min == max) {
         return min;
      }
      return (rand() % (max + 1 - min)) + min;
   }
   
   /**
    * A floating point random number generator.
    *
    * @param min The minimum floating point value
    * @param max The maximum floating point value
    * @param dev The number of decimal places you want returned.
    * dev = 10 will return 1 decimal place.
    * dev = 100 will return 2 decimal places.
    * @return returns random floating point value between min and max.
    *
    */

   public float randf(float min, float max, int dev) {
      if (min == max) {
         return min;
      }
      return ((float)rand((int)(min * dev), (int)(max * dev))/dev);
   }
   
   /**
    * Returns the current seed for the random number generator
    */

   public long getSeed() {
      return seed;
   }
   
   /**
    * Sets the current seed to seed
    */

   public void setSeed(final long seed) {
      this.seed = seed;
   }
}


Below is a simple test program

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
public class test {
   public static void main(String[] args) {
     
      Random rand = new Random();
      final int guess = 42;
     
      while (true) {        
         long guessed = rand.rand(1, 100);
         
         System.out.println(guessed);
         
         if (guessed == guess) {
            break;
         }
      }
   }
}


EDIT : Below I've included a small benchmark program for bench marking the run-times of the above Random generator Vs Java's Random generator.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
public class test {
   public static void main(String[] args) {
     
      Random xRandom = new Random();
      java.util.Random jRandom = new java.util.Random();
     
      final int runs = 1000;
      long startTime = 0, stopTime = 0;
      float xRun = 0.0f;
      float jRun = 0.0f;
     
      /*
       * RUN THE JAVA RANDOM BENCHMARK
       */

     
      startTime = System.nanoTime();
     
      for (int i = 0; i < runs; i++) {
         jRandom.nextInt(100);
      }
     
      stopTime = System.nanoTime();
     
      jRun += ((stopTime - startTime) * 1e-6);
     
      /*
       * RUN THE XOR RANDOM BENCHMARK
       */

     
      startTime = System.nanoTime();
     
      for (int i = 0; i < runs; i++) {
         xRandom.rand(0, 100);
      }
     
      stopTime = System.nanoTime();
     
      xRun += ((stopTime - startTime) * 1e-6);
     
      System.out.println("RunTime for JRandom: " + jRun + "ms For: " + runs + " runs");
      System.out.println("RunTime for XRandom: " + xRun + "ms For: " + runs + " runs");
   }
}


And Below are bench-marking results for different runs on my machine.

RunTime for JRandom: 0.283136ms For: 1000 runs
RunTime for XRandom: 0.236113ms For: 1000 runs

RunTime for JRandom: 3.022447ms For: 10,000 runs
RunTime for XRandom: 2.67428ms For: 10,000 runs

RunTime for JRandom: 11.892359ms For: 100,000 runs
RunTime for XRandom: 5.694059ms For: 100,000 runs

RunTime for JRandom: 23.15375ms For: 1,000,000 runs
RunTime for XRandom: 9.104691ms For: 1,000,000 runs

RunTime for JRandom: 120.58705ms For: 10,000,000 runs
RunTime for XRandom: 33.68179ms For: 10,000,000 runs

RunTime for JRandom: 1094.5873ms For: 100,000,000 runs
RunTime for XRandom: 289.4332ms For: 100,000,000 runs

Hope it helps you all for any game creation needs. All comments/contributions to the source are welcome!

EDIT2 - I've generated and added a bitmap image for comparison of "randomness" of this versus java's random generator. Basically a pixel value is picked randomly in the range of 0 to 255. The images are 512 X 512 in size. Left is the above Generator, Right is Java's Generator.



EDIT3 - Changed the rand() function as suggested by Roquen, cheers!

~DrHalfway

Offline sproingie

JGO Kernel


Medals: 202



« Reply #1 - Posted 2012-10-24 00:09:07 »

How does it fare on a randomness test suite?  Not that I expect j.u.Random to show flying colors there either, but it'd still be a good benchmark for comparison other than raw speed.

http://www.phy.duke.edu/~rgb/General/dieharder.php
Offline Best Username Ever

Junior Duke





« Reply #2 - Posted 2012-10-24 01:12:43 »

How much randomness do you get out of such a system? It does not look like it would work very well. Is it based on an existing rng scheme?

You should also add something to the no argument constructor to prevent two instances created around the same time from sharing the same seed. (Just in case?)

1  
2  
3  
4  
5  
6  
7  
8  
9  
   private long seed;
+   private static long thing = System.nanoTime() ^ 0x1234567812345678L;
   
   /**
    * Default Constructor which generates the seed based on system time.
    */

   public Random(){
+        seed = (thing++) + System.nanoTime();
   }
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline DrHalfway
« Reply #3 - Posted 2012-10-24 01:35:42 »

I have updated the above with images of a randomness test on two grey scale images of size 512 x 512, comparing Java's random generator Vs Halfway Generator.

Also, as far as nano times are concerned, it is not a problem to do this.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
public static void main(String[] args) {      
   Random rand = new Random();
   Random rand2 = new Random();
     
   System.out.println("First Nano Time: " + rand.getSeed());
   System.out.println("Second Nano Time: " + rand2.getSeed());
}

// results

/*
First Nano Time: 12199246486318
Second Nano Time: 12199246488319
*/


This is more than enough for varying "randomness" between two generators. If you'd like, you can make the seed "static", the random pattern will not be repeating itself for a very-very-VERY long time  Grin

Offline ReBirth
« Reply #4 - Posted 2012-10-24 02:06:20 »

Seems legit. I like the fact it runs fast. Usually I even use Math.random() Roll Eyes

Offline UltimateSin

Junior Newbie


Medals: 2



« Reply #5 - Posted 2012-10-24 02:49:54 »

How much randomness do you get out of such a system? It does not look like it would work very well. Is it based on an existing rng scheme?

It's an XORShift RNG (A subset of a Linear Feedback Shift Register [LFSR]) . The system is extremely fast at generating pseudo-random numbers and has been in use for a long time. The numbers that are being used for the shifts aren't just off the top of your head. They are picked to create a maximal 64 bits shift register (63 bits are caused from the absolute function, effectively doubling up the numbers that can be returned therefore halving the actual variation in numbers returned).

With LFSRs the sequence of numbers will eventually repeat. To be maximal means every single combination of bits (apart from the all zeroes) will appear before the sequence repeats. This means there are a total 9,223,372,036,854,775,808 numbers in a 64-bit LFSR that will appear before the sequence repeats itself when using a maximal sequence.

This system can be "cracked" with a given sample size so you wouldn't use it alone in a security system but there are security algorithms based off it.

However for the sake of games programming, 99 times out of 100 your random number generator doesn't need to be secure.

If you want more information there is plenty of information on the topic all over Google.

I hope this enlightens some of you who haven't seen this type of RNG before.

Matt.
Offline Roquen
« Reply #6 - Posted 2012-10-24 03:46:13 »

XORSHIFT and some other notes I made here: http://www.java-gaming.org/topics/math-random/18426/msg/168661/view.html#msg168661

The version above is very broken.  You can't just change ops around willy-nilly.  As written it has an unknown period...and that's very very bad.

1  
2  
3  
4  
5  
6  
7  
   /** XORSHIFT base generator (George Marsaglia "Xorshift RNGs", Row 1 Column 3)*/
   private long rand() {
        seed ^= (seed <<  1);
        seed ^= (seed >>> 3);
        seed ^= (seed << 45);
        return seed;
   }


This will have a period of (264-1), but I have know idea about the statistical properties about this specific choice.

The ranged result methods need rethinking.
Offline Roquen
« Reply #7 - Posted 2012-10-24 13:09:31 »

FOLLOW UP!  In a moment of work avoidance I ran the corrected version above through SmallCrush and it performs worse than a good LCG.  Specifically it fails 8 out of 15 tests.  Didn't bother with BigCrush.  Results here: http://pastebin.java-gaming.org/c9c0d928f22

Changing the values to the one mentioned in the paper as being on of his favorites [13, 17, 5], drops the failure rate to 3.  Summary (SmallCrush only):

  1  BirthdaySpacings                 eps 
  6  MaxOft                           eps 
  8  MatrixRank                       eps





Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #8 - Posted 2012-10-24 13:30:22 »

I use a m sequence with a plain counter. I then add these before using them. This makes it non linear but adds a bias in the last bit. Not much though. Also the period becomes 2^128-1. Not that you need that kind of period.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Roquen
« Reply #9 - Posted 2012-10-24 14:16:11 »

On XORSHIFT: I screwed up when I glanced at the paper and grabbed a 32-bit constant set (oops).  A proper 64-bit set is [13,7,17], which only fails one SmallCrush (MatrixRank).

@delt0r: Most of the time I just use a 32-bit LCG and don't worry about it.  If I need something better, then WELL1024.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline UltimateSin

Junior Newbie


Medals: 2



« Reply #10 - Posted 2012-10-25 00:06:51 »

You can't just change ops around willy-nilly.

I took over because I wrote the RNG and to be fair the OP shouldn't have posted it because he knew none of the theory behind it so I came in to answer and clarify things for some of the posters.

As for the period as you said it is 2^64 - 1 (Maximal) which is why I chose these numbers. As for the statistical properties, I didn't realise that different choices in numbers could effect it. I will have to read up and better understand all these properties. As for now, I will change the values to your last suggested ones and have the OP correct it in the code.

Edit: I'm not having a go at the OP there he is trying to do the right thing by the community and provide you guys with some working code =)
Offline DrHalfway
« Reply #11 - Posted 2012-10-25 00:14:07 »

Updated the rand() function as suggested by Matt and Roquen, cheers guys. Oh and Matt, welcome to the community.

Offline Roquen
« Reply #12 - Posted 2012-10-25 08:44:53 »

That second line has a typo: seed >> 7 must be seed >>> 7.  The signed instead of unsigned shift breaks everything.  I'd strongly recommend losing the Math.abs(seed - 1) and just return seed.  It's a significant performance hit that doesn't buy you anything.

On the whole I'd really suggest using a 32-bit xorshift instead of 64-bit.  You just don't need the long period (or rather is massively unlikely...and if you do you should know why...and you should probably rethink what you're doing if you need upward to ~3 billion random number to make a decision in a video game).  On 64-bit VMs the performance will be similar, but not so for 32-bit...which is a sad reality.  Android?  I'll let people that have a clue respond here.

Err...I'll just toss together an example and let people critic me!
Offline DrHalfway
« Reply #13 - Posted 2012-10-25 09:19:13 »

Cheers again Roquen, updated the code accordingly. As far as Android goes, haven't really had a bottleneck with using the above version, then again, we only get something like 80FPS on Android compared to 4000FPS PC (The whole engine). Might look into a 32 bit version instead.

This may not be true but isn't Math.abs() call extremely fast? I know it is on C++ (normally translates to a single instruction on modern hardware) but have't really bothered to benchmark java, always assumed its about the same.

Offline Roquen
« Reply #14 - Posted 2012-10-25 11:46:16 »

Speed is always relative.  In this case you have a dependency chain of length 6 which is being extended to 9 (negate, conditional move, subtract)...so it's 50% longer.  Luckily there is no reason to prefer low-bits over high bits, so you could replace the return statement with: return (seed >>>1); if you want to stick with unsigned 63 bit results (which only pushes the chain length up to 7, or ~17% longer).

My opinion is to return 64-bit results and let call-site do any fix-up they need locally.  Personally the vast majority of my random number generation is for some fixed number of bits.  But having said that, when inlined the two shift sequence would be folded into one given the proposed change above.
Offline Best Username Ever

Junior Duke





« Reply #15 - Posted 2012-10-25 16:05:10 »

I see you took out the return Math.abs(seed - 1); That made the RNG scheme seem dubious. There is no reason why you could not get 64 bits out of this scheme in Java if it works for a 64 bit unsigned int. (And it sounds like there is no need to throw out any bits.) I look into my crystal ball and see someone adding that line to get results in the domain [0, 2^63 - 1] instead of any 64 bit signed number other than zero. If that's the case you're unnecessarily limiting yourself to one fewer bit of randomness per call. You also changed a comment to read "Period is 2^64 - 1 " instead of "Max period is 2^64 - 1", which is good. I was going to say the minimum period is more important, but you've already corrected the comment and the old code that broke it. There are still a few things you should change.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
public class Random {
   private long seed;
   
   public Random(){
+        long s = System.nanoTime(); // See note
+        setSeed(s != 0 ? s : 1);
   }
   
   public Random(long seed){
+        setSeed(seed);
   }
   
+  public long rand() {
        seed ^= (seed << 13);
        seed ^= (seed >>> 7);
        seed ^= (seed << 17);
        return seed;
   }

+  public long randNonNegative() {
+      return rand() >>> 1;
+  }

+  public long rand(int bits) {
+      return rand() >>> (64 - bits);
+  }
   
   public long rand(long min, long max ){
      if(min > max){ // See other note
+        long m = max;
+        max = min;
+        min = m;
      }
      if (min == max) {
         return min;
      }
      return (rand() % (max + 1 - min)) + min;
   }
   
   public float randf(float min, float max, int dev) {
      if (min == max) {
         return min;
      }
+     return ((float)rand((long)(min * dev), (long)(max * dev))/dev); // Probably should be long and not int.
   }
   
   public long getSeed() {
      return seed;
   }
   
   public void setSeed(long seed) {
+     if(seed == 0)
+       throw new IllegalArgumentException("Seed cannot be zero."); // See third note
      this.seed = seed;
   }
}


Note 1: Although I can't get two calls in a row to return the same nano time on my computer, that might not be the case on all platforms. Return values for System.nanoTime() can be as impercise as currentTimeMillis() which may not even have millisecond precision. It's probably not likely that a computer is fast enough to create two objects but doesn't have a timer accurate enough to return different values in that time span, but maybe there's a small chance. I fixed something else that's far less likely. nanoTime() could return zero, so that could create a bad Random instance.

Note 2: Is this the behavior you want for bad min/max values?

Note 3: Changed it to throw an exception to prevent zero values. I changed the constructor behavior, too, but maybe you wanted zero to be a special value. You can choose one method or the other (or allow zero seeds), but setSeed should probably be consistent with the constructor.
Offline theagentd
« Reply #16 - Posted 2012-10-25 17:40:31 »

Note 2: Is this the behavior you want for bad min/max values?
Shouldn't it throw an exception in that case? o_O

Myomyomyo.
Offline Roquen
« Reply #17 - Posted 2012-10-26 09:27:56 »

Throwing an exception for setting a seed to zero is a bad idea IHMO.  This problem should be addressed as follows:
1  
2  
3  
4  
5  
6  
/**
 * (blah, blah)
 * <p>
 * If seed is zero, then (we do this)
 */

public void setSeed(long seed) { ... }

Throwing an exception is exposing an implementation detail.  As long as the code does (we do this), then it's perfectly to contract.  One common thing to do, say in procedural generation, is to use a pretty poor hashing function to seed a PRNG so zero is a pretty reasonable seeding value.  The procedural content generator really should care about any specifics of whatever PRNG it ends up using.

@UltimateSin: I forgot to mention that the various shifting constants (and their permutations) only insure full period and not any statistical properties.
Offline Best Username Ever

Junior Duke





« Reply #18 - Posted 2012-10-26 21:57:19 »

I agree in this case it exposes implementation details and have no interest in arguing one way or another, but I disagree that throwing certain exceptions exposes implementation details. Though in this case it does. But I don't think you can avoid exposing implementation details if that were your only change. This class is not a generic stream of random bits and already abuses that problem. For example, there is no differentiation between seed and state. The fact that getState() getSeed() returns a long instead of an instance of RngState<Random> also carries that problem.

I mainly used the exception to convey an idea (there were no doc comments and people would have just ignored a "don't use zero" statement.) It's probably ...

Sorry, I walked away from the computer, forgot my train of thought for this post, and remembered my original train of thought for my previous post. Tongue My original thoughts were that the contract of setSeed should be that only values returnable by getSeed should be considered valid. A user of this class would only choose arbitrary seeds for the instantiation of the object (in which case the contract could reasonably be implementation specific because it is a constructor). All calls to setSeed should assume that the user knows they have a valid seed value, whether that key was obtained from getSeed() or obtained using a static utility function or hardcoded by the programmer. Under that contract, no implementation details are exposed in ordinary methods.

(The setSeed/getSeed name bugs me a lot more now. Seed should be changed to state.)
Offline Roquen
« Reply #19 - Posted 2012-10-27 11:56:13 »

My verbage was unclear: I wasn't talking about exceptions in general, only in these kinds of situations.  WRT: seed vs. state.  Two distinctly different notions...they only get blurred in short-period generators were state is representable by (say) a 32 or 64 bit integer.  If you want to be nit-picky, then you can't really get a seed, only a state...it's simply a pragmatic choice to name the methods so...and it would be pretty unclear to people that don't understand the "guts" of generators to have "setSeed" & "getState" for these short period generators.
Offline Roquen
« Reply #20 - Posted 2012-11-15 08:18:50 »

For "NON-GAMING PURPOSES ONLY".  In a moment of work avoidance I added a Weyl generator to the above (making it an XorWOW) and ran it through Crush.  It passes all test.  As a point of reference, the famous Mersenne twister (on it's own) will fail 2.
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #21 - Posted 2012-11-15 09:51:17 »

I have no idea why the over rated, slow and quite poor MT is so popular. It doesn't even fix the problem it was suppose to solve. That is the hyperplanes problem, it just has a lot of them. Weyl generator + m sequence, done. Faster, no hyperplanes and great for serious random number. The only thing you shouldn't use it for is crypto stuff.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Roquen
« Reply #22 - Posted 2012-11-15 09:54:47 »

I think it's because it has the one of most cool names is about the only reason.  I want to cry every time I see a game using MT.  I slowly working on a runtime game PRNG wiki page so HOPEFULLY nobody here will fall into that trap.
Offline Varkas
« Reply #23 - Posted 2012-11-15 10:42:23 »

Over there is a XOR-shift generator mentioned, which seems to perform well on test suites:

http://www.javamex.com/tutorials/random_numbers/xorshift.shtml

Quote
The "magic" values of 21, 35 and 4 have been found to produce good results. With these values, the generator has a full period of 264-1, and the resulting values pass Marsaglia's "Diehard battery" of statistical tests for randomness4. L'Ecuyer & Simard (2007)5 also found that values of 13, 7 and 17 fail on only 7 of the 160 tests of their BigCrush battery (for comparison, java.util.Random fails on 21, while crypographic generators such as Java's SecureRandom— as indeed we might expect— generally pass all tests).

if (error) throw new Brick(); // Blog (german): http://gedankenweber.wordpress.com
Offline Roquen
« Reply #24 - Posted 2012-11-15 10:58:46 »

Remember that all of this statistical testing is a tangent and is of about zero interest for a game runtime.  Quickly tossing the [21,35,4] numbers in (without a Weyl) and it fails 2 SmallCrush tests where the current [13,7,17] only fails one.
Offline Roquen
« Reply #25 - Posted 2012-11-15 12:06:56 »

Hehe:  "A man is only as interesting as his contradicts".

Seriously, I understand were you're coming from.  That's why I'm doing a first pass at a wiki page. 

The problems with java.util.Random isn't one of quality.  The quality of its generator is poor, but it is perfectly adequate for virtually all game runtime usage.  I most often use a LCG32 which is poorer quality...but it's sufficient most of the time.  It's the design of Random that's the problem...it doesn't properly target any specific use-case.  You can get sufficient quality much faster and even vastly superior quality faster.  So the bottom line is that you're paying a higher than needed cost.  If you don't generate many random numbers then it's not really a concern.  (I'm ignoring dimensions here)

On the topic of quality, the only reason to consider it here is the notion of maximizing what you get for a given fixed cost.  Even if that is only addressing programmer conform-zone issues...it's for "free" so why not choose the known constants that perform the best.

WRT: The link you provided.  The thing is there are thousands of 64-bit xorshift and I "know" that none of them alone will pass Crush or BigCrush.  No LSFR random number generator will (including MT).  DIEHARD (the quoted test) is dated and SmallCrush contains the same tests.  It fails SmallCrush simply because that test-suite has been updated to require more computations per test than DIEHARD.

Does that at least partially clarify?
Offline Varkas
« Reply #26 - Posted 2012-11-15 12:53:07 »

I think this was a reply to the message which I deleted soon after posting it. Soon after posting it appeard to me that it isn't of general interest and that I don't want to stir up more discussion, so I deemed me better to delete it. Sorry for writing it in the first place. Random numbers are a wide field, require in depth math and computational science knowledge and I assume my own level in those domains is about as good to decide which RNG is good for my purpose, or to see if code is efficient. So I want to leave the expert discussion to you and those who know more. For myself I conclude:

- Random() is usually good enough for me needs (i.e. I made no mistakes in my past projects, that need to be fixed).
- I used mersenne twister in my C/C++ programs and learned that it is inefficient, but most likely still good enough.
- My choice to use SecureRandom() for high quality random numbers in Solarex was right, since performance isn't an issue there, but the quality of the number sequence is.
- Xor-Shift is an interesting method which I didn't know before, since it's fast and passes standard tests (i.e. it doesn't have any obvious fails)

... and more I don't need to know for my projects. Sorry for stirring up more discussion than needed  Sad

if (error) throw new Brick(); // Blog (german): http://gedankenweber.wordpress.com
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #27 - Posted 2012-11-15 13:38:28 »

For the record and for completeness. Using a xor shift scheme with the correct constants produces m-sequences. These have clearly defined randomness properties. They are heavily used for testing binary circuits and for communications etc. They have nice mathematics behind them and have all sorts of properties that make them useful for many things.

In short we know a lot about them.

However random here is typically defined as the Spectrum it produces should be white (or the autocorrelation function should be a Dirac delta). Alternatively an 8 bit register will produce every 8 bit number once and only once except 0. Clearly this is not true random. For somethings this is good. For example with stochastic integration you get faster convergence because successive numbers clump less than true random.

If non of that matters to you, then a simple m-sequence generator is perhaps going to be the easiest and fastest by a long shot.

For the few of us doing some scientific simulations, we perhaps want to break up some of the m-sequence structure. This is most easily done with a the previously mentioned weyl generator and then add the results together. This gives nonliterary and passes every test (or not) the same as true random. It is also just 2 extra additions compared to a m-sequences. It is often even faster than LGC because % tends to be pretty slow.

For crypto... well stop reading here for start. Your doing it wrong.

I have no special talents. I am only passionately curious.--Albert Einstein
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (43 views)
2014-10-16 15:22:06

Norakomi (33 views)
2014-10-16 15:20:20

lcass (37 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (67 views)
2014-10-14 00:35:47

TehJavaDev (60 views)
2014-10-14 00:32:37

BurntPizza (73 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45

BurntPizza (86 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!