4

Is there any literature available on the periodicity of the random number generator in gcc's g++ (if we don't re-seed the function)? I suppose I could run tests myself, but it would be better to have access to well-verified research.

Thanks in advance for your help.

// EDIT

I just wanted to add that I have searched quite a bit, with multiple engines, but I have not found anything specific. I have only read general comments about the periodicity being limited by the number of bits needed to represent the seed. (So I guess that given the fact that srand is usually called with time, the periodicity can be no more than 10^12 or so. But something more definite would be very helpful before I start implementing my algorithms.)

wallyk
  • 56,922
  • 16
  • 83
  • 148
Shredderroy
  • 2,860
  • 2
  • 29
  • 53
  • 3
    If you mean `rand`/`srand`: that's not part of GCC, but of the OS/C library. – Fred Foo Jun 11 '11 at 19:07
  • @larsman That may or may not be the case. And GCC provides an implementation of the C library. –  Jun 11 '11 at 19:09
  • 1
    @Neil: You sure? [Gcc](http://gcc.gnu.org/) and [glibc](http://www.gnu.org/s/libc/) are different projects on the GNU tree, and gcc works just fine with other libc's. Certainly they are intended to go together, and generally ship together, but that is not quite the same as being a single project or product. – dmckee --- ex-moderator kitten Jun 11 '11 at 19:15
  • @dmckee I meant what you just said :-) –  Jun 11 '11 at 19:17
  • 3
    "They generally ship together" -- except on zillions of Macs where BSD libc is used. – Fred Foo Jun 11 '11 at 19:19
  • 2
    ... and on MS Windows, where cygwin gcc uses `newlib`, and Neil himself taught me that mingw gcc uses MSVCRT.DLL which comes with the OS. – Ben Voigt Jun 11 '11 at 19:24
  • @laersmans: Granted, granted. And I should know it, as I'm typing on one of those. But I'll weasel out by noting that there are still more linux boxes. Yeah, that's it! – dmckee --- ex-moderator kitten Jun 11 '11 at 19:24
  • 1
    "They generally ship together"...on Linux...Others have cited Windows and MacOS and BSD; I'll add HP-UX, Solaris, and AIX as other platforms where GCC does not generally ship with glibc. – Jonathan Leffler Jun 11 '11 at 20:43
  • `srand/rand` are indeed a part of the C standard library, and as has been mentioned elsewhere, *never use them*. At best they are just bad. Some implementations are beyond bad. Alternatives abound. Boost, and now C++11, has a Mersenne twister, which is extremely good. Also available on many machines is the rand48 family. Not as good as MT, but still very good. Even random/srandom is better than rand/srand. – David Hammen Jun 11 '11 at 21:37

2 Answers2

4

The srand/rand functions are a bit broken. As you are using C++, I strongly recommend you use the boost random number library. It's a header-only library, so you don't need to build anything. There's an example of how to use it here.

Community
  • 1
  • 1
4

When searching in the rand(3) man page, I found this:

The versions of rand() and srand() in the Linux C Library use the same random number generator as random() and srandom()

so I had a look at the random(3) man page, and here is your answer:

The period of this random number generator is very large, approximately 16*((2**31)-1)

This can be quite useful for pedagogic purposes, since you want to develop your own PRNG. However, I would discourage you to use this PRNG when developing an application. You should prefer one of the Boost.Random's implementation as suggested @Neil Butterworth (MT19937 is a good default PRNG, sufficient for most of the applications).

Finally, if you intend to learn more about PRNGs, I would suggest you to read these two scientific articles, that well survey PRNGs.

Practical distribution of random streams for stochastic High Performance Computing, David RC Hill, in International Conference on High Performance Computing and Simulation (HPCS), 2010

Pseudorandom number generators, Pierre L'Ecuyer, in Encyclopedia of Quantitative Finance Encyclopedia of Quantitative Finance, 2008

jopasserat
  • 5,721
  • 4
  • 31
  • 50
  • 1
    The chapter on random number generation from Numerical Recipes **3rd edition** is also worth reading, and quite up to date (eg. it doesn't advocate Mersenne Twister). – Alexandre C. Jun 12 '11 at 16:43
  • I do agree with you, and I could also have added Knuth's *The art of computer programming*, Vol 2. However, the 2 papers I cited in my answer are shorter and refer to these two books. – jopasserat Jun 12 '11 at 17:02
  • Thank you very much, jHackTheRipper! – Shredderroy Jun 12 '11 at 19:33