# Liinear distribution of random numbers?

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

1. ### petertwocakesGuest

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

2. ### geoGuest

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

3. ### Ben BacarisseGuest

"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
4. ### petertwocakesGuest

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

petertwocakes, Jan 17, 2009
5. ### petertwocakesGuest

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
6. ### Walter BanksGuest

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
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
7. ### Ben BacarisseGuest

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
8. ### CBFalconerGuest

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
> 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>

CBFalconer, Jan 20, 2009
9. ### osmiumGuest

"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
>> 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
10. ### Ben BacarisseGuest

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
>> 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
11. ### Ben PfaffGuest

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
12. ### Nate EldredgeGuest

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
>> 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
13. ### Ben BacarisseGuest

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
14. ### Walter BanksGuest

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
15. ### 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
16. ### Phil CarmodyGuest

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
>> 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
17. ### Phil CarmodyGuest

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
18. ### Phil CarmodyGuest

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
19. ### 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
20. ### Ben PfaffGuest

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