How do I generate a random intager in C++?
Also could I set the number to be in a certain range, such as between 0 and 25.
Printable View
How do I generate a random intager in C++?
Also could I set the number to be in a certain range, such as between 0 and 25.
faq.
Hi there,
#include<cstdlilb>
int random;
random = 1 + rand() % 25;
will generate random numbers in the range of 1 to 25.
But these will be fairly predictable numbers.
#include <ctime>
#include <cstdlib>
srand(time(0) ); //uses clock to seed the random number
dice1 = 1 + rand() % 6;
more random- uses clock seconds to seed.
Hope this helps.
Ok thanks
A better seed:
Code:1 #include <iostream>
2
3 extern "C" {
4 #include <time.h>
5 }
6
7 int main(int argc,char* argv[])
8 {
9 struct timespec seed;
10 for (int i=0;i<=10;++i) {
11 clock_gettime(CLOCK_REALTIME,&seed);
12 srand(seed.tv_sec+seed.tv_nsec);
13 std::cout<<rand()%10000<<std::endl;
14 }
15
16 return 0;
17 }
>struct timespec seed;
>clock_gettime(CLOCK_REALTIME,&seed);
Neither of these are standard. A good, portable method still uses the current time, but instead uses a pseudo-hash of the bytes in a time_t value:
You would use it like this:Code:/*
Based off of Ben Pfaff's implementation that was based off
of Lawrence Kirby's implementation. :-)
*/
#include <cstddef>
#include <ctime>
#include <limits>
unsigned
time_seed()
{
time_t timeval; /* Current time. */
unsigned char *ptr; /* Type punned pointed into timeval. */
unsigned seed; /* Generated seed. */
size_t i;
timeval = std::time(0);
ptr = reinterpret_cast<unsigned char *>(&timeval);
seed = 0;
for (i = 0; i < sizeof timeval; i++) {
seed = seed * (std::numeric_limits<unsigned char>::max() + 2U) + ptr[i];
}
return seed;
}
>std::cout<<rand()%10000<<std::endl;Code:std::srand(time_seed());
Using the low order bits of a random number may not result in a good distribution. I've seen long strings of repeating numbers when using modulus with rand. A better way would be to divide by RAND_MAX. Here's a nifty function to do that:
Code:#include <cstdlib>
#include <iostream>
double
random()
{
return static_cast<double>(std::rand()) / RAND_MAX;
}
int
main()
{
std::srand(time_seed());
for (int i = 0; i < 10; i++) {
std::cout<< static_cast<int>(random() * 10) <<std::endl;
}
}
Wait a minute. Assume, for sake of simplicity, that RAND_MAX is 10,000 (I know that that isn't the real value of RAND_MAX) and that rand() returns a value between 0 and RAND_MAX. Division of the return value by RAND_MAX will result in values ranging from 1 to 0.0001. The number of times 0 appears in the first placeholder to the right of the decimal has to be greater than the number of times any other digit appears in that spot given that 0 is in that spot for all numbers less than 0.1, which is well over half of all the possible values obtainable by division of RAND_MAX. Multiplication of that value by 10 will promote the first digit to the right of the decimal to integer status, meaning the probability of having 0 as the final result of (rand()/RAND_MAX) * 10 has to be over 50%, too. Therefore the chance of having a string of zeros as a result of that process should be significantly higher than a string of any given digit using a modulus with a constant (other than 1). Or am I missing something here? (Wouldn't be the first time.)
1) The range of numbers is 0 to 1 when using the divison method.
2) Every RAND_MAX I've seen is odd. I'm fairly confident this is by design to avoid problems such as above.
But that begs the argument (argument here being my side of the debate, not speaking in anger) as posed.
Well really it could be a lot less than .0001 since you are storing it into a double. In set notation it would look like [0,1].
If RAND_MAX was 10000 then yes you could have problems. However that is completely outside the bounds of what is. Values I've seen used for RAND_MAX:
16383
32767
65535
2147483647
Notice a pattern here?
>for all numbers less than 0.1, which is well over half of all the possible values obtainable by division of RAND_MAX.
Why do you say well over half? I would say 1/10, or 10%.
No, I didn't think so.Quote:
Originally Posted by Prelude
Thanks for that extra information. =)
swoopy---Thanks for getting me to think through the problem from a different angle and therefore helping me see the error of my initial logic. You are correct. I am wrong.
If rand() returns a value from 0 to RAND_MAX and RAND_MAX is defined as 10000 then you can generate a table as follows:
0/10000 = 0
1/10000 = 0.0001
10/10000 = 0.001
100/10000 = 0.01
1000/10000 = 0.1
2000/10000 = 0.2
3000/10000 = 0.3
Therefore there are 1000 possible values of rand(), 0 to 999, that will give results less than 0.1, or 10% of all possible values of rand(). Likewise there are 1000 possible values of rand(), 1000 to 1999, that will give end results 0.1 to < 0.2 which is 10%, and similar for 0.2 to 0.3, etc. The same logic should hold for any value assigned to RAND_MAX. Now Preludes code makes sense.
Thank you.
Elad, both you and Prelude are much more logical thinkers than myself. For the part of your quote I posted, I thought maybe I had interpreted it wrong, so wanted some clarification from you. It's fun to learn new things from threads of this nature.
It's understandable why dividing by RAND_MAX gives an even distribution, but it's unclear why modulus doesn't. However since Prelude has explained this before, I was aware modulus was to be avoided.
swoopy, I'm not sure why Preludes indicates that rand()/RAND_MAX is less likely to give a string of equal values on repeated values than rand()/modulus, either; but it clearly isn't the reason I initially came up with, as you pointed out. Maybe the problem is I'm misinterpretting what Prelude wrote in the first place.
The problem is/was in the random number generator. The low order bits (which modulus uses) tend/tended to be far less random than the higher order bits (which division by RAND_MAX uses). It's basically a hack to get around the limitations of rand, a function that doesn't require the algorithm to be good. :)Quote:
Originally Posted by elad
I'm sure there are more curtains to get to the genie on this one. Maybe it will lead to realms really unintelligible by us mortals, instead of just flirting on the fringes like this one, but I can't help from trying to turn the next curtain to see what's there.
Prelude--So, to try to restate your answer to see if I can even come close to understanding it: rand() uses one protocol to generate the high order bits of the number it returns and second protocol to generate the lower order bits of the number it generates. The former protocol tends to generate more random results than does the latter. That seems fair enough. Now the part that's confusing me. Are you saying that modulus uses a protocol to generate it's results and it makes use of a different set of bits in the divisor and modulant(?sp) than the bits used by division (by RAND_MAX)? Doesn't modulus use division on the entire number, like I do, to get the result it returns? And, for that matter, doesn't division use all the digits (bits, whatever) of the dividend and divisor to generate it's answer, too? I've had to deal with enough black boxes in my days, so if you say, "yes, and trust me on this, you don't want to go there", I will. But at the moment I'm curious to see what's behind the next curtain.
There are good algorithms and bad algorithms. The bad algorithms are typically linear congruential generators because good constants are hard to find. The problem is that the low order bits of the random number returned tend to repeat more often than the high order bits.Quote:
Originally Posted by elad
The desired effect of modulus for rand() % N is to reduce the value returned by rand to the range of [0..N-1) by calculating the remainder of division by N. The division effectively shifts the high bits of the value into nothingness until the value is within the requested range:
Now, when the low order bits repeat often then a value of N in rand() % N that's a power of two will use those exact bits as the reduced value. For example, if N = 2 and the lowest bit is 0, 1 and 0 for a given sequence of three, the final value will be 0, 1 and 0, respectively. If the lowest bit repeats infinitely between 0 and 1 (a situation that does happen as I'll show in a moment) then the random numbers of rand() % 2 will not be random. They'll switch between 0 and 1 giving sequences of 0,1,0,1,0,1,0,1,...Code:#include <iostream>
#include <cstdlib>
using namespace std;
void bits(unsigned int val);
int
main()
{
int i = RAND_MAX;
while (i) {
bits(i /= 2); // The definition of bits is in a later example
cout<<endl;
}
}
Why division works instead of modulus is a little more complicated. When you divide a number returned by rand by RAND_MAX in floating-point context, the result is a number between 0 and 1 with the pseudo-randomness in the precision, but no obvious repetition in the value (exercise: Why? :)). Then by multiplying by N, you force the value into the range you desire by effectively shifting the values left into integral range. The effect is the same even for values of N that are powers of 2.
The following code is an example program that prints the repeating values of modulus using a poor linear congruential generator with the bits (lowest order to highest order) of the unchanged random number followed by the pseudo-random values of division without modulus and the bits of the original value. The code also describes another way to use the high order bits without casting to double. (exercise: How does it work?):
Code:#include <iostream>
#include <limits>
using namespace std;
namespace {
const int RAND_INT_MAX = numeric_limits<unsigned short>::max();
}
void bits(unsigned int val);
int rand_int(unsigned int& seed);
int
main()
{
unsigned int seed1 = 1;
unsigned int seed2 = 1;
int base = 2;
for (int i = 0; i < 20; i++) {
int r1 = rand_int(seed1);
int r2 = rand_int(seed2);
cout<< r1 % base <<':';
bits(r1);
cout<<'\t'<< r2 / (RAND_INT_MAX / base + 1) <<':';
bits(r2);
cout<<endl;
}
}
void
bits(
unsigned int val
)
{
int bits = numeric_limits<char>::digits + 1;
int int_bits = sizeof(unsigned short) * bits;
for (int i = 0; i < int_bits; i++) {
cout<< !!(val & 1);
val >>= 1;
}
}
int
rand_int(unsigned int& seed)
{
seed = seed * 1103515245 + 12345;
return seed % (RAND_INT_MAX + 1);
}
>>The bad algorithms are typically linear congruential generators because good constants are hard to find.
I knew there was a technical explanation in there somewhere! To me this sounds as otherworldly as when I use a phrase like "Gastrointestinal dysfunction due to Dibothriocephalous is mainly due to altered peristalsis." It can sure be interesting when someone explains the inner workings of something, however. Thanks.
I'll have to play with the bit shifting stuff later. Not my favorite pastime and not something I can do during idle moments at work, but I'll give it a shot later.
Another problem with using % is that some numbers, such as 6 in the case of a dice game, are not divisible into RAND_MAX+1 (the number of possible return values from rand() ). This means the distribution of numers returned will not be even. If you're hoping for 6's as often as 1's, then forget it. Is this significant to worry about? Perhaps not... but if you had money riding on it, you would care.
The best random number generator I have found is the Mersenne Twister. It has a period of 2^19937-1, and you can seed it with any number of bits. This means there are more than 2^32 possible unique sequences to be generated, as is the case with a 32-bit seed. I am using it in my current project, and it works well.
>I don't understant why rand() is PSEUDO-number generator,
Because it is not really random. The numbers produced are deterministic, in that the same sequences can be repeated given knowledge of the seed used to start the generator.
With sufficient knowledge, future outputs from a pseudo-random generator can be predicted, and given that they are predictable, they cannot be random.
However, for most purposes, the ability to produce numbers which appear to be random is sufficient.
During lab time for my ASM class we had an interesting converstation about this. We came to the realization that nothing is random. We thought long and hard and even went so far as to look at electron and molecular movement and we still couldn't find a truely random event. As such there must not be a way to generate a truely random set of numbers :)
Give me the same random number generator and the same starting seed as you use, and I can tell you what numbers will appear when. Imagine if a VLT used such a method, and you found out how it generated numbers? Sometimes knowing the actual generator and seed is not important - if the next number generated uses only the last number as a seed, then the maximum period of such a generator is limited to the number of different numbers the variable holding this number/seed can store. It may even be shorter. This means you could predict future events just by looking at the numbers themselves.Quote:
Originally Posted by C+++C_forever
>ok thanks , but how are they predictable?
Given a sufficiently large list of numbers from a pseudo random generator, it is possible to predict what is coming next without explicit knowledge of the algorithm or the seed. I believe this can be done by plotting the values in 'attractor space'.
>i mean, how could this function be implemented so that it gives predictable results?
Any deterministic random number generator is predictable, i.e. rand(). There are devices which you can plug into your computer in order to generate non-deterministic random numbers. I understand that these devices used either radioactive decay or background radio noise as the source of the random number generation.
Take a look at this site:Quote:
Originally Posted by Davros
http://www.lavarnd.org/
That would be a very simple one that doesn't work well, but, yes, that is the general idea (it should also store the new result back into seed, however). It is a formula that uses the last number generated (which is the seed if none have been generated, yet) to produce a new value.Quote:
Originally Posted by C+++C_forever
Here is a simple one I made very quickly, in a matter of minutes, a while back to temporarily take the place of an improved generater that would be implemented later:
Notice that m_value computes a new value from itself and stores it to itself.Code:// Note: _rotl and _rotr are OS specific
// The decimal constants are prime numbers.
// The hexadecimal constants are meant to have a somewhat similar number of 1's and 0's in binary.
m_value = ((m_value * 5653 ^ _rotl(m_value,12)) + 710459 * _rotr(m_value,13) + 0xB82A4D7E ) ^
((m_value * 148157 ^ _rotl(m_value,23)) + 15881 * _rotr(m_value, 7) + 0x82F54EC5 )
+ 0xC85B4A18; // using 0xC85B4A19 here repeats MUCH more quickly
For a much better, and much more complicated, implementation of a random number generator, take a look at the Mersenne Twister page I linked to above.
>Take a look at this site:
http://www.lavarnd.org/
The LavaCan is Interesting. However, I recall seeing tiny devices which plug into the RS232 port and cost around $20 from RS Components.
One of my math professors kept a book called "The List of Random Numbers". The entire book (some 400 pages) was a chart of random numbers. I guess it didn't occur to the writer that once the numbers were ordered, they were no longer random. Must have been pretty simple to write the book. I'm pretty sure most of the people that frequent this board could write a program to write a sequel for it in under 20 minutes.Quote:
Originally Posted by Thantos
The book's contents may be truly random numbers, like those obtained by throwing dice, rather than pseudo random numbers generated by a computer. Basically, one set can be reproduced exactly, the other can not. I would assume a book would use a set that can not. I think that they would still be classified as random numbers, as you can start anywhere in the book, and as long as you don't already have the list memorized, you cannot determine which number will appear next - just like the die.
And even if we live in a deterministic universe, it would be very difficult to set up the environment - the entire universe - exactly as before to achieve the same results. In fact, we would not even realize that we were repeating the experiment as we would all have the same thoughts and memories as the first time.
If you need a 'better' random number on windows check out CryptGenRandom().
Quote:
CryptGenRandom documentation
The data produced by this function is cryptographically random. It is far more random than the data generated by the typical random number generator such as the one shipped with your C compiler.
This function is often used to generate random initialization vectors and salt values.
Software random number generators work in fundamentally the same way. They start with a random number, known as the seed, and then use an algorithm to generate a pseudo-random sequence of bits based on it. The most difficult part of this process is to get a seed that is truly random. This is usually based on user input latency, or the jitter from one or more hardware components.
With Microsoft CSPs, CryptGenRandom uses the same random number generator used by other security components. This allows numerous processes to contribute to a system-wide seed. CryptoAPI stores an intermediate random seed with every user. To form the seed for the random number generator, a calling application supplies bits it might have—for instance, mouse or keyboard timing input—that are then added to both the stored seed and various system data and user data such as the process ID and thread ID, the system clock, the system time, the system counter, memory status, free disk clusters, the hashed user environment block. This result is SHA-1 hashed, and the output is used to seed an RC4 stream, which is then used as the random stream and used to update the stored seed. If an application has access to a good random source, it can fill the pbBuffer buffer with some random data before calling CryptGenRandom. The CSP then uses this data to further randomize its internal seed. It is acceptable to omit the step of initializing the pbBuffer buffer before calling CryptGenRandom.
Hi, sorry if I'm asking a dumb question (having looked through the FAQ/boards etc), but here goes:
I need to generate a list of numbers from 1 (to a set number, for e.g. 25) in a random order. However, I can't have the same number twice, but I need the list ordering to be random.
ANy thoughts?
Have an array that will store the numbers, a variable that will tell you how many items are in the array, and a temporary variable that will hold the result of each random call.
Process would be:
1) call the random generator and put value into the temporary variable
2) Search the array (using the above mentioned variable to make sure you only look at values you've put in already).
3) If you didn't find a match, add in the temp and increase the size counter. Repeat until filled
Search an array for each new random number? Even not taking into account duplicate values, this is a terribly inefficient process. IMO it's much better to just fill an array with the range of values and permute it randomly:Quote:
Originally Posted by Thantos
Code:#include <algorithm>
#include <cstdlib>
#include <iostream>
using namespace std;
double random();
int
main()
{
int *vals;
int n;
cout<<"Upper limit: ";
if (!(cin>> n)) {
cerr<<"Input error"<<endl;
exit(EXIT_FAILURE);
}
// Make and fill array
vals = new int[n];
for (int i = 0; i < n; i++) {
vals[i] = i + 1;
}
// Random permutation
for (int i = 0; i < n - 1; i++) {
int x = static_cast<int>(random() * (n - i));
swap(vals[i], vals[i + x]);
}
// Prove that it works and clean up
for (int i = 0; i < n; i++) {
cout<< vals[i] <<endl;
}
delete [] vals;
}
double
random()
{
return static_cast<double>(std::rand()) / RAND_MAX;
}
But what if you only wanted 20 numbers with a max value of 10000?
And I wasn't going for efficiently but ease of use and understanding for the questioner :)
>But what if you only wanted 20 numbers with a max value of 10000?
Then I would use a more suitable data structure than a simple array. ;) But that wasn't the question. The question was a list of numbers from 1 to N in random order.
>And I wasn't going for efficiently but ease of use and understanding for the questioner :)Quote:
I need to generate a list of numbers from 1 (to a set number, for e.g. 25) in a random order.
I know, but I can't resist giving you a hard time every now and then. It keeps you on your toes. ;)
Quote:
I'm not sure why Preludes indicates that rand()/RAND_MAX is less likely to give a string of equal values on repeated values than rand()/modulus
From what I see, Prelude is not talking about repeating values, but about the random distribution.Quote:
Using the low order bits of a random number may not result in a good distribution. I've seen long strings of repeating numbers when using modulus with rand.
Her argument is that dividing by RAND_MAX conserves this distribution, while the modulo method often does not.
The easiest way is this:Quote:
Originally Posted by weirdbeardmt
1. create the list storing 1..25, in order, in the indices 0..24
2. loop through the indicies, i = 0..24, pick a random index, j = 0..24, and swap the two.
This way, you swap a random index with each position, assuring that each index is swapped out at least once.
hmm... I did not see before posting that this thread was already several pages in length.
Anyway...
Well, they are deterministic :DQuote:
Any deterministic random number generator is predictable, i.e. rand().
Incidentally, Hotbits at fourmilab.ch provides such a generator, online.Quote:
There are devices which you can plug into your computer in order to generate non-deterministic random numbers.
For a pseudo-random number generator, I tend to use the Mersenne Twister, with a particular C++ implementation by Rick Wagner.
The problem with rand()%n using only the lower order bits is only a problem when n is a power of two.
Thus, the problem with rand()%n is not that much of a problem.
If you write rand()%3, the higher-order bits should also be taken into consideration.
Am I not correct, Prelude?
I have made an encryption program that uses noise from the microphone compressed with MD5 to generate keys of many megabits.Quote:
There are devices which you can plug into your computer in order to generate non-deterministic random numbers.
http://www.strandmark.com/otp.shtml
I think that this is still a problem, since they arent always "taken into consideration" evenly.Quote:
The problem with rand()%n using only the lower order bits is only a problem when n is a power of two.
Thus, the problem with rand()%n is not that much of a problem.
If you write rand()%3, the higher-order bits should also be taken into consideration.
>Am I not correct, Prelude?
Yes, the problem is most obvious when N is a power of 2.
Bah must have misread the question :)
Sure pick an easy target (large feet)Quote:
I know, but I can't resist giving you a hard time every now and then. It keeps you on your toes
What do you guys make of these nag routines which my dept. provides as a default install?
http://www.iss.soton.ac.uk/manuals/a...c/summary.html (about half way down for Random Number generators). I've used the equivalent in Fortran, but never in C...