Velocity Reviews > How can get random number in your range

# How can get random number in your range

bipi
Guest
Posts: n/a

 07-27-2007
Dear all,

I found function rand(), it can create random number but this function
can not define the range of number which I want to get it, such as, I
want to get random number in the range from 0 to 100 [0-100].

Many thanks,

jacob navia
Guest
Posts: n/a

 07-27-2007
bipi wrote:
> Dear all,
>
> I found function rand(), it can create random number but this function
> can not define the range of number which I want to get it, such as, I
> want to get random number in the range from 0 to 100 [0-100].
>
>
> Many thanks,
>

13.16: How can I get random integers in a certain range?

A: The obvious way,

rand() % N /* POOR */

(which tries to return numbers from 0 to N-1) is poor, because
the low-order bits of many random number generators are
distressingly *non*-random. (See question 13.18.) A better
method is something like

(int)((double)rand() / ((double)RAND_MAX + 1) * N)

If you're worried about using floating point, you could use

rand() / (RAND_MAX / N + 1)

Both methods obviously require knowing RAND_MAX (which ANSI
#defines in <stdlib.h>), and assume that N is much less than
RAND_MAX.

(Note, by the way, that RAND_MAX is a *constant* telling you
what the fixed range of the C library rand() function is. You
cannot set RAND_MAX to some other value, and there is no way of
requesting that rand() return numbers in some other range.)

If you're starting with a random number generator which returns
floating-point values between 0 and 1, all you have to do to get
integers from 0 to N-1 is multiply the output of that generator
by N.

References: K&R2 Sec. 7.8.7 p. 168; PCS Sec. 11 p. 172.

Peter J. Holzer
Guest
Posts: n/a

 07-27-2007
On 2007-07-27 09:38, bipi <(E-Mail Removed)> wrote:
> I found function rand(), it can create random number but this function
> can not define the range of number which I want to get it, such as, I
> want to get random number in the range from 0 to 100 [0-100].

See the FAQ, question 13.16.

hp

--
_ | Peter J. Holzer | I know I'd be respectful of a pirate
|_|_) | Sysadmin WSR | with an emu on his shoulder.
| | | http://www.velocityreviews.com/forums/(E-Mail Removed) |
__/ | http://www.hjp.at/ | -- Sam in "Freefall"

Ben Bacarisse
Guest
Posts: n/a

 07-27-2007
jacob navia <(E-Mail Removed)> writes:

> 13.16: How can I get random integers in a certain range?
>
> A: The obvious way,
>
> rand() % N /* POOR */
>
> (which tries to return numbers from 0 to N-1) is poor, because
> the low-order bits of many random number generators are
> distressingly *non*-random.

It may be worth adding to this FAQ entry. rand() % N is poor even in
some cases where the low-order bits are fine. If N does not divide
RAND_MAX + 1, there will be a bias towards the numbers between 0 and
RAND_MAX % N. The bias is small but grows as N gets closer to
RAND_MAX.

--
Ben.

Keith Thompson
Guest
Posts: n/a

 07-27-2007
jacob navia <(E-Mail Removed)> writes:
> bipi wrote:
>> Dear all,
>> I found function rand(), it can create random number but this
>> function
>> can not define the range of number which I want to get it, such as, I
>> want to get random number in the range from 0 to 100 [0-100].
>> Many thanks,
>>

>
> 13.16: How can I get random integers in a certain range?
>
> A: The obvious way,
>
> rand() % N /* POOR */
>
> (which tries to return numbers from 0 to N-1) is poor, because
> the low-order bits of many random number generators are

[snip]

