I understand that the C specification does not give any specification about the specific implementation of rand(). What different algorithms are commonly used on different major platforms? How do they differ?
views:
1078answers:
5
+7
A:
See this article: http://en.wikipedia.org/wiki/List_of_random_number_generators
This is the source code of glibc's rand(): http://qa.coreboot.org/docs/libpayload/rand_8c_source.html
As you can see, it's a simple multiply with an addition and a shift. The values are carefully chosen to make sure that you get no repeat of the output for RAND_MAX iterations.
Aaron Digulla
2009-06-22 10:00:24
That's it? Surprisingly simple. Thanks muchly.
Azrael
2009-06-22 10:04:29
Yes, that's it, most general purpose PNRGs are surprisingly simple to implement. If you're looking for something more complex try the Mersenne Twister.
Jasper Bekkers
2009-06-22 10:12:39
Even MT19937 isn't exactly hard to implement.
Joey
2009-06-22 10:56:53
via @Tiemen below: @Aaron I can not comment but RAND_MAX is the highest possible value returned, not the number of iterations before repeating.
Jason Watkins
2009-06-22 21:45:37
@Jason: Any link for that? I was under the impression that there won't be a repeat for RAND_MAX calls (unless you change the seed, of course)
Aaron Digulla
2009-06-23 20:12:07
@Aaron: If that were the case, it wouldn't be a very good random number generator. What you'd have in that case is sampling without replacement.
Mike Daniels
2009-09-18 21:08:36
@Mike: rand() is not random but pseudo random, so the numbers aren't really random at all. IIRC, the values of the standard rand() are chosen to yield the maximum of iterations before a repeat.
Aaron Digulla
2009-09-21 07:33:26
Your http://qa.coreboot.org/docs/libpayload/rand_8c-source.html link doesn't work, you probably meant http://qa.coreboot.org/docs/libpayload/rand_8c_source.html .
Adrian
2010-07-09 03:54:55
@Adrian: Thanks, fixed!
Aaron Digulla
2010-07-09 09:59:41
+2
A:
You could use Boost Random library for different random number generators, if you need something specific, or more advanced.
The documentation of Boost Random is here.
Cătălin Pitiș
2009-06-22 10:04:40
A:
@Aaron I can not comment but RAND_MAX is the highest possible value returned, not the number of iterations before repeating.
Tiemen
2009-06-22 10:13:31
Yes, but I think he qualified his statement in a way that it's mostly true: The values are typically carefully chosen so that you don't get a repeat for (at most) RAND_MAX iterations.Sometimes, the cycles are smaller.IIRC, the rule of thumb is that RAND_MAX is ought to be co-prime with the other constants.
hythlodayr
2009-06-22 22:01:22
If I recall correctly, r=r*5+1 is such a beast. It cycles through all possible bit combinations, no matter how many bits you choose.
Nosredna
2009-06-22 23:33:49
+1
A:
The field of PRNGs (Pseudo Random Number Generators) is quite vast.
First of all you have to understand that without having an external input (usually physical) you can't get a real source of random numbers.. That's why these algorithms are called pseudo random: they usually use a seed to initialize a position in a very long sequence that seems random but it's not random at all.
One of the simplest algorithms is the Linear Congruential Generator (LCG), that has some costraints to guarantee a long sequence and it's not secure at all.
Another funny one (at least for the name) is the Blum Blum Shub Generator (BBS) that is unusual for normal PRNGs because it relies on exponentiation in modulo arithmetic giving a security comparable to other algorithms like RSA and El Gamal in breaking the sequence (also if I'm not sure about the proof of it)
Jack
2009-06-22 23:24:23