rand() chooses the same number after several trials

K

kkirtac

Hello, i m using the standard rand() function to generate several
random numbers. Even if i seed the generator before the loop
"srand( (unsigned)time( NULL ) );" , it usually selects a previously
selected number in the process, after 6-7 iterations, i want the
sequence to be unique..should i consider some further modifications in
the code to achieve my goal maybe ? here is the piece of code..

vector<int> rands ;
int rnd ; //random number
srand( (unsigned)time( NULL ) );
int range_max = 165, range_min = 0 ;
for( int i = 0; i < 15 ; i++ )
{
rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
range_min;
rands.push_back(rnd);
}

it usually chooses a previously selected random number after 7-8
iterations, not all the time but usually..

Regards,
 
Z

zacariaz

Hello, i m using the standard rand() function to generate several
random numbers. Even if i seed the generator before the loop
"srand( (unsigned)time( NULL ) );" , it usually selects a previously
selected number in the process, after 6-7 iterations, i want the
sequence to be unique..should i consider some further modifications in
the code to achieve my goal maybe ? here is the piece of code..

vector<int> rands ;
int rnd ; //random number
srand( (unsigned)time( NULL ) );
int range_max = 165, range_min = 0 ;
for( int i = 0; i < 15 ; i++ )
{
rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
range_min;
rands.push_back(rnd);

}

it usually chooses a previously selected random number after 7-8
iterations, not all the time but usually..

Regards,

nomatter what you do it will allways be psudo random. By using complex
math and stuff you can it seem like it isnt, but it is. there are
other options though. Ive heard of people experimenting with geneating
random numbers by the help of the soundcard static and simular, but
really i dont think that is a god option. Allso there are devices that
you can plug into your computer which generates truly random number.
My favorite so far is: http://random.irb.hr/
however it relys on you having got a internet conenction.
 
P

Philip Potter

Abdo said:
Why not use:
rnd = range_min + rand() % rang_max;
instead? I think it's much clearer and you gain some performance by omitting
the extra multiplication, don't know why some use the style you're using
though.

Because the lower bits of a PRNG are often much less random than the higher
bits. See the comp.lang.c FAQ, question 13.16:
http://c-faq.com/lib/randrange.html

The OP's code is better quality under such conditions.
 
P

Philip Potter

kkirtac said:
Hello, i m using the standard rand() function to generate several
random numbers. Even if i seed the generator before the loop
"srand( (unsigned)time( NULL ) );" , it usually selects a previously
selected number in the process, after 6-7 iterations, i want the
sequence to be unique..should i consider some further modifications in
the code to achieve my goal maybe ? here is the piece of code..

vector<int> rands ;
int rnd ; //random number
srand( (unsigned)time( NULL ) );
int range_max = 165, range_min = 0 ;
for( int i = 0; i < 15 ; i++ )
{
rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
range_min;
rands.push_back(rnd);
}

it usually chooses a previously selected random number after 7-8
iterations, not all the time but usually..

Even with a perfect random number generator, this may well happen, due to a
thing called the "birthday paradox":
http://en.wikipedia.org/wiki/Birthday_paradox

This states (in terms applicable here) that given 23 numbers randomly chosen
from the range [1,365] it is more likely than not that they will be nonunique.
IOW, given 23 random people, it is more likely than not that two share a birthday.

In your case, given a perfect rand() the probability that 8 numbers will be
unique in the range [1,165] is 80.1%. That's more likely than not, but about 1
time in 5 you'll have collisions.

You should modify your code to prevent collisions entirely if you wish to avoid
them entirely. This is comp.lang.c FAQ question 13.19; see http://c-faq.com/ for
details.

Phil
 
A

Abdo Haji-Ali

kkirtac said:
Hello, i m using the standard rand() function to generate several
random numbers. Even if i seed the generator before the loop
"srand( (unsigned)time( NULL ) );" , it usually selects a previously
selected number in the process, after 6-7 iterations, i want the
sequence to be unique..should i consider some further modifications in
the code to achieve my goal maybe ?
Yes... rand() generate pseudorandom numbers, but it doesn't guarantee those
numbers to be unique.
Consider when generating a random number between 0 and 1 (i.e. only 0 or 1),
it wouldn't be so random then if I got a 0 then 1 then 0 then 1
(alternatively)
You need to check that you didn't push the generated number in 'rands'
before; if that's the case you should generate another random number and
pray it will be different :)
Or you could search the internet for a better "shuffling" algorithm.
rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
range_min;
Why not use:
rnd = range_min + rand() % rang_max;
instead? I think it's much clearer and you gain some performance by omitting
the extra multiplication, don't know why some use the style you're using
though.

Hope that helps,
 
D

Daniel T.

kkirtac said:
Hello, i m using the standard rand() function to generate several
random numbers. Even if i seed the generator before the loop
"srand( (unsigned)time( NULL ) );" , it usually selects a previously
selected number in the process, after 6-7 iterations, i want the
sequence to be unique..should i consider some further modifications in
the code to achieve my goal maybe ? here is the piece of code..

vector<int> rands ;
int rnd ; //random number
srand( (unsigned)time( NULL ) );
int range_max = 165, range_min = 0 ;
for( int i = 0; i < 15 ; i++ )
{
rnd = (double)rand() / (RAND_MAX + 1) * (range_max-1 -range_min) +
range_min;

Why the (RAND_MAX + 1)? On my system that is equal to INT_MIN. Why
(range_max - 1 - range_min)? That doesn't seem right either.
rands.push_back(rnd);
}

You should do your multiplies first, otherwise you loose precession. Try
this instead:

rnd = (double)rand() * (range_max - range_min) / RAND_MAX + range_min;
 
P

Philip Potter

Daniel said:
Why the (RAND_MAX + 1)? On my system that is equal to INT_MIN. Why

Ooh, nice catch, I didn't spot that.
(range_max - 1 - range_min)? That doesn't seem right either.

I think the OP maybe meant (range_max + 1 - range_min), because this is the
number of values in the range [range_min,range_max] including both endpoints.
You should do your multiplies first, otherwise you loose precession. Try
this instead:

rnd = (double)rand() * (range_max - range_min) / RAND_MAX + range_min;

For integers, divides lose precision while multiplies retain perfect accuracy.
For floats, they both lose about the same precision and order doesn't matter. If
you're using floating point the right line is probably:

rnd = (double)rand() / ((double)RAND_MAX + 1) * (range_max - range_min + 1) +
range_min;

But someone will probably see a bug in my code too, even though I'm just copying
from the clc FAQ.
 
P

Pete Becker

Yes... rand() generate pseudorandom numbers, but it doesn't guarantee those
numbers to be unique.

And if the numbers were guaranteed to be unique, they would not be random.
 
P

Pete Becker

Hello, i m using the standard rand() function to generate several
random numbers. Even if i seed the generator before the loop
"srand( (unsigned)time( NULL ) );" , it usually selects a previously
selected number in the process, after 6-7 iterations, i want the
sequence to be unique..should i consider some further modifications in
the code to achieve my goal maybe ? here is the piece of code..

Yes, that's how random numbers work. If you never got a duplicate value
until all the values in the range had been returned, the values would
not be random. (That's why casino operators get so upset with card
counters) To generate a sequence of unique values, look at the
algorithm std::random_shuffle.
 
B

BobR

kkirtac said:
Hello, i m using the standard rand() function to generate several
random numbers. Even if i seed the generator before the loop
"srand( (unsigned)time( NULL ) );" , it usually selects a previously
selected number in the process, after 6-7 iterations, i want the
sequence to be unique..should i consider some further modifications in
the code to achieve my goal maybe ? here is the piece of code..

vector<int> rands ;

If you want 'unique', try a std::set:

std::set<int> rands ; // #include <set>

while( 15 > rands.size() ){
rands.insert( ( int( std::rand() ) % 165 ) );
} // while()
 
J

Jerry Coffin

[ ... ]
You should do your multiplies first, otherwise you loose precession. Try
this instead:

rnd = (double)rand() * (range_max - range_min) / RAND_MAX + range_min;

This still has a problem: it produces skewed output (some values occur
more often than others) unless the range evenly divides the range of the
original generator. Many generators use a prime number as their range,
in which case this can never happen, so the result is always skewed.

You can avoid this (and floating point math as well) pretty easily:

#include <stdlib.h>

int rand_lim(int limit) {
int divisor = RAND_MAX/(limit+1);
int retval;

do {
retval = rand() / divisor;
} while (retval > limit);

return retval;
}

int rand_lim(int lower, int upper) {
int range = abs(upper-lower);

return rand_lim(range) + lower;
}
 
K

kkirtac

Hmm, thanks for all sugestions, so i change the topic a little, what
kind of implementation would you suggest for building a perfectly
unique sequence. For instance, i will choose a random element from a
sequence, and save it and then maybe delete it from the original
sequence to prevent drawing it again in the next selection..but just
deleting it wont help i think..if i delete, say "3" from the original
sequence, the size will decrease by 1, but how can i tell the compiler
not to draw "3" again ?

Regards,
 
?

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=

Hmm, thanks for all sugestions, so i change the topic a little, what
kind of implementation would you suggest for building a perfectly
unique sequence. For instance, i will choose a random element from a
sequence, and save it and then maybe delete it from the original
sequence to prevent drawing it again in the next selection..but just
deleting it wont help i think..if i delete, say "3" from the original
sequence, the size will decrease by 1, but how can i tell the compiler
not to draw "3" again ?

Save each number you've drawn already in a separate container and check
if it's in the container when you draw a new number. If it is just draw
a new number until you get a unique one.
 
O

osmium

kkirtac said:
Hmm, thanks for all sugestions, so i change the topic a little, what
kind of implementation would you suggest for building a perfectly
unique sequence. For instance, i will choose a random element from a
sequence, and save it and then maybe delete it from the original
sequence to prevent drawing it again in the next selection..but just
deleting it wont help i think..if i delete, say "3" from the original
sequence, the size will decrease by 1, but how can i tell the compiler
not to draw "3" again ?

I think there are only two ways, and the best way depends on how many
numbers you expect to want, call it n. If n is smallish, say a few hundred,
use shuffle which has been mentioned. If n is larger, keep track of what
has already been used and if it is a repeat, throw it away and keep drawing
numbers until you find an acceptable number..
 
K

kkirtac

Save each number you've drawn already in a separate container and check
if it's in the container when you draw a new number. If it is just draw
a new number until you get a unique one.

Thank you very much Erik for the nice idea,
I think there are only two ways, and the best way depends on how many
numbers you expect to want, call it n. If n is smallish, say a few hundred,
use shuffle which has been mentioned. If n is larger, keep track of what
has already been used and if it is a repeat, throw it away and keep drawing
numbers until you find an acceptable number..

and yes, i use both shuffle and Erik's algorithm, thank you too
osmium .
 
J

Jerry Coffin

I think there are only two ways, and the best way depends on how many
numbers you expect to want, call it n. If n is smallish, say a few hundred,
use shuffle which has been mentioned. If n is larger, keep track of what
has already been used and if it is a repeat, throw it away and keep drawing
numbers until you find an acceptable number..

There is at least one more designed by Robert Floyd. It's covered quite
nicely in "A Sample of Brilliance", an old "Programming Pearls" column.
It's reprinted as column 13 in "More Programming Pearls", but Jon
Bentley, ISBN 0-201-11889-0.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top