jacob, thanks for making use of the FAQ, but surely it would be better
to provide a *pointer* to it rather than just quoting it. And you
forgot to mention what you were quoting, which fails to give credit to
the FAQ and its author and potentially denies the OP the opportunity
to read the rest of it (not that it's difficult to find).

When I cite the FAQ, I usually just provide the FAQ's URL
<http://www.c-faq.com/> and a question number (13.16 in this case).

Ben Bacarisse also made a good point about another problem with using
one result from rand() to generate one number is a specified range.
If there are, for example, 32768 possible results (RAND_MAX==32767),
and you want numbers in the range 0..99, you can't possibly produce a
uniform distribution, because 32768 is not a multiple of 100. In some
applications, the slight skew is acceptable. If it isn't, you can
reduce the range to 32700 possible values by rejecting any results in
the range 32700..32767, and map 327 distinct rand() results to each
value in the range 0..9. With a bit of work, the method can be
generalized to arbitrary ranges and arbitrary values of RAND_MAX, as
long as the desired range contains no more than RAND_MAX values. In
the very worst case, this will reject fewer than half of the values
returned by rand(), on average. This is random, of course, so you
might wait arbitrarily long for a valid result.

All this assumes that the rand() implementation is good enough that
all this work is worthwhile.

With some more arithmetic, I *think* there are ways to get a sequence
of results in a specified range from a sequence of results in
different specified range without rejecting anything. That's probably
more than the OP needs, though, and I'm too lazy to work it out.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Walter Roberson
Guest
Posts: n/a

 07-27-2007
In article <(E-Mail Removed)>,
Keith Thompson <(E-Mail Removed)> wrote:

>Ben Bacarisse also made a good point about another problem with using
>one result from rand() to generate one number is a specified range.
>If there are, for example, 32768 possible results (RAND_MAX==32767),
>and you want numbers in the range 0..99, you can't possibly produce a
>uniform distribution, because 32768 is not a multiple of 100.

couple of days ago,

"After that... find some power of 2 that is "just a bit" above a
multiple of r (minimize the difference between the power of 2
and the multiple), mask off that many bits from the returned
random number, then reject the result if it is in the upper portion
of the range (between the last full multiple and 2**N - 1)."

I didn't specifically speak of bias the way Ben did, but that
bias is the reason for the stated algorithm.
--
Okay, buzzwords only. Two syllables, tops. -- Laurie Anderson

Keith Thompson
Guest
Posts: n/a

 07-27-2007
http://www.velocityreviews.com/forums/(E-Mail Removed)-cnrc.gc.ca (Walter Roberson) writes:
> In article <(E-Mail Removed)>,
> Keith Thompson <(E-Mail Removed)> wrote:
>>Ben Bacarisse also made a good point about another problem with using
>>one result from rand() to generate one number is a specified range.
>>If there are, for example, 32768 possible results (RAND_MAX==32767),
>>and you want numbers in the range 0..99, you can't possibly produce a
>>uniform distribution, because 32768 is not a multiple of 100.

>
> couple of days ago,
>
> "After that... find some power of 2 that is "just a bit" above a
> multiple of r (minimize the difference between the power of 2
> and the multiple), mask off that many bits from the returned
> random number, then reject the result if it is in the upper portion
> of the range (between the last full multiple and 2**N - 1)."
>
> I didn't specifically speak of bias the way Ben did, but that
> bias is the reason for the stated algorithm.

I think for best effect (fewest rejected random numbers), you'd want
to miminize the *ratio* of the chosen power of 2 and a multiple of the
size of your range, not the difference.

Using a power of 2, I think, makes part of the operation quicker (you
can use bitwise operations rather than division), but I think that by
ignoring powers of 2 you can reject fewer of the input random numbers.

I think you can avoid rejecting *any* input random numbers at the
expense of some fairly heavy calculations. For example, if your
desired range has 100 elements, you can treat a sequence of, say, 1000
16-bit numbers as a single, very large, base-100 number, and grab one
"digit" at a time. Generalizing this to arbitrarily long sequences is
likely to require operations on arbitrarily large integer (bignums),
and will be worthwhile only if the input random numbers are
*extremely* expensive, or if you absolutely can't afford to reject too
many in a row. But for such an application, it would probably be much
easier to write your own random number generator in the first place.

If RAND_MAX+1 is a multiple of the number of elements in your desired
range, all these problems go away.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Army1987
Guest
Posts: n/a

 08-01-2007
On Fri, 27 Jul 2007 16:46:46 +0100, Ben Bacarisse wrote:

> jacob navia <(E-Mail Removed)> writes:
>
> <FAQ on random numbers asked>
>
>> 13.16: How can I get random integers in a certain range?
>>
>> A: The obvious way,
>>
>> rand() % N /* POOR */
>>
>> (which tries to return numbers from 0 to N-1) is poor, because
>> the low-order bits of many random number generators are
>> distressingly *non*-random.

>
> It may be worth adding to this FAQ entry. rand() % N is poor even in
> some cases where the low-order bits are fine. If N does not divide
> RAND_MAX + 1, there will be a bias towards the numbers between 0 and
> RAND_MAX % N. The bias is small but grows as N gets closer to
> RAND_MAX.

This is already pointed out in the Web version of the FAQ.
http://www.c-faq.com/lib/randrange.html
Also, if N is very small, if it isn't a divisor of RAND_MAX + 1,
then RAND_MAX % N is better than if it is a divisor of it.
For example, RAND_MAX % 2 alternates in some RNG, but RAND_MAX % 3
uses all of the bits, so it is less predictable.
--
Army1987 (Replace "NOSPAM" with "email")
"Never attribute to malice that which can be adequately explained
by stupidity." -- R. J. Hanlon (?)

Ben Bacarisse
Guest
Posts: n/a

 08-01-2007
Army1987 <(E-Mail Removed)> writes:

> On Fri, 27 Jul 2007 16:46:46 +0100, Ben Bacarisse wrote:
>
>> jacob navia <(E-Mail Removed)> writes:
>>
>> <FAQ on random numbers asked>
>>
>>> 13.16: How can I get random integers in a certain range?
>>>
>>> A: The obvious way,
>>>
>>> rand() % N /* POOR */
>>>
>>> (which tries to return numbers from 0 to N-1) is poor, because
>>> the low-order bits of many random number generators are
>>> distressingly *non*-random.

>>
>> It may be worth adding to this FAQ entry. rand() % N is poor even in
>> some cases where the low-order bits are fine. If N does not divide
>> RAND_MAX + 1, there will be a bias towards the numbers between 0 and
>> RAND_MAX % N. The bias is small but grows as N gets closer to
>> RAND_MAX.

> This is already pointed out in the Web version of the FAQ.
> http://www.c-faq.com/lib/randrange.html

I can't find it. I am happy to assume it is me and leave it at that.
It is not a major issue, so if it is covered somewhere, that is more

--
Ben.

Keith Thompson
Guest
Posts: n/a

 08-01-2007
Ben Bacarisse <(E-Mail Removed)> writes:
> Army1987 <(E-Mail Removed)> writes:
>
>> On Fri, 27 Jul 2007 16:46:46 +0100, Ben Bacarisse wrote:
>>
>>> jacob navia <(E-Mail Removed)> writes:
>>>
>>> <FAQ on random numbers asked>
>>>
>>>> 13.16: How can I get random integers in a certain range?
>>>>
>>>> A: The obvious way,
>>>>
>>>> rand() % N /* POOR */
>>>>
>>>> (which tries to return numbers from 0 to N-1) is poor, because
>>>> the low-order bits of many random number generators are
>>>> distressingly *non*-random.
>>>
>>> It may be worth adding to this FAQ entry. rand() % N is poor even in
>>> some cases where the low-order bits are fine. If N does not divide
>>> RAND_MAX + 1, there will be a bias towards the numbers between 0 and
>>> RAND_MAX % N. The bias is small but grows as N gets closer to
>>> RAND_MAX.

>> This is already pointed out in the Web version of the FAQ.
>> http://www.c-faq.com/lib/randrange.html

>
> I can't find it. I am happy to assume it is me and leave it at that.
> It is not a major issue, so if it is covered somewhere, that is more

It's covered in the cited web page (which is question 13.16 of the FAQ):

When N is close to RAND_MAX, and if the range of the random number
generator is not a multiple of N (i.e. if (RAND_MAX+1) % N != 0),
all of these methods break down: some outputs occur more often
than others. (Using floating point does not help; the problem is
that rand returns RAND_MAX+1 distinct values, which cannot always
be evenly divvied up into N buckets.) If this is a problem, about
the only thing you can do is to call rand multiple times,

unsigned int x = (RAND_MAX + 1u) / N;
unsigned int y = x * N;
unsigned int r;
do {
r = rand();
} while(r >= y);
return r / x;

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"