Liinear distribution of random numbers?

Discussion in 'C Programming' started by petertwocakes, Jan 17, 2009.

  1. Hi

    Is there a way of creating a distribution of random numbers (using
    random() or any otherwise) that approximates:

    frequency = N-x (0<=x<=N)

    or

    frequency = N/(x+1) (0<=x<=N)


    Thanks

    Steve
    petertwocakes, Jan 17, 2009
    #1
    1. Advertising

  2. petertwocakes

    geo Guest

    On Jan 17, 7:16 am, petertwocakes <>
    wrote:
    > Is there a  way of creating a distribution  of random numbers (using
    > random() or any otherwise) that approximates:
    > frequency = N-x (0<=x<=N)
    > or
    > frequency = N/(x+1)  (0<=x<=N)
    > Thanks
    > Steve


    Perhaps the fastest way to generate
    such variates with exactly those (scaled)
    frequencies---and with specific C programs---may
    be found in a web-available article:
    "Fast Generation of Discrete Random Variables",
    Marsaglia, Tsang and Wang,
    www.jstatsoft.org/v11/i03/paper
    geo, Jan 17, 2009
    #2
    1. Advertising

  3. "Malcolm McLean" <> writes:

    > "petertwocakes" <> wrote in message news:
    >> Hi
    >>
    >> Is there a way of creating a distribution of random numbers (using
    >> random() or any otherwise) that approximates:
    >>
    >> frequency = N-x (0<=x<=N)
    >>
    >> or
    >>
    >> frequency = N/(x+1) (0<=x<=N)
    >>

    >
    > generate a uniform random number on 0-1 by
    >
    > rand()/(RAND_MAX + 1.0)
    >
    > Then log transform it
    >
    > x = (int) (log(uniform() * (e-1) + 1.0) * N)


    .... and you hope the C implementer of rand() has not joined your
    campaign for 64 bit ints! :)

    --
    Ben.
    Ben Bacarisse, Jan 17, 2009
    #3
  4. On 17 Jan, 13:24, geo <> wrote:
    > On Jan 17, 7:16 am, petertwocakes <>
    > wrote:
    >
    > > Is there a  way of creating a distribution  of random numbers (using
    > > random() or any otherwise) that approximates:
    > > frequency = N-x (0<=x<=N)
    > > or
    > > frequency = N/(x+1)  (0<=x<=N)
    > > Thanks
    > > Steve

    >
    > Perhaps the fastest way to generate
    > such variates with exactly those (scaled)
    > frequencies---and with specific C programs---may
    > be found in a web-available article:
    > "Fast Generation of Discrete Random Variables",
    >  Marsaglia, Tsang and Wang,www.jstatsoft.org/v11/i03/paper


    Thanks, interesting read.
    petertwocakes, Jan 17, 2009
    #4
  5. On 17 Jan, 13:50, "Malcolm McLean" <> wrote:
    > "petertwocakes" <> wrote in message news:
    > > Hi

    >
    > > Is there a  way of creating a distribution  of random numbers (using
    > > random() or any otherwise) that approximates:

    >
    > > frequency = N-x (0<=x<=N)

    >
    > > or

    >
    > > frequency = N/(x+1)  (0<=x<=N)

    >
    > generate a uniform random number on 0-1 by
    >
    > rand()/(RAND_MAX + 1.0)
    >
    > Then log transform it
    >
    > x = (int) (log(uniform()  * (e-1) + 1.0) * N)
    >
    > (e is Euler's number to put your random number into the range 0-N-1).
    >
    > You can also square root transform it, or use a cosine transform.
    >
    > I am not sure what the best approximation to a linearly increasing density
    > function actually is. If you do several thousand of them and plot out the
    > histogram you can see what is acceptable.
    >
    > --
    > Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm


    >x = (int) (log(uniform() * (e-1) + 1.0) * N)

    With a million samples, that gives something almost linear with just a
    bit of sag(?); not sure what's happening yet, but it's a good starting
    point for further exploration.

    So far, this gives a reasonable linear:
    r = random()% (int)sqrt(random()%((N*N)-1) +1);
    and reciprocal:
    r = random()%(random()%(N-1)+1);

    Not very efficient though.

    Steve
    petertwocakes, Jan 17, 2009
    #5
  6. petertwocakes

    Walter Banks Guest

    geo wrote:

    > On Jan 17, 7:16 am, petertwocakes <>
    > wrote:
    > > Is there a way of creating a distribution of random numbers (using
    > > random() or any otherwise) that approximates:
    > > frequency = N-x (0<=x<=N)
    > > or
    > > frequency = N/(x+1) (0<=x<=N)
    > > Thanks
    > > Steve

    >
    > Perhaps the fastest way to generate
    > such variates with exactly those (scaled)
    > frequencies---and with specific C programs---may
    > be found in a web-available article:
    > "Fast Generation of Discrete Random Variables",
    > Marsaglia, Tsang and Wang,
    > www.jstatsoft.org/v11/i03/paper


    A very good practical reference I use for generating random
    numbers with various distributions is,

    "Statistical Distributions" N.A.J. Hastings and J.B.Peacock
    ISBN 0-470-35889-0 QA273.6.H37
    Halstead Press
    Distributed by Wiley 1974

    There are later editions. This book is worth tracking down
    for anyone who needs good random number generators.


    Regards,


    --
    Walter Banks
    Byte Craft Limited
    1 519 888 6911
    http://bytecraft.com
    Walter Banks, Jan 19, 2009
    #6
  7. petertwocakes <> writes:

    > Is there a way of creating a distribution of random numbers (using
    > random() or any otherwise) that approximates:
    >
    > frequency = N-x (0<=x<=N)


    The function you want is pow(rand_in_0_1(), 0.5) * N though the
    suggestion to use a table (as in the Marsaglia, Tsang and Wang paper)
    may well be faster.

    > frequency = N/(x+1) (0<=x<=N)


    I think this one is pow(rand_in_0_1(), 2.0) * N. It may be too late
    now, but I have found this a very useful reference:

    http://ftp.arl.mil/random/random.pdf

    --
    Ben.
    Ben Bacarisse, Jan 19, 2009
    #7
  8. petertwocakes

    CBFalconer Guest

    Walter Banks wrote:
    >

    .... snip ...
    >
    > A very good practical reference I use for generating random
    > numbers with various distributions is,
    >
    > "Statistical Distributions" N.A.J. Hastings and J.B.Peacock
    > ISBN 0-470-35889-0 QA273.6.H37
    > Halstead Press
    > Distributed by Wiley 1974
    >
    > There are later editions. This book is worth tracking down
    > for anyone who needs good random number generators.


    Huh? How can you consider a 'random sequence' with 'controlled
    distribution' to be a random number sequence? Or do those phrases
    not mean what I attribute to them?

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
    CBFalconer, Jan 20, 2009
    #8
  9. petertwocakes

    osmium Guest

    "CBFalconer" wrote:

    > Walter Banks wrote:
    >>

    > ... snip ...
    >>
    >> A very good practical reference I use for generating random
    >> numbers with various distributions is,
    >>
    >> "Statistical Distributions" N.A.J. Hastings and J.B.Peacock
    >> ISBN 0-470-35889-0 QA273.6.H37
    >> Halstead Press
    >> Distributed by Wiley 1974
    >>
    >> There are later editions. This book is worth tracking down
    >> for anyone who needs good random number generators.

    >
    > Huh? How can you consider a 'random sequence' with 'controlled
    > distribution' to be a random number sequence? Or do those phrases
    > not mean what I attribute to them?


    They are random drawings from a specified distribution. For a normal
    distribution centered on zero, numbers near zero are more likely than
    numbers two or three sigma away from zero.
    osmium, Jan 20, 2009
    #9
  10. CBFalconer <> writes:

    > Walter Banks wrote:
    >>

    > ... snip ...
    >>
    >> A very good practical reference I use for generating random
    >> numbers with various distributions is,
    >>
    >> "Statistical Distributions" N.A.J. Hastings and J.B.Peacock
    >> ISBN 0-470-35889-0 QA273.6.H37
    >> Halstead Press
    >> Distributed by Wiley 1974
    >>
    >> There are later editions. This book is worth tracking down
    >> for anyone who needs good random number generators.

    >
    > Huh? How can you consider a 'random sequence' with 'controlled
    > distribution' to be a random number sequence?


    The numbers that result from calling rand() are usually a good
    approximation to sampling from a discrete uniform distribution over
    [O, RAND_MAX]. By computing some function of the these numbers it is
    possible to approximate other distributions. For example,

    int bin(void)
    {
    int r = rand();
    return !(r & 1) + !(r & 2) + !(r & 4) + !(r & 8) + !(r & 16);
    }

    will return a pseudo-random number with a binomial distribution.
    Controlling the distribution to some extent does not prevent the
    sequence from being pseudo-random.

    > Or do those phrases
    > not mean what I attribute to them?


    If you said what you mean by them we'd know!

    --
    Ben.
    Ben Bacarisse, Jan 20, 2009
    #10
  11. petertwocakes

    Ben Pfaff Guest

    Ben Bacarisse <> writes:

    > The numbers that result from calling rand() are usually a good
    > approximation to sampling from a discrete uniform distribution over
    > [O, RAND_MAX].


    That's only true if the value of O is 0 :)

    The FAQ claims that "the low-order bits of many random number
    generators are distressingly *non*-random," by the way.
    --
    "A lesson for us all: Even in trivia there are traps."
    --Eric Sosman
    Ben Pfaff, Jan 20, 2009
    #11
  12. CBFalconer <> writes:

    > Walter Banks wrote:
    >>

    > ... snip ...
    >>
    >> A very good practical reference I use for generating random
    >> numbers with various distributions is,
    >>
    >> "Statistical Distributions" N.A.J. Hastings and J.B.Peacock
    >> ISBN 0-470-35889-0 QA273.6.H37
    >> Halstead Press
    >> Distributed by Wiley 1974
    >>
    >> There are later editions. This book is worth tracking down
    >> for anyone who needs good random number generators.

    >
    > Huh? How can you consider a 'random sequence' with 'controlled
    > distribution' to be a random number sequence? Or do those phrases
    > not mean what I attribute to them?


    "Random" to a mathematician means a quantity whose value is not
    completely predictable, and is influenced by chance. It is possible
    that some values are more or less likely than others; this information
    is expressed by the "distribution" of the quantity, which specifies the
    probabilities of the possible outcomes. If every outcome is equally
    likely, the distribution is said to be "uniform"; this is what
    laypeople often have in mind when they use the word "random".

    Rolling a die produces a random number between 1 and 6, distributed
    uniformly. Rolling a pair of dice produces a random number between 2
    and 12 whose distribution is not uniform (7 is six times more likely
    than 2).

    The OP wants to generate a random number such that the probability of
    the value being x is given by some function f(x). f here would
    technically be called a probability mass function.

    The antonym of "random" is "deterministic".
    Nate Eldredge, Jan 20, 2009
    #12
  13. Ben Pfaff <> writes:

    > Ben Bacarisse <> writes:
    >
    >> The numbers that result from calling rand() are usually a good
    >> approximation to sampling from a discrete uniform distribution over
    >> [O, RAND_MAX].

    >
    > That's only true if the value of O is 0 :)


    Ha! :-(

    > The FAQ claims that "the low-order bits of many random number
    > generators are distressingly *non*-random," by the way.


    Yes, it probably needs to be said every time rand() crops up though
    the result might still be considered a "good approximation" to a
    uniform distribution. For example, in the context to this thread
    where we compute f(rand() / (RAND_MAX + 1.0)) the bottom bits hardly
    matter (unless f is really odd and looks at the representation of its
    floating argument!).

    --
    Ben.
    Ben Bacarisse, Jan 20, 2009
    #13
  14. petertwocakes

    Walter Banks Guest

    Ben Bacarisse wrote:

    > I think this one is pow(rand_in_0_1(), 2.0) * N. It may be too late
    > now, but I have found this a very useful reference:
    >
    > http://ftp.arl.mil/random/random.pdf


    This is a very useful reference complete with simple example code
    for each of the random distribution algorithms. Similar in them to the
    reference I detailed, this is a collection of algorithms to produce
    random numbers with know statistical distributions starting with a
    random number generator with a a linear random distribution.

    These are extremely useful for Monte Carlo simulation and
    communication simulation applications.

    Nice Find

    Regards,


    --
    Walter Banks
    Byte Craft Limited
    http://bytecraft.com
    Walter Banks, Jan 20, 2009
    #14
  15. petertwocakes

    Guest

    Ben Pfaff <> wrote:
    >
    > The FAQ claims that "the low-order bits of many random number
    > generators are distressingly *non*-random," by the way.


    Which overstates the issue. The low-order bits of *most* random number
    generators, including the example one in the C standard, are just fine.
    As far as I know, there was only *one* reasonably wide spread random
    number generator whose low-order bits could be accurately described that
    way. Unfortunately, it was *very* wide spread. Fortunately, it's
    mostly gone now and it's very easy to detect (the generated sequence
    strictly alternates between even and odd numbers).
    --
    Larry Jones

    What better way to spend one's freedom than eating chocolate
    cereal and watching cartoons! -- Calvin
    , Jan 20, 2009
    #15
  16. petertwocakes

    Phil Carmody Guest

    CBFalconer <> writes:
    > Walter Banks wrote:
    >>

    > ... snip ...
    >>
    >> A very good practical reference I use for generating random
    >> numbers with various distributions is,
    >>
    >> "Statistical Distributions" N.A.J. Hastings and J.B.Peacock
    >> ISBN 0-470-35889-0 QA273.6.H37
    >> Halstead Press
    >> Distributed by Wiley 1974
    >>
    >> There are later editions. This book is worth tracking down
    >> for anyone who needs good random number generators.

    >
    > Huh? How can you consider a 'random sequence' with 'controlled
    > distribution' to be a random number sequence? Or do those phrases
    > not mean what I attribute to them?


    Almost certainly the latter.

    Go to sci.math and ask "how can you consider a sequence of 'random
    variables' with a 'probability density function' to be random?".
    Then translate the answer you get back into the computing domain.

    Phil
    --
    I tried the Vista speech recognition by running the tutorial. I was
    amazed, it was awesome, recognised every word I said. Then I said the
    wrong word ... and it typed the right one. It was actually just
    detecting a sound and printing the expected word! -- pbhj on /.
    Phil Carmody, Jan 20, 2009
    #16
  17. petertwocakes

    Phil Carmody Guest

    Ben Pfaff <> writes:
    > Ben Bacarisse <> writes:
    >
    >> The numbers that result from calling rand() are usually a good
    >> approximation to sampling from a discrete uniform distribution over
    >> [O, RAND_MAX].

    >
    > That's only true if the value of O is 0 :)
    >
    > The FAQ claims that "the low-order bits of many random number
    > generators are distressingly *non*-random," by the way.


    The FAQ needs updating. Very few c libraries have the dismal
    properties that many did back when that FAQ answer was written.
    Probably only one (and if so, yes, it's just a shame it's
    installed on a billion computers owned by people who don't
    care whether or not its c library is crap or not).

    Phil
    --
    I tried the Vista speech recognition by running the tutorial. I was
    amazed, it was awesome, recognised every word I said. Then I said the
    wrong word ... and it typed the right one. It was actually just
    detecting a sound and printing the expected word! -- pbhj on /.
    Phil Carmody, Jan 20, 2009
    #17
  18. petertwocakes

    Phil Carmody Guest

    writes:
    > Ben Pfaff <> wrote:
    >>
    >> The FAQ claims that "the low-order bits of many random number
    >> generators are distressingly *non*-random," by the way.

    >
    > Which overstates the issue. The low-order bits of *most* random number
    > generators, including the example one in the C standard, are just fine.
    > As far as I know, there was only *one* reasonably wide spread random
    > number generator whose low-order bits could be accurately described that
    > way. Unfortunately, it was *very* wide spread. Fortunately, it's
    > mostly gone now and it's very easy to detect (the generated sequence
    > strictly alternates between even and odd numbers).



    MS have, for instance, used the quite depressingly, but predictably,
    pitiful n' = (n*a+c)%m with a=16598013, c=2820163 and m=2^24.
    I wouldn't call stuff from, or at least yclept, 2003 'mostly gone'.

    Phil
    --
    I tried the Vista speech recognition by running the tutorial. I was
    amazed, it was awesome, recognised every word I said. Then I said the
    wrong word ... and it typed the right one. It was actually just
    detecting a sound and printing the expected word! -- pbhj on /.
    Phil Carmody, Jan 20, 2009
    #18
  19. petertwocakes

    Guest

    Phil Carmody <> wrote:
    >
    > MS have, for instance, used the quite depressingly, but predictably,
    > pitiful n' = (n*a+c)%m with a=16598013, c=2820163 and m=2^24.
    > I wouldn't call stuff from, or at least yclept, 2003 'mostly gone'.


    Precisely where did you find that generator? My MS Visual Studio 6
    (circa 1998) source has:

    seed' = seed * 214013 + 2531011
    n' = (seed' / 65536) % 32768

    which may not be stellar, but it's certainly not depressing or pitiful.
    (And it appears VS 8 is still using the same generator.)
    --
    Larry Jones

    ANY idiot can be famous. I figure I'm more the LEGENDARY type! -- Calvin
    , Jan 21, 2009
    #19
  20. petertwocakes

    Ben Pfaff Guest

    writes:

    > As far as I know, there was only *one* reasonably wide spread random
    > number generator whose low-order bits could be accurately described that
    > way. Unfortunately, it was *very* wide spread.


    Which one?
    --
    "Programmers have the right to be ignorant of many details of your code
    and still make reasonable changes."
    --Kernighan and Plauger, _Software Tools_
    Ben Pfaff, Jan 21, 2009
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. globalrev
    Replies:
    4
    Views:
    745
    Gabriel Genellina
    Apr 20, 2008
  2. Alex
    Replies:
    11
    Views:
    578
    Jeremy Sanders
    Aug 8, 2008
  3. thinke365
    Replies:
    11
    Views:
    2,228
    Robert Kern
    Jan 25, 2010
  4. Alex Untitled
    Replies:
    11
    Views:
    651
    Giampiero Zanchi
    Nov 16, 2009
  5. VK
    Replies:
    15
    Views:
    1,125
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page