5

Possible Duplicate:
Generating random numbers effectively

I need to generate random numbers in my C++ application. I know from reading these two articles --

http://www.cprogramming.com/tutorial/random.html

write a c function that generates one random number, or a pair of random numbers, or a triplet of random numbers given the particular ranges

-- that random numbers can be generated using srand() and rand() but in both cases the current time according to the system clock is used as a seed. But I read in the first article that rand() will create the same random numbers if the seed is the same. So if two different users ran my application at the same time then they would have the same random numbers. Which would be pointless because I need the random numbers to be unique for the most part. (I know they cant be truly 100% unique if they are generated randomly)

So my question is can I create a random seed not based on system time and if so how, why does rand() produce the same numbers with the same seed and is there a way to make rand() produce different numbers with the same seed, or is there any other way to generate random numbers?

Community
  • 1
  • 1
John Vulconshinz
  • 1,088
  • 4
  • 12
  • 29
  • 3
    It's not clear what your requirements are or what your platform is. For example, on most x86 platforms, you can get a time measurement to the billionth of a second (from the TSC) making the chance that two users will run your program at the same time effectively zero. (The exact answer to your question will depend a lot on your exact requirements and your platform.) – David Schwartz Sep 30 '12 at 16:18
  • 4
    You cam't generate truly random numbers without an external noise source - the best you can do is pseudorandom numbers. – Paul R Sep 30 '12 at 16:22
  • 1
    [Kolmogorov complexity](http://en.wikipedia.org/wiki/Kolmogorov_complexity) is not computable. – ely Sep 30 '12 at 16:25
  • You can always use one of the better options in the `` header. – chris Sep 30 '12 at 16:25
  • @DavidSchwartz Is the function time() that precise or would I need to use something else? and to answer your question I am writing the application on a x86(Linux). – John Vulconshinz Sep 30 '12 at 18:14
  • @JohnVulconshinz: `time` is only to the second. So that's not what you want to use for precision time. – David Schwartz Oct 01 '12 at 05:50

4 Answers4

8

Without using special hardware (and even then, it's debatable), there is no such thing as a truly random number generated by a computer.

That being said; your only problem is: how do you generate your seeds such that two programs will not generate the same number. Using the current time as part of your seed is reasonable, but as you understand, it's not enough because two programs could generate their seed at the same time... so you need to augment your seed based on something that will be unique between the programs. Possibilities include process ID (which will differ if both programs are on the same computer), hardware mac address (which will differ if both programs are on different computers), or timing how long it takes the user to perform some task (which will generally differ as long as the user is human, not automation).

mah
  • 39,056
  • 9
  • 76
  • 93
  • Are process IDs (on Windows/Linux) generated from a formula or something else? and thank you for the quick response. – John Vulconshinz Sep 30 '12 at 18:04
  • Process IDs are fairly linear in their creation on most systems (though this is system dependent, and eventually their direct linearity isn't possible due to conflict / reuse). However if you are using the pid as part of a hash as @David Schwartz suggests, it will cause your seed to vary significantly from one pid to the next one even when they are close together. – mah Sep 30 '12 at 18:07
3

Depending on your exact requirements, your solution might be as simple this:

struct timeval;
gettimeofday(&time, NULL);
srand(hash3(time.tv_sec, time.tv_usec, getpid()));

You can use any three integer hashing function, such as this one:

unsigned int hash3(unsigned int h1, unsigned int h2, unsigned int h3)
{
    return ((h1 * 2654435789U) + h2) * 2654435789U) + h3;
}
David Schwartz
  • 179,497
  • 17
  • 214
  • 278
2

In addition of other answers, on Linux (and some other Unix) systems, you could read a few bytes from the /dev/random or /dev/urandom pseudo-device (at least to seed your PNRG). Read also carefully the random(4) man page (which also explains the important difference between /dev/random and /dev/urandom)

If coding for the latest C++2011 standard (and not the previous ones), you could be interested by its <random> header. Then use a very recent GCC compiler (e.g. 4.7) and libstdc++ library

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
0

It's not possible to implement a truly random number generator, but there are many nice pseudo-random function implementations that might help you:

  1. Boost.Random: http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random.html
  2. The C++11 <random> header file: http://www.cplusplus.com/reference/std/random/
  3. The C <stdlib.h> header file which includes the rand() function: http://www.cplusplus.com/reference/clibrary/cstdlib/rand/
PointerToConstantChar
  • 146
  • 1
  • 10
Rontogiannis Aristofanis
  • 8,883
  • 8
  • 41
  • 58