We all know that computer generated random numbers are not really random at all, but just pseudo-random. And I know that is a lot of discussion about how best to generate random numbers.
To be honest, I have not taken much notice of this in all the programming that I have done but today I found out that it is important.
Without going into the (boring) details, I have been generating a random number that is either 1 or 2 – but I generate quite a few very quickly.
For anybody that is interested the code is something like
r = rand() % n +1 [where n is the range you are interested in]
The problem is, I was returning the same number every time. Only very occasionally did I get the odd difference.
If I increased the range (say generating numbers between 1 and 20), this made no difference (I always got the same number).
However, if I put in a delay between each call to rand(), this “solved” the problem, but this is not a good solution.
Doing some reading around the subject, I think it is to do with the low/high order bits when generating the random numbers.
But that does not help me generate a decent distribution when making very frequent calls to rand().
I seem to recall that there is a C++ class called RNG (Random Number Generator) available and I am sure that Numerical Recipes in C will have something to say on the issue, but I need to look into these.
So you're working on Windows? 🙂
That behaviour is pretty normal. It's like Math.random() and new Random()'s nextInt() in java.
1) First case:
double r1 = Math.random();
double r2 = Math.random();
uses the currentTimeMillis as seed and ask the first random, every single time.
Windows's currentTimeMillis take about 15 milliseconds to update (ubuntu is better IIRC from the last time I tried) so your random is stable during those intervals.
2) Second case:
int seed = 0;
Random random = new Random(seed);
double r1 = random.nextDouble();
double r2 = random.nextDouble();
I supply the seed, so r2 will the next pseudo random number after r1 based on the seed.
If I don't supply the seed, it gets initialized by currentTimeMillis, but on the first time (for new Random()).
So in both cases r2 will differ from r1.
In heuristics you should always use 2) because of:
– the bug you just stumbled upon
– reproducibility if you use the same seed
Actually, in Drools Solver, I did 2 extra improvements on top of this:
– There is only one Random instance, used by any code that needs it. This way can reproduce mosts solver's configuration output a 100%. For example:
double randomChance = moveScope.getWorkingRandom().nextDouble();
– By default, I always use a seed of 0, instead of the currentTimeMillis, so the users of my framework get reproducibility out of the box during development. In production however, it's recommended to configure no seed (so currentTimeMillis).
#include iostream
#include cstdlib
using namespace std;
int main() {
srand(time(0)); // /random/ seed
int a = 0;
int b = 10;
int n = 100;
for (int i=1; i<=n; ++i) {
cout << a+rand()%b << " ";
if (i%10==0) cout << endl;
}
return 0;
}
Output run1:
0 3 3 0 5 9 6 6 2 0
4 3 1 0 6 8 4 2 7 8
1 9 6 1 1 6 9 0 0 0
4 3 5 7 3 0 9 1 6 1
1 2 4 2 3 2 3 9 6 0
7 9 1 6 2 3 2 2 5 4
4 9 7 9 9 0 2 8 1 8
1 4 3 7 7 8 9 2 7 8
2 5 7 4 3 0 9 5 4 4
9 8 5 9 9 4 9 1 4 3
Output run2:
1 1 2 1 6 8 0 1 7 7
2 6 8 0 7 9 3 8 2 3
2 0 1 3 9 9 2 6 5 6
0 9 7 4 2 5 5 2 6 4
0 1 0 0 1 7 0 6 6 4
0 8 6 3 3 6 5 7 4 2
3 4 1 3 0 4 8 5 8 7
2 0 8 2 3 1 0 3 8 8
9 0 6 5 5 1 3 0 8 7
3 1 3 6 4 4 2 5 1 1
Cheers for both comments. I need to look into both of these suggestions.
In the meantime, I downloaded a class from the internet. It too me a while to get it to run but it is certainly more "random" that the C++ functions I was using.
I'll blog the details soon. I am on a different computer at the moment, so don't have all the information to hand.
Thanks again for the feedback.
Hi Aileen
Many thanks for the kind words. I look forward to hearing more from you.
Best Wishes
Graham