random number generation in C++ … first number not

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 start my program, I seed with: srand( time(NULL) );

Then I print 8 random numbers. I separate different runs of the program with a blank 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 exactly the same every time? I don't get it. Should I toss the first number out or something?

---

Sample code:

#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

You can use the standard library, which provides both high-quality PRNG engines as well as the appropriate 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 2

Maybe the delay between program executions is too short, thus the time function may be returning seeds that are too similar to each other.

It is hard 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 multiple executions. Try to feed seeds with a larger delay betweem each other, or add a variable padding to the time returned by the time function, and see if this affects the output enough. However, be aware that they are not real random numbers.

Answer 3

No, don't throw out the first one. That skews the results. The sequence {1,1,1,1,1,1,1} is exactly as likely to appear as any other arbitrary seven-number sequence despite the propensity of humans trying to find meaning in everything :-)

Trying to fiddle with it because you don't like the sequence makes the random number generation worse, not better.

For what it's worth, you should make sure that your runs are at least a second apart so you don't use the same seed (that doesn't appear to be the case here). Other than that, use the results that the PRNG gives you as-is or find a better generator.

Either you're a statistician/cryptographer where you wouldn't be using a normal random function, or it really doesn't matter! For the vast majority of situations, it's the latter.

---

If you don't want a fancy one (or one involving a large amount of extra stuff) and you're just not happy with the one provided with your implementation, it's easy to implement one based on the gcc version, something like:

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

And keep in mind the initial seed value is calculated on the argument supplied to srand with a modulus of 231-1 to minimise the sequence having a linear dependence on the initial seed (there's still linearity for the sequence, just not from the initial seed value).

The following code may make your life easier if you're just looking for a quick solution without depending on external libraries or spending time implementing the 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 actually give you an idea as to what that algorithm will do with small changes to the seed value provided to mySRand.

It gets the initial seed from time (NULL) then shows you what the initial values are out of myRand for twenty sequential seed values, along with the 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;
}

The percentage changes are based on the difference between the current value and the average between the current and the previous so as to hopefully not introduce bias. Sample output is:

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 there's actually a large difference in starting values based on initial seeds that are close together.

Answer 4

That's perfectly normal. PRNG's must be warmed up. The number I have in the back of my head is something about 1000. That means, after seeding your PRNG, get 1000 numbers and throw them away.

The reason is how most generators are implemented. They are typically something like x = a*x+b, where a and b are constants. So, if you're unlucky, your seeds (which are in your case pretty close!) are chosen so that the first part of the equation does not have much relevance to the outcome (i.e. close to 0 (mod MAX_RAND)). That's why you have to warm up: It irons the similarity of your chosen seeds out. It sounds stupid, but that's how PRNG's work (you might get away with throwing out 50 instead of 1000, YMMV).

---

Btw., using rand is a terrible idea in general. Not only that (for reasons that honestly escape me) it is quite slow compared to other PRNG's, also the numbers it generates are quite poor (in terms of entropy, periodicity and so forth). If you don't want to use boost, maybe you can use gsl which has pretty much everything you could need (regarding random numbers).

Answer 5

When I slightly tweaked your sample to run when compiled as C (I don't know C++ well enough to fix the compile errors without cursing) I saw nothing but random-looking first lines:

$ 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