1

I have a program, in C, which creates an array of 1000 integers using a random number from 0-999 and then performs some sort of algorithm on that array. In order to test the algorithm's running time, I try running the program 10000 times, but every time I run it the array is the same for a few arrays and then it changes. I have used the srand() function to feed the seed with the current time, but it still does not help.

Is there an alternative solution to rand() or a way to fix this? My function is: 

void getarray(int *ptr1, int size, int option){
    int n;
    srand(time(NULL));
    for(n=0; n<size; n++)
        *(ptr1+n) = *(ptr2+n)= rand()%1000; 
}

Thanks in advance!

Fred Larson
  • 60,987
  • 18
  • 112
  • 174
AYR
  • 1,139
  • 3
  • 14
  • 24
  • 7
    You should only call srand once: on program startup. – Pubby May 18 '13 at 11:41
  • 1
    Exactly as @Pubby says. Otherwise you end up seeding with an identical seed several times because the time difference is too small. This will cause your random sequence to start at the exact same point in the pseudo-random sequence of numbers. – Marc Claesen May 18 '13 at 11:42
  • I tried to find the best one; some of the apparent duplicates are questions caused by not calling `srand()` at all. Possible duplicate of [Recommended way to initialize srand?](http://stackoverflow.com/questions/322938/recommended-way-to-initialize-srand) – Pascal Cuoq May 18 '13 at 11:45
  • rand()%1000 is not good practice, it doesn't provide uniform distribution. There is better alternative - arc4random_uniform. This is for Unix though – kotlomoy May 18 '13 at 13:00

4 Answers4

10

You should only call srand once: on program startup.

Right now, if you call your function multiple times before time changes your sequence will be the same.

Pubby
  • 51,882
  • 13
  • 139
  • 180
5

The lrand48() call tends to have a lot more state internally and a better pseudorandom number distribution.

However, note that you're reseeding with only 1-second granularity, so calls within the same second will generate the same sequence. Put your srand() call in main() or somewhere, once, instead of recalling it in getarray.

Alex North-Keys
  • 4,200
  • 1
  • 20
  • 22
4

You should investigate very carefully if rand() is the better function for the job.

It varies by compiler and platforms but it is often implmented as a "Linear congruential generator" which are very convenient in terms of speed and memory usage but have poor statistical properties (i.e. you can tell if a long enough sequence has been generated by congruential random generator or if it's truly random).

In your use case (testing algorithm's speed) may be perfectly fine to use rand() as long the execution is not influenced by the statistical properties of the data. If rand() is a linear congruential RNG, number sequences show a pattern which means that at any given time it is not true that all the numbers are equiprobable. A nice example is in this wikipedia picture:

LC NRG

Your system might also have a RNG (e.g. /dev/random) and its associated functions but be aware that those are meant to produce few high quality random numbers and may be pretty slow to use. You might even run out of numbers and end up waiting for the system to collect more enthropy!

A simple, pretty fast RNG with statistical properties good enough for cryptography is ISAAC. Personally I use it whenever I need decent random numbers.

Another alternative is to use true random numbers as those generated by RANDOM.org or HotBits but it may be overkill in your case.

As a side note, RANDOM.ORG has a nice page on RNG with another example of "patterns" created by the PHP rand() function

Remo.D
  • 16,122
  • 6
  • 43
  • 74
1

First, call the seed function once, not in a loop.

Second, I suggest you either :

1) Switch to the random(3) function 2) Pick something from rand48 / lrand48 3) Read the number of desired bytes for /dev/random yourself.

Solution 1) is easy and somewhat portable. 2 need a bit of thinking, 3 is the most work, and the least portable.

Igmar Palsenberg
  • 637
  • 4
  • 10