Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > How can get random number in your range

Reply
Thread Tools

How can get random number in your range

 
 
websnarf@gmail.com
Guest
Posts: n/a
 
      08-02-2007
On Jul 27, 3:07 am, "Peter J. Holzer" <(E-Mail Removed)> wrote:
> 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.


The FAQ is deceptive and incomplete on this issue (and what the hell
is drand48?). You can get a better explanation here:

http://www.pobox.com/~qed/random.html

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      08-02-2007
Keith Thompson <(E-Mail Removed)> writes:

> Ben Bacarisse <(E-Mail Removed)> writes:
>> Army1987 <(E-Mail Removed)> writes:

<snip>
>>> 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
>> than adequate.

>
> It's covered in the cited web page (which is question 13.16 of the FAQ):
>
> When N is close to RAND_MAX,...


So it is. Must pay more attention.

--
Ben.
 
Reply With Quote
 
 
 
 
Keith Thompson
Guest
Posts: n/a
 
      08-02-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) writes:
> On Jul 27, 3:07 am, "Peter J. Holzer" <(E-Mail Removed)> wrote:
>> 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.

>
> The FAQ is deceptive and incomplete on this issue


How so?

> (and what the hell
> is drand48?).


That's answered in question 13.21, which question 13.16 directly
refers to.

> You can get a better explanation here:
>
> http://www.pobox.com/~qed/random.html


You raise 3 major points on that page.

1. If the desired range does not divide the range of values returned
by rand() a bias is introduced. FAQ 13.16 directly addresses that.

2. The quality of rand() is often not very good. FAQ 13.16 also
directly addresses that.

3. There are problems if the desired range is wider than RAND_MAX. I
think that's a valid criticism, though it certainly doesn't justify
using the word "deceptive". (And in this particular context, the OP
wanted range of 0..100, and RAND_MAX is guaranteed to be at least
32767.)

Your page appears to contain a lot of good information, and I hope to
have the time to read the whole thing at some point, but it's probably
more than would be appropriate for the clc FAQ. Adding a pointer to
your page to the "additional links" page
<http://www.c-faq.com/lib/sd15.html> might be a good idea.

Perhaps the FAQ has been updated since the last time you read it?

--
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"
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      08-02-2007
Keith Thompson wrote:
>

.... snip ...
>
> 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,
> discarding certain values:
>
> unsigned int x = (RAND_MAX + 1u) / N;
> unsigned int y = x * N;
> unsigned int r;
> do {
> r = rand();
> } while(r >= y);
> return r / x;


However people should be aware that some RNGs will never return the
value 0. If this is so, and it is probably not documented, then
you need some additional constructs to ensure even handed
operation.

The lack of a zero is the result of a shift algorithm, which will
lock up on the value 0.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
cbfalconer at maineline dot net



--
Posted via a free Usenet account from http://www.teranews.com

 
Reply With Quote
 
websnarf@gmail.com
Guest
Posts: n/a
 
      08-02-2007
On Aug 1, 6:18 pm, Keith Thompson <(E-Mail Removed)> wrote:
> (E-Mail Removed) writes:
> > On Jul 27, 3:07 am, "Peter J. Holzer" <(E-Mail Removed)> wrote:
> >> 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.

>
> > The FAQ is deceptive and incomplete on this issue

>
> How so?


It gives an "answer", that is insufficient, and accompanied by
incorrect explanations.

> > (and what the hell
> > is drand48?).

>
> That's answered in question 13.21, which question 13.16 directly
> refers to.


Right, and its off topic for this newsgroup, right? I mean, what is
it even doing in the FAQ?

> > You can get a better explanation here:

>
> > http://www.pobox.com/~qed/random.html

>
> You raise 3 major points on that page.
>
> 1. If the desired range does not divide the range of values returned
> by rand() a bias is introduced. FAQ 13.16 directly addresses that.


The FAQ suggests that if the range is small enough, then you are ok.
This is untrue if accuracy is required, regardless of of what the
range is. Specifically, if you take 1000 * (RAND_MAX / RANGE)
samples, you will see a statistically significant deviation from the
samples from the techniques they suggest and from a proper evenly
distributed random sample. This is tantamount to the FAQ saying
"don't sample this too much". On modern machines, given that RAND_MAX
is commonly 32767, that number of samples is going to pretty much
always be "smallish".

> 2. The quality of rand() is often not very good. FAQ 13.16 also
> directly addresses that.


