Re: random number problem

From: Ricardo Gibert (nospamgibert_at_cox.net)
Date: 07/09/04 

Date: Fri, 9 Jul 2004 11:31:42 -0700

<Jens.Toerring@physik.fu-berlin.de> wrote in message news:2l845qF9e8jmU2@uni-berlin.de...
> copx <invalid@invalid.com> wrote:
>
> > <Jens.Toerring@physik.fu-berlin.de> schrieb im Newsbeitrag news:2l811pF9vdpkU1@uni-berlin.de...
> >> copx <invalid@invalid.com> wrote:
> >> > I need a routine that returns a random integer number
> >> > between A and B including A and B (r >= A && r <= B).
> >> > That would be simple but I've an additional requirement:
> >> > The chance of all possible return values must be equal.
> >>
> >> That's what typical random generators are meant for -
> >> they should return numbers uniformly distributed over
> >> the whole interval.
>
> > Of course the number created by the PRNG is uniformly distributed.
> > But to create a random_int(min,max) function I need to apply
> > some additional calculations. Most PRNGs I know return
> > a float between 0 and 1. IIRC to create a function like I need
> > you would do something like
>
> > random_int = (rand() * max) + min
>
> > And I think this additional step destroys the uniformity..
>
> Why should it do that? It's a simple linear transformation.
> If you have uniformly distributed points drawn on an elastic
> band and then stretch it they stay uniformly ditributed.
> And a simple multiplication does nothing else (and adding an
> offset doesn't change anything).

The linear transformation maps from one interval to another. If the smaller number of elements of the one interval does not divide
evenly into the larger number of elements of other, then there will necessarily be some bias. When the number of elements you map
onto is a great deal smaller, then the bias is small enough to be ignored. This is usually the case, but when it is not, this is
usually overlooked with poor results as a consequence.

...

Relevant Pages

  • Re: Strange cryptanalysis results using bad RNGs
    ... > - the bias due to the blocks being ASCII text is much greater than that ... > due to the PRNG; ... this is a less subtle statistical mistake than the mistake ...
    (sci.crypt)
  • Re: Choose k random lines from file
    ... > Suppose we have an unbiassed PRNG giving us numbers in the range ... > NOT have the potential for creating an infinite loop; ... That's a bias. ...
    (comp.programming)
  • Re: Random Number Generation -----> Hardware or Software?
    ... >> shorter periodic cycles. ... make the sequence random. ... A prng is nothing more than a _counter_. ... in the limit it becomes impossible to tell bias from 1/f noise. ...
    (comp.arch.embedded)
  • Re: N groups of random numbers with different ranges
    ... even with a good pseudo-random number generator. ... It seems to me that with a sufficiently good PRNG, ... Why should I ignore the introduction of bias? ... Ignoring the possible results of a gunshot wound it is not a bad idea to shoot yourself in the head. ...
    (comp.lang.c)
  • Re: Random Number Generation --> Hardware or Software?
    ... > cannot find bias in cryptographically strong PRNGs ... These the same crypto experts who bring us all these crackable ... A prng is just one more code. ... And I can't believe I agree with Macon. ...
    (comp.arch.embedded)