- Forum
- Windows Programming
- A chalenge in generating [REALY!] rando
A chalenge in generating [REALY!] random numbers
Hello everybody,
in a program i tried to use rand() function for generating random numbers , and in the end calculating PI with these. but result was that this function doesn't really generate random numbers with same possibility.
I used it in this way:
is there some way to generate better random numbers ?
How does srand(-) works ?
Cheers, Danial
in a program i tried to use rand() function for generating random numbers , and in the end calculating PI with these. but result was that this function doesn't really generate random numbers with same possibility.
I used it in this way:
|
|
is there some way to generate better random numbers ?
How does srand(-) works ?
Cheers, Danial
It's impossible to generate truely random numbers. All random numbers generated on any hardware (not quantum) is pseudo-random.
If you want some better algorthms then you can use something like the Boost Random library: http://www.boost.org/doc/libs/1_35_0
srand = Seed Random number generator
If you want some better algorthms then you can use something like the Boost Random library: http://www.boost.org/doc/libs/1_35_0
srand = Seed Random number generator
srand() just seeds the random number generator (although I really have no idea how the seed works, you could probably find something on google about it). And yes, there are better ways, a very good one being the Mersenne Twister:
http://en.wikipedia.org/wiki/Mersenne_twister
http://en.wikipedia.org/wiki/Mersenne_twister
Go get a lump of radioactive material with a custom Gieger counter that cycles through the alphabet at a fixed speed, and it pauses when it gets the radiation pulse. Then write that letter down (or number if you want).
@danyalji:
The standard C implementation of rand() implements a linear congruential random number generator. An LCRNG has the mathematical expression R(x+1) = ( c1 * R(x) + c2 ) mod p,
where c1 and c2 are carefully chosen constants, p is 2^32 for a 32-bit machine, R(x) refers to the xth random number and R(x+1) refers to the (x+1)st random number.
srand() sets R(0).
This random number generator generates every possible integer in the range [ 0.. 2^32 - 1 ] exactly once before the cycle repeats, which means that across the range [ 0..2^32 - 1] the RNG generates a perfect uniform distribution.
If you choose to use fewer bits in the random numbers -- for example, you want to generate only random numbers in the range [ 0..99 ] inclusive, then the following algorithm does contain bias:
int rn = rand() % 100;
The standard C implementation of rand() implements a linear congruential random number generator. An LCRNG has the mathematical expression R(x+1) = ( c1 * R(x) + c2 ) mod p,
where c1 and c2 are carefully chosen constants, p is 2^32 for a 32-bit machine, R(x) refers to the xth random number and R(x+1) refers to the (x+1)st random number.
srand() sets R(0).
This random number generator generates every possible integer in the range [ 0.. 2^32 - 1 ] exactly once before the cycle repeats, which means that across the range [ 0..2^32 - 1] the RNG generates a perfect uniform distribution.
If you choose to use fewer bits in the random numbers -- for example, you want to generate only random numbers in the range [ 0..99 ] inclusive, then the following algorithm does contain bias:
int rn = rand() % 100;
| quantum mechanics...Or radiation |
User inputs are considered random, and so is the noise on the PCI bus, for example. Look at the methods better operating systems use to generate truly random numbers or at least the entropy pool for their generation (and if you really want to argue that they are not truly random, I suggest that you come up with a method to predetermine them)
Your initial problem might be one of the following two: (a) you initialized the RNG before each call to rand(). Don't do this, initialize with srand() only once. (b) you used the numbers in more than one dimension (e.g. generating points (x,y) by calling (rand(), rand())). This might fail, either, since the numbers might be distributed uniformly in only one dimension (the points generated this way then are on hyperplanes in d+1 dimensions, in this case that would be lines). This might not be what you want. (The already mentioned Mersenne Twister generates random numbers uniformly distributed in 624 dimensions; and there are still better (and even simpler) methods around).
The perhaps biggest problem of all is that the standard doesn't say what exactly rand() shall do (the cycle length, the number of independent dimensions etc. aren't specified). So if you want reproducible results, you'll have to use another implementation (there are libraries around, and Knuth's vol. 2 covers the topic of the linear congruential method quite well). This is also a reason why you most likely don't want "real" random numbers: you won't be able to debug your algorithm if the sequence isn't reproducible. However, if you use a PRNG, all you have to do is store the initialization, then you get the same sequence again if required.
| As i got, u mean i need to make random function better... any other suggestion ? |
Read about it. You know, in books, articles and papers... (you might want to start with Knuth's vol. 2...). And, as already mentioned, the documentation of an OS entropy pool management. Another source for a not-so-in-depth version would be books on simulation; they usually discuss the topic of PRNGs briefly.
Oh, and being on the topic of really random numbers: I remember a device consisting of a web cam and a lava lamp...
1. Take a radio.
2. Turn the dial all the way up or all the way down.
3. Connect the line-out of the radio to the line-in of the computer.
4. Find some way to capture input from the line-in and do so.
5. ???
6. PROFIT!
2. Turn the dial all the way up or all the way down.
3. Connect the line-out of the radio to the line-in of the computer.
4. Find some way to capture input from the line-in and do so.
5. ???
6. PROFIT!
Topic archived. No new replies allowed.