It addresses the wrong things. In order to get more bits out of it,
you have to call it a successive number of times, however, rand()
implementations with too small of a state cannot produce all possible
permutations of successive calls -- in fact successive calls are
typically deterministic after 32 bits are output. For this reason, to
be ideal, you need to use a PRNG that has a large enough state (such
as the Mersenne Twister) to avoid this issue.

If you know anything about computer graphics; using a small state
rand() successively is like using (stochastic) dithering for images,
while using a large state rand() is like having truly higher
resolution. Having the higher resolution is generally better than
dithering which is basically trying to gloss over the fundamental
weakness of having lower resolution.

> 3. There are problems if the desired range is wider than RAND_MAX. I
> think that's a valid criticism, though it certainly doesn't justify
> using the word "deceptive".


It said there are problems if N is close to RAND_MAX (they should
point out that its devastatingly wrong if RAND_MAX > N > RAND_MAX/2),
which includes N being slightly larger than RAND_MAX. If it said "if
N approaches RAND_MAX from below" or something like that you could
almost forgive them, but they didn't.

> [...] (And in this particular context, the OP wanted range of 0..100,
> and RAND_MAX is guaranteed to be at least 32767.)


Give a man a fish vs teaching him to fish ...

> Your page appears to contain a lot of good information, and I hope to
> have the time to read the whole thing at some point, but it's probably
> more than would be appropriate for the clc FAQ.


Well the FAQ could simply give my implementation of randbiased () and
randrange () (the two together are not prohibitively long) and say
that why it works is an exercise to the reader, or point to my page
about it.

> [...] Adding a pointer to
> your page to the "additional links" page
> <http://www.c-faq.com/lib/sd15.html> might be a good idea.


Looks like more half-answer kind of things going on in there. It kind
of reminds me of being forced to vote for the democratic nominee or
the republican nominee instead of the candidate you actually want for
the office.

Sometimes the right answer matters.

> Perhaps the FAQ has been updated since the last time you read it?


It was, but insufficiently.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

 
Reply With Quote
 
Ernie Wright
Guest
Posts: n/a
 
      08-02-2007
(E-Mail Removed) wrote:

> If you know anything about computer graphics; using a small state
> rand() successively is like using (stochastic) dithering for images,
> while using a large state rand() is like having truly higher
> resolution. Having the higher resolution is generally better than
> dithering which is basically trying to gloss over the fundamental
> weakness of having lower resolution.


<ot>
I know something about graphics, and this analogy misses the mark.

Higher resolution with uniform samples is like a bad PRNG with lots of
bits. Stochastic sampling at lower resolution is like a good PRNG with
fewer bits. Uniform sampling produces aliasing; higher resolution just
changes the artifact wavelengths. Stochastic sampling randomizes (!)
the unavoidable error of discrete sampling, trading aliasing for much
less visually objectionable noise.

They aren't mutually exclusive, either. Just like you'd want your PRNG
with lots of bits to be good, you can stochastically sample at high
resolution. But for CG, if I have to choose, I'll take sampling quality
over raw resolution.

See

http://graphics.pixar.com/StochasticSampling/paper.pdf

So I think you need a different analogy.
</ot>

- Ernie http://home.comcast.net/~erniew
 
Reply With Quote
 
David Thompson
Guest
Posts: n/a
 
      08-26-2007
On Fri, 27 Jul 2007 13:49:04 -0700, Keith Thompson <(E-Mail Removed)>
wrote:
<snip>
> 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.
>

This is a recurring topic on sci.crypt, where it is sometimes applied
to _true_ random sources (which can be expensive, at least in time) as
well as PRNGs.

IIRC the final outcome of the most recent round of discussions was to
immediately use (uniformly) values below the highest exact multiple of
R not over RAND_RANGE, as you noted upthread, and use 'rejected'
values over that as base RAND_RANGE-N*R digits collected into an
auxiliary accumulator, from which a value is taken when the
digits=entropy in it get up to R and any overflow reused similarly.

Unfortunately that group has been under a massive hipcrime attack for
about two months now, which may make finding any useful information
difficult, unless gooja has done an atypically good job of filtering.

- formerly david.thompson1 || achar(64) || worldnet.att.net
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Math.random() and Math.round(Math.random()) and Math.floor(Math.random()*2) VK Javascript 15 05-02-2010 03:43 PM
How do I get a random number between two random numbers? Alex Untitled Ruby 11 11-16-2009 09:45 AM
random.random(), random not defined!? globalrev Python 4 04-20-2008 08:12 AM
get random number in range [10..50] Roman Mashak C Programming 14 08-24-2006 03:38 AM



Advertisments