getting random numbers within a range
don
function to obtain numbers only between 0 and 51 for my array of cards......
I plan on swapping card[i] with say card[j]
Mike Larry
low=0;
low + ( high - low ) * ( rand() / RAND_MAX) ;
Does this help?
"don" <d...@panix.com> wrote in message
news:asmoc3$d8h$1...@reader1.panix.com...
Chris Ho-Stuart
> high = 51;
> low=0;
> low + ( high - low ) * ( rand() / RAND_MAX) ;
>
> Does this help?
No... because rand() is an integer, rand() / RAND_MAX will be zero.
To get a truly uniform distribution, you need to take random
numbers repeatedly until they are in some range 0..N-1 where N
is divisible by the upper bound of the required range.
Code in this post uses C.
/*
* Get a number uniformly distributed in range 0..bound-1;
*/
int BoundRand(int bound)
{
int r;
int limit;
int factor = (RAND_MAX - bound + 1) / bound;
factor++;
limit = factor * bound;
do {
r = rand();
}while ( r >= limit );
return r / factor;
}
/* Here is code I gave in another thread for dealing cards. */
/*
* Set the deck to be 0 1 2 3 4 ... size-1
* For a regular deck, size is 52.
*/
void SeedDeck(int Deck[], int size)
{
while ( --size >= 0 ) {
Deck[size] = size;
}
}
/*
* Deal(Deck, size, n) -- Deal a card.
*
* Deck is an array of "size" numbers (52 for a deck of cards)
* n is in the range 0..size-1
*
* Pick a number uniformly in range n..size-1,
* and swap what is in that position with position n.
*
* Return the card moved into position n.
*
* Essentially; assume the first n positions in the
* array have already been dealt, and deal the next one.
*/
int Deal(int Deck[], int size, int n)
{
int i = BoundRand(size-n)+n;
int c = Deck[i];
Deck[i] = Deck[n];
Deck[n] = c;
return c;
}
int main()
{
/*
* Deals several hands of 8 distinct digits,
* using the above routine.
*/
int Deck[52];
int a, b, c, i;
SeedDeck(Deck, 52);
/* Deal poker hands to four people, seven times. */
for(a = 0; a < 7; a ++) {
/* i counts the number of cards being dealt */
i = 0;
for(b = 0; b < 4; b++) {
for(c = 0; c < 5; c++) {
printf("%3d", Deal(Deck, 52, i++));
}
printf(b == 3 ? "\n" : ", ");
}
}
return 0;
}
André Pönitz
> I'm trying to shuffle a deck and I need to know how to use the rand()
> function to obtain numbers only between 0 and 51 for my array of cards......
rand() % 52 should yield more or less random numbers between 0 and 51.
But's probably better to use something like
j = int((52.0*rand())/RAND_MAX);
[And your original problem might be solvable in one line by using
std::random_shuffle from <algorithm>]
Andre'
--
Those who desire to give up Freedom in order to gain Security,
will not have, nor do they deserve, either one. (T. Jefferson)
CJ Bell
"Chris Ho-Stuart" <host...@sky.fit.qut.edu.au> wrote in message
news:3dee...@news.qut.edu.au...
> Mike Larry <mikel...@yahoo.com> wrote:
> > high = 51;
> > low=0;
> > low + ( high - low ) * ( rand() / RAND_MAX) ;
> >
> > Does this help?
>
> No... because rand() is an integer, rand() / RAND_MAX will be zero.
>
> To get a truly uniform distribution, you need to take random
> numbers repeatedly until they are in some range 0..N-1 where N
> is divisible by the upper bound of the required range.
> Code in this post uses C.
>
> /*
> * Get a number uniformly distributed in range 0..bound-1;
> */
Should the purpose really be to get a uniform distribution?
> int BoundRand(int bound)
> {
> int r;
> int limit;
> int factor = (RAND_MAX - bound + 1) / bound;
> factor++;
> limit = factor * bound;
> do {
> r = rand();
> }while ( r >= limit );
> return r / factor;
> }
I think it would be much more efficient & better to scale rand() instead of
waiting for a valid return value. Theoretically, it is possible that it will
take forever for a result to appear that is within range. That's assuming
the rand() is truly random, which it probably won't be. Since the
implementation of rand() may vary, though, it would be safer not to wait for
valid numbers -- just in case.
I would not suggest using "rand() % N", either, since it throws out the
higher bits -- I've heard the remaining lower bits are less random.
This would work:
const int high = 51;
const int low=0;
int RandVal = low + ( high - low ) * ( double(rand()) / RAND_MAX) ;
In practice, though, your method would probably work fine.
CJ Bell
Pete Becker
>
>
> because rand() is an integer, rand() / RAND_MAX will be zero.
>
Or one.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Andrew Koenig
CJ> instead of waiting for a valid return value.
More efficient, maybe. Better, no.
The trouble is that if you simply scale the result of rand(), some
values will be more likely than others. To see this, imagine a
machine on which 0 <= rand() < 32768, and imagine that you want a
final result n with 0 <= n < 30000. Scaling 32768 distinct values
into 30000 distinct values implies that 2768 of the possible output
values will be twice as likely as the others (or that one or more
possible output value will be three or more times as likely as one of
the others).
So if you want to do a good job of generating random numbers in a
given range, you have to discard values from rand() that are outside
an integral multiple of the number of values in the range.
--
Andrew Koenig, a...@research.att.com, http://www.research.att.com/info/ark
Andrew Koenig
André> j = int((52.0*rand())/RAND_MAX);
...except that if you do this, some results will be slightly more
likely than others. For more information, see the discussion starting
on page 135 of "Accelerated C++."
Alexander Terekhov
Andrew Koenig wrote:
>
> André> But's probably better to use something like
>
> André> j = int((52.0*rand())/RAND_MAX);
>
> ...except that if you do this, some results will be slightly more
> likely than others. For more information, see the discussion starting
> on page 135 of "Accelerated C++."
Do you have a link? ;-)
regards,
alexander.
Neil Cerutti
Well, the function given in the C++-FAQ-LITE is sort of similar
to the one in AC++.
Besides, "link" by itself, has no meaning on the internet. ;-)
--
Neil Cerutti <cer...@trans-video.net>
Alexander Terekhov
Neil Cerutti wrote:
>
> In article <3DEF7C12...@web.de>, Alexander Terekhov wrote:
> > Andrew Koenig wrote:
> >>
> >> André> But's probably better to use something like
> >>
> >> André> j = int((52.0*rand())/RAND_MAX);
> >>
> >> ...except that if you do this, some results will be slightly
> >> more likely than others. For more information, see the
> >> discussion starting on page 135 of "Accelerated C++."
> >
> > Do you have a link? ;-)
>
> Well, the function given in the C++-FAQ-LITE is sort of similar
> to the one in AC++.
I really have no idea what you're talking about, but the "right"
[well, almost] answer is this: < ;-) >
#include <stdio.h>
#include <stdlib.h>
const int CARDS = 52;
int main() {
unsigned long c[CARDS] = { 0 };
int cards = CARDS;
for ( ;; )
if ( 0 == c[static_cast< size_t >(CARDS * drand48())]++ &&
0 == --cards )
break;
do printf( "%2d: %lu\n", cards, c[cards++] ); while (CARDS-cards);
}
Or am I just missing and/or misunderstanding something?
regards,
alexander.
--
http://www.opengroup.org/onlinepubs/007904975/functions/drand48.html
Chris Ho-Stuart
> "Chris Ho-Stuart" <host...@sky.fit.qut.edu.au> wrote in message
> news:3dee...@news.qut.edu.au...
>> To get a truly uniform distribution, you need to take random
>> numbers repeatedly until they are in some range 0..N-1 where N
>> is divisible by the upper bound of the required range.
>> Code in this post uses C.
>>
>> /*
>> * Get a number uniformly distributed in range 0..bound-1;
>> */
>
> Should the purpose really be to get a uniform distribution?
Yes. Every possible result should be equiprobable.
>> int BoundRand(int bound)
>> {
>> int r;
>> int limit;
>> int factor = (RAND_MAX - bound + 1) / bound;
>> factor++;
>> limit = factor * bound;
>> do {
>> r = rand();
>> }while ( r >= limit );
>> return r / factor;
>> }
>
> I think it would be much more efficient & better to scale rand() instead of
> waiting for a valid return value. Theoretically, it is possible that it will
> take forever for a result to appear that is within range. That's assuming
> the rand() is truly random, which it probably won't be. Since the
> implementation of rand() may vary, though, it would be safer not to wait for
> valid numbers -- just in case.
Scaling rand does not address the problem. If you want a
uniform distribution, then you need to discard values, and
retain only a set of values, the size of which is a multiple
of the size of the sample set you are generating.
Waiting forever is not a problem. Really. It is like getting
a number in the range 1..5 using a fair dice. You roll, and keep
rolling until you get something that is not a six.
The vast majority of time the above loop will execute only
once. If the bound is 52, for example, and RAND_MAX is 32767,
then the limit is 32760.
This means that 1 in every 4096 calls, you will need to draw
a second number. And assuming indepedence (which in fact does
not hold for rand() in MS VC++!) you will need to draw three
random numbers 1 in every 16 million calls. If we assume true
randomness, and you run this function a million times a second
for a billion years, then I still claim with confidence that it
will never go around more than ten times. With a pseudo-random
number generator you can be even more confident.
> I would not suggest using "rand() % N", either, since it throws out the
> higher bits -- I've heard the remaining lower bits are less random.
>
> This would work:
>
> const int high = 51;
> const int low=0;
> int RandVal = low + ( high - low ) * ( double(rand()) / RAND_MAX) ;
This method has the non-uniform defect that I am trying to avoid,
and also has the defect that it can possibly give the value 52.
You need to divide by RAND_MAX+1.0
With the code you have given, and assuming RAND_MAX = 32767 as in
MS VC++, the numbers 0, 44, 29, 37, 14, 22 and 7 are slightly more
likely than other numbers, with 52 occuring once every 32768 calls.
The more frequent numbers are 0, 6, 13, 19, 26, 32, 39 and 45 when
the correction is applied.
Cheers -- Chris
Cy Edmunds
"Andrew Koenig" <a...@research.att.com> wrote in message
news:yu99ptsg...@europa.research.att.com...
You're right theoretically, but the OP wants to generate a number in the
range [0..51] and I'll bet he has a 32 bit computer. Most of us do. LOL I
think scaling would be adequate for what appears to be a card game.
Chris Ho-Stuart
Microsoft VC++ 6.0 has RAND_MAX equal to 32767.
Wierd, but true.
Cheers -- Chris
Cy Edmunds
I didn't know that. I haven't used rand() in many years because it has such
a bad history.
Jerry Coffin
says...
[ ... ]
> > const int high = 51;
> > const int low=0;
> > int RandVal = low + ( high - low ) * ( double(rand()) / RAND_MAX) ;
>
> This method has the non-uniform defect that I am trying to avoid,
> and also has the defect that it can possibly give the value 52.
> You need to divide by RAND_MAX+1.0
This has worked reasonably well for me for years:
int rand_lim(int limit) {
/* return a random number between 0 and limit inclusive.
*/
int divisor = RAND_MAX/(limit+1);
int retval;
do {
retval = rand() / divisor;
} while (retval > limit);
return retval;
}
The only problem it's ever caused was when I accidentally tried to
pass a limit greater than RAND_MAX. Integer division by zero didn't
accomplish much...
--
Later,
Jerry.
The universe is a figment of its own imagination.
Neil Cerutti
One of the exercises in _Accelerated C++_ is a charge to extend
that function to handle a limit argument greater than RAND_MAX.
I'm glad noboby got to see my solution.
Coping with overflow was a pain, and I found it quite difficult
to empirically show that my function actually worked.
--
Neil Cerutti <cer...@trans-video.net>