Sign in to follow this  
bentaberry

random not random enough for me - use sleep? and how?

Recommended Posts

bentaberry    100
Hi everyone, I am currently trying to code a binary search just to see how it works and ive not got to the actual stage of writing the binary search function but i did a test output of my sorted array and I realised that the random numbers are pretty rubbish. I am guessing this is because when i seed rand with the time and I create my array by using a "for" it creates the array so fast that you end up with lots of the same numbers. I figure I can fix this by adding sleep() inside the {} for the for statement but I cant figure out how to do it. What do I need to #include and how would i write the sleep()? I am using visual studio express 2008 just incase that changes anything. Kind Regards David

Share this post


Link to post
Share on other sites
Windryder    270
Perhaps you could use time + loop counter as a seed? For the first iteration this would just use the current time, but even if the time is the same (I'm assuming millisecond precision?) in the next iteration the loop counter will have increased.

EDIT: By the way, do you have a good reason to re-seed on every loop iteration?

Share this post


Link to post
Share on other sites
smc    292
Generally a function such as rand() should return a pseudo random sequence of numbers. This sequence is not dependent on time. I may be mistaken but the seed only serves as a factor in the sequence generation. Others on here can explain this in more detail.

I am not sure what function you are using, but the documentation should explain how it is generating the sequence.

Edit: Usually you will not seed the random function each time in a loop.

Share this post


Link to post
Share on other sites
Windryder    270
Quote:
Original post by smc
Generally a function such as rand() should return a pseudo random sequence of numbers. This sequence is not dependent on time. I may be mistaken but the seed only serves as a factor in the sequence. Others on here can explain this in more detail.


Time is quite often used as seed because it's easy. By using the current time as seed you can avoid the catch-22 situation where you need a random number to seed your PRNG. Thus, if the time value happens to be the same in two separate cases, the pseudo-random sequences will be identical (assuming there are no other variable factors involved in the process).

Share this post


Link to post
Share on other sites
Promethium    580
Seeding from the current time should not be an issue, unless you seed before every rand, which you shouldn't do. Seed once, at the beginning of your program and then just call rand whenever you need a new number. What does your loop look like?

Share this post


Link to post
Share on other sites
smc    292
Quote:
Original post by Windryder
Quote:
Original post by smc
Generally a function such as rand() should return a pseudo random sequence of numbers. This sequence is not dependent on time. I may be mistaken but the seed only serves as a factor in the sequence. Others on here can explain this in more detail.


Time is quite often used as seed because it's easy. By using the current time as seed you can avoid the catch-22 situation where you need a random number to seed your PRNG. :)


What I mean is the function itself is not dependent on time. Using time as a seed value is simply a scalar... it is an arbitrary number used by the function for the purposes of sequence generation.

In other words if I call for the next number at T=1, the value returned will be the same as if I had called for it a T=100. The sequence is predetermined.

It is entirely possible that a particular implementation is dependent on some timer function in which case I am wrong.

Share this post


Link to post
Share on other sites
flammable    280
answer to the actual question:


#include <windows.h>
Sleep(TimeToSleepInMilliSeconds);


Sleep at msdn

And I have a question with may lead to the cause of the problem.
Do you set the seed every time you need a random value (or every time inside the {} for the for statement)?
If so:
You must only set the seed once (or at least not every time you need a random value). Because srand sets the seed for the random algorithm (I don't know for sure if it's called a algorithm) but also resets it. What I mean is this:

srand(10);
rand() % 100 // = 45 (for example).
rand() % 100 // = 89
rand() % 100 // 2

srand(10);
rand() % 100 // = 45
srand(10);
rand() % 100 // = 45
srand(10);
rand() % 100 // = 45




I can't make up from your message if you do that but if so that is probably the cause of the problem.

[Edited by - flammable on February 8, 2010 8:19:18 AM]

Share this post


Link to post
Share on other sites
Windryder    270
Quote:
Original post by smc
[...]

In other words if I call for the next number at T=1, the value returned will be the same as if I had called for it a T=100. The sequence is predetermined.

It is entirely possible that a particular implementation is dependent on some timer function in which case I am wrong.


Yes, the sequence is determined the moment you call srand() or whatever function you use to seed your particular randomizer. All implementations I am aware of will produce the same sequence given the same seed. However, if I've understood the OP's problem correctly, it basically boils down to the fact that he re-seeds the randomizer repeatedly in a loop, but sometimes one loop iteration doesn't take long enough for the time value (which in the case of GetTickCount() has millisecond precision) to increase. This would, as you pointed out, result in the same sequence being generated twice.

Share this post


Link to post
Share on other sites
bentaberry    100
Thanks for responses guys I will look them over carefully to understand how the rand function works and see if it is the problem or not.

btw just to clear things up - I only seed rand once - i might have not worded that very well sorry. inside the for {} i have int var = rand();

Thanks for help again everyone.

Kind Regards
David

Share this post


Link to post
Share on other sites
bentaberry    100
Just to confirm guys by adding the sleep the randomness seems to be the same and just makes the program slower :)

I guess that just looking at the numbers in a sorted array skewed my way of thinking :)

Thanks again guys
David

Share this post


Link to post
Share on other sites
Wan    1366
Quote:
Original post by bentaberry
Just to confirm guys by adding the sleep the randomness seems to be the same and just makes the program slower :)

Well yes, that's what sleep does, it suspends the execution. [smile]

In case you really need to reseed every iteration, you might as well add some offset to the actual time:

int t = time();

for (int i = 0; i < 10; i++)
{
srand(t);
int r = rand();

t += 1000;
}

(pseudo-ish code)

Share this post


Link to post
Share on other sites
bentaberry    100
Quote:
Original post by SiCrane
What kind of criteria did you use to decide that the numbers weren't random enough?


I basically sorted the array from lowest to highest and then just used a "for" and output the sorted array element by element and it just had a lot of the same numbers.

a copy and paste of results from console:

test one:
0:1:2:4:5:8:12:13:13:14:15:16:16:18:18:19:20:20:20:20:20:21:21:22:23:24:25:25:28
:29:

test two:
0:3:3:4:5:5:5:6:6:8:9:11:13:13:14:14:14:15:16:16:18:19:19:22:22:22:27:27:28:28:

test three:
0:2:3:3:3:4:4:4:5:6:6:7:8:9:10:11:11:16:18:18:19:19:20:22:23:23:23:24:25:25:

i came to the conclusion purely based on the fact that I got a lot of numbers the same rather than a more unique list of elements. Is that a poor way of thinking or is there a more logical approach?

Kind Regards
David







Share this post


Link to post
Share on other sites
SiCrane    11839
No, that's a pretty poor test of randomness. In fact, if you got only one of every number that would be a sign of a bad random number generator.

Share this post


Link to post
Share on other sites
NickGravelyn    855
That's perfectly fine in a random situation. Think of it this way:

You roll one six-sided die. You have a 1/6 chance of getting any given number. You get a 4 on the first roll. You roll again. You get a 4. Roll again, another 4. Is your die broken? Possibly, but assuming it's a perfectly random roll, that's how randomness works.

That said, if you want random-but-different numbers, you'll need more logic. This is a common issue with the way people think of random numbers. For instance, some people figure asking for 100 numbers between 0-800 should have a relatively even distribution over that range, when in reality you are just as likely to get 100 1's as you are an evenly distributed set of numbers.

Share this post


Link to post
Share on other sites
bentaberry    100
Quote:
Original post by SiCrane
No, that's a pretty poor test of randomness. In fact, if you got only one of every number that would be a sign of a bad random number generator.


Yeah that makes sense :)

Thanks again
David

Share this post


Link to post
Share on other sites
alvaro    21266
Quote:
Original post by bentaberry
Quote:
Original post by SiCrane
What kind of criteria did you use to decide that the numbers weren't random enough?


I basically sorted the array from lowest to highest and then just used a "for" and output the sorted array element by element and it just had a lot of the same numbers.

[...]

i came to the conclusion purely based on the fact that I got a lot of numbers the same rather than a more unique list of elements. Is that a poor way of thinking or is there a more logical approach?


Oh, your thread should have been titled "I have poor intuitions for what random numbers look like" :) . Actually, this is a problem that most people have. If you ask people to write down thirty random numbers between 0 and 29, they would usually write many fewer repeats than they should.

Try to think of what property of your numbers seems suspicious to you, and I'll try to compute the probability of that happening. I bet it's much higher than you would expect.

Share this post


Link to post
Share on other sites
alvaro    21266
Quote:
Original post by yewbie
Couldn't you just seed it with time + i, i being the current iteration of your loop?


Seeding every time is just not a good idea. Pseudo-random number generators are designed to be seeded once and to then generate many numbers.

Share this post


Link to post
Share on other sites
kauna    2922

Quote:

srand(10);
rand() % 100 // = 45 (for example).
rand() % 100 // = 89
rand() % 100 // 2


Hi

I didn't see the actual code you use for generating the random numbers. Anyway, the code presented above has one problem with it and I was wondering if your code has a similar problem.

The code presented above won't give even distribution of numbers between 0 and 99. The reason for this is that the maximum random number generated is likely not divisible by 100.

The RAND_MAX value determines the maximum random number and it is usually something like 32767. If you mod that number by 100 the result is 67 which means that the 67 first numbers have increased probability of coming out from the randon number generator.

This may be a minor thing, but it can be proven by collecting statistics about the occurance of different numbers.

Cheers!

Share this post


Link to post
Share on other sites
alvaro    21266
If you want a better uniform distribution, discard any numbers that are larger than (RAND_MAX/100)*100.

int random_100() {
int r;
do {
r = std::rand();
} while(r>=((RAND_MAX/100)*100));
return r%100;
}



You may also want to use a better PRNG, like a Mersenne twister or something of that type.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this