Random number generation in C ++ ... the first number is not very random

Question

I am trying to get a uniform random number between 0 and 1 in C ++ without using boost. I do not want to depend on the library.

Whenever I run my program, I seed: srand (time (NULL));

Then I print 8 random numbers. I share different runs of the program with an empty line:

Random number: 0.226063 Random number: 0.449186 Random number: 0.474514 Random number: 0.160779 Random number: 0.220868 Random number: 0.136685 Random number: 0.260120 Random number: 0.843334 Random number: 0.226181 Random number: 0.422253 Random number: 0.808594 Random number: 0.040531 Random number: 0.212377 Random number: 0.421073 Random number: 0.965790 Random number: 0.026305 Random number: 0.226306 Random number: 0.526858 Random number: 0.898279 Random number: 0.378934 Random number: 0.736653 Random number: 0.924420 Random number: 0.718503 Random number: 0.888140 Random number: 0.226463 Random number: 0.157614 Random number: 0.010386 Random number: 0.551936 Random number: 0.391998 Random number: 0.303603 Random number: 0.659396 Random number: 0.465434 

Why is the first number almost the same every time? I do not understand. Should I throw out the first number or something else?

---

Code example:

 #include <iostream> int main() { srand( time(NULL) ); printf("%f\n", (float)rand()/RAND_MAX); printf("%f\n", (float)rand()/RAND_MAX); printf("%f\n", (float)rand()/RAND_MAX); printf("%f\n", (float)rand()/RAND_MAX); printf("%f\n", (float)rand()/RAND_MAX); printf("%f\n", (float)rand()/RAND_MAX); printf("%f\n", (float)rand()/RAND_MAX); printf("%f\n", (float)rand()/RAND_MAX); } 

Answer 1

No, do not discard the first. This distorts the results. The sequence {1,1,1,1,1,1,1} can appear just like any other arbitrary sequence of seven numbers, despite the tendency of people trying to find meaning in everything {1,1,1,1,1,1,1}

Trying to mess with it because you don't like the fact that sequence makes a random number of generations worse and not better.

For what it's worth, you have to make sure your runs are at least on the second side, so that you are not using the same seed (which does not seem to be here). In addition, use the results that PRNG gives you as they are, or find the best generator.

Either you are a statistician / cryptographer where you will not use the usual random function, or it really does not matter! For the vast majority of situations, this is the last.

---

If you do not want fancy (or one of which includes a large number of additional materials), and you are simply unhappy with the one provided with your implementation, it is easy to implement it based on the gcc version, something like:

 seed = (1103515245 * seed + 12345) & 0xffffffff return seed & 0x7fffffff 

And remember that the initial seed value is calculated by the argument specified in srand with module 2 31 -1 to minimize the sequence, which has a linear dependence on the initial seed (there still exists linearity for the sequence, and not on the initial seed value).

The following code can make your life easier if you are just looking for a quick solution that does not depend on external libraries, or spend time implementing more complex generators:

 // Assume 32-bit integer. static int seed = 1; void mySRand (int newseed) { seed = newseed % 0x7fffffff; } int myRand() { seed = 1103515245 * seed + 12345; return seed & 0x7fffffff; } 

---

The following program will really give you an idea of ​​what this algorithm will do with small changes to the initial value provided by mySRand .

It gets the seed from time (NULL) , and then shows you that the seed is outside myRand for twenty consecutive seed values ​​along with percentage changes.

 #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> static int seed = 1; void mySRand (int newseed) { seed = newseed % 0x7fffffff; } int myRand() { seed = 1103515245 * seed + 12345; return seed & 0x7fffffff; } int main (void) { int i, xyzzy, val, lastVal; double avg, diff; xyzzy = time (NULL); mySRand (xyzzy); lastVal = myRand(); printf ("seed=%d, val=%12d\n", xyzzy, lastVal); for (i = 0; i < 20; i++) { mySRand (++xyzzy); val = myRand(); avg = val; avg = (avg + lastVal) / 2; diff = 100 * fabs (avg - val) / avg; printf ("seed=%d, val=%12d, avg=%12.1f, %%chg=%f\n", xyzzy, val, avg, diff); lastVal = val; } return 0; } 

Percent changes are based on the difference between the current value and the average value between the current and previous, so I hope not to introduce bias. Output Example:

 seed=1324533721, val= 1092183454 seed=1324533722, val= 48215051, avg= 570199252.5, %chg=91.544175 seed=1324533723, val= 1151730296, avg= 599972673.5, %chg=91.963792 seed=1324533724, val= 107761893, avg= 629746094.5, %chg=82.888041 seed=1324533725, val= 1211277138, avg= 659519515.5, %chg=83.660545 seed=1324533726, val= 167308735, avg= 689292936.5, %chg=75.727484 seed=1324533727, val= 1270823980, avg= 719066357.5, %chg=76.732504 seed=1324533728, val= 226855577, avg= 748839778.5, %chg=69.705726 seed=1324533729, val= 1330370822, avg= 778613199.5, %chg=70.864150 seed=1324533730, val= 286402419, avg= 808386620.5, %chg=64.571108 seed=1324533731, val= 1389917664, avg= 838160041.5, %chg=65.829626 seed=1324533732, val= 345949261, avg= 867933462.5, %chg=60.141039 seed=1324533733, val= 1449464506, avg= 897706883.5, %chg=61.463005 seed=1324533734, val= 405496103, avg= 927480304.5, %chg=56.279815 seed=1324533735, val= 1509011348, avg= 957253725.5, %chg=57.639642 seed=1324533736, val= 465042945, avg= 987027146.5, %chg=52.884483 seed=1324533737, val= 1568558190, avg=1016800567.5, %chg=54.264095 seed=1324533738, val= 524589787, avg=1046573988.5, %chg=49.875518 seed=1324533739, val= 1628105032, avg=1076347409.5, %chg=51.262038 seed=1324533740, val= 584136629, avg=1106120830.5, %chg=47.190523 seed=1324533741, val= 1687651874, avg=1135894251.5, %chg=48.574735 

so you can see that there really is a big difference in the initial values ​​based on the original seeds that are close to each other.

Answer 2

You can use the standard library, which provides both high-quality PRNG engines and corresponding distribution adapters:

 #include <random> typedef std::mt19937 rng_type; std::uniform_real_distribution<double> u01dist; rng_type rng; int main() { rng.seed(std::time(NULL)); double random_number = u01dist(rng); // ... } 

Answer 3

This is completely normal. PRNG needs to be warmed up. The number on the back of my head is about 1000. This means that after seeding your PRNG, you will get 1000 numbers and throw them away.

The reason is how most generators are implemented. Usually they have the value x = a*x+b , where a and b are constants. So, if you're out of luck, your seeds (which are pretty close in your case!) Are selected so that the first part of the equation does not matter much for the result (i.e., Close to 0 (mod MAX_RAND)). That's why you need to warm up: it sutters the similarity of the seeds you have chosen. That sounds silly, but the way PRNG works (you can leave with throwing 50 instead of 1000, YMMV).

---

Btw., Using rand , is a terrible idea in general. Not only that (for reasons that honestly avoid me), it is rather slow compared to other PRNGs, and the numbers it generates are pretty bad (in terms of entropy, periodicity, etc.). If you don't want to use boost, perhaps you can use gsl, which has almost everything you might need (regarding random numbers).

Answer 4

Perhaps the delay between program execution is too short, so the time function may return seeds that are too similar to each other.

It is difficult to be sure without knowing how the srand function is implemented, but it is a pseudo-random generator, it will output the same sequence for the same seed for several executions. Try to feed the seeds with a longer delay between each other or add a variable complement to the time returned by the time function and see if this affects the yield enough. However, keep in mind that they are not real random numbers.

Answer 5

When I fine-tuned your launch pattern when compiled as C (I don't know C ++ well enough to fix compilation errors without a curse), I didn't see anything but random strings:

 $ while true ; do sleep 1 ; ./rand | head -1 ; done 0.493923 0.353780 0.217848 0.570592 0.430408 0.290481 0.651497 0.006394 0.865017 0.721335 0.581914 0.936602 0.796496 ^C