Home > algorithms, c programming language, python > Generate random numbers deterministically and non-deterministically

Generate random numbers deterministically and non-deterministically

Problem
I wanted to compare the efficiency of some sorting algorithms. For this, I wrote a simple program that accepts a command-line parameter (the name of a sorting algorithm) and calls the specified algorithm on a large array containing random integers. Using the Unix “time” command I could do my tests.

However, if the array is filled up with different random numbers each time, the tests wouldn’t be fair. Thus, the array should contain random numbers that are generated in a deterministic way, i.e. each time I execute my little program, the array should be filled with the same numbers in the same order.

Generate random numbers deterministically
C snippet:

int UPPER = 10;

for (i = 0; i < 10; ++i) {
    printf("%d ", (int)(random() % UPPER + 1));
}

Full source code is here.

Python snippet:

UPPER = 10
random.seed(0)  # use a constant seed

for _ in range(10):
    print random.randint(1, UPPER),

Full source code is here. Doc on random.seed is here.

Sample output:

$ ./det.py
4 7 8 6 4 6 7 3 10 2
$ ./det.py
4 7 8 6 4 6 7 3 10 2

Generate random numbers non-deterministically
Now let’s see how to generate random numbers non-deterministically.

Note that this method is still deterministic since it uses the current time as its seed. If someone knows the time when you launched your program, (s)he could reproduce your “random” numbers. As John von Neumann said: “Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.

C snippet:

int UPPER = 10;

srand((unsigned)time(NULL));   /* use current time as seed */

for (i = 0; i < 10; ++i) {
   printf("%d ", (int)(random() % UPPER + 1));
}

Full code is here.

Python snippet:

UPPER = 10

for _ in range(10):
    print random.randint(1, UPPER),

Full code is here.

Sample output:

$ ./non-det.py
2 4 4 10 6 9 4 3 2 7
$ ./non-det.py
5 8 10 2 10 10 1 10 4 5

Note
Notice the different behaviors of C and Python. By default, C uses the same seed, thus if you want “true randomness”, you must call srand. On the other hand, Python generates “true random” numbers by default and you must provide a constant seed if you want a determinsitic behavior.

Thanks to Temia E. for his (her?) help.

About these ads
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 72 other followers

%d bloggers like this: