|
Home > Archive > Unix Programming > May 2005 > a question each about random() function and LCG
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
a question each about random() function and LCG
|
|
| Chakravarthi 2005-04-24, 2:46 pm |
| hi all.
________________________________________
_______________________________
1. A snippet from man page of random() function in Linux reads -
"The random() function uses a non-linear additive feedback random number
generator employing a default table of size 31 long integers to return
successive pseudo-random numbers in the range from 0 to RAND_MAX. The
period of this random number generator is very large, approximately
16*((2**31)-1)."
Can anyone give reference material where this is proved ?
________________________________________
_______________________________
2. Divide the interval 0 - RANDMAX of an Linear Congruential
Generator into `k' sub intervals and output the interval number
where the output number falls in rather than the number itself.
How can one comment on the periodicity of this sequence.
Even for a good choice of parameters for LCG, can it happen that
this sequence has periodicity less than original sequence ?
Even a reference on this is highly welcome.
________________________________________
_______________________________
thanx,
chax.
| |
|
| On 24 Apr 2005 09:25:36 -0700, pschax@gmail.com (Chakravarthi) wrote:
>hi all.
>
> ________________________________________
_______________________________
>
> 1. A snippet from man page of random() function in Linux reads -
>
> "The random() function uses a non-linear additive feedback random number
> generator employing a default table of size 31 long integers to return
> successive pseudo-random numbers in the range from 0 to RAND_MAX. The
> period of this random number generator is very large, approximately
> 16*((2**31)-1)."
>
> Can anyone give reference material where this is proved ?
Without more information on the generator, no. Don't have time to
look at the source code.
> ________________________________________
_______________________________
>
> 2. Divide the interval 0 - RANDMAX of an Linear Congruential
> Generator into `k' sub intervals and output the interval number
> where the output number falls in rather than the number itself.
> How can one comment on the periodicity of this sequence.
>
> Even for a good choice of parameters for LCG, can it happen that
> this sequence has periodicity less than original sequence ?
>
> Even a reference on this is highly welcome.
The sequence will be much more orderly, see
Marsaglia, G. Random numbers fall mainly in the planes, Proceedings
National Academy Science, 61, 25-28 (1968).
> ________________________________________
_______________________________
>
>
> thanx,
> chax.
Leslie 'Mack' McBride
remove text between _ marks to respond via e-mail
| |
| Chakravarthi 2005-04-25, 2:53 am |
| Mack <macckone@a_nospamjunk123_ol.com> wrote in message news:<ec1o61hqbd370dtidhcr2hli44h78rgooe@4ax.com>...
> On 24 Apr 2005 09:25:36 -0700, pschax@gmail.com (Chakravarthi) wrote:
>
> The sequence will be much more orderly,
"much more orderly" meaning what ? Does it mean that their periodicities
are less as compared to original sequence or more ? Please elaborate.
> see
> Marsaglia, G. Random numbers fall mainly in the planes, Proceedings
> National Academy Science, 61, 25-28 (1968).
I have read this paper already. It is about how, when one groups the
output sequences into n-tuples, points lie in a set of hyperplanes
governed by the recurrence relation of the LCG.
Hopefully, I'm missing something subtle in the paper. Please elaborate.
thanx,
chax.
| |
|
| On 24 Apr 2005 22:03:15 -0700, pschax@gmail.com (Chakravarthi) wrote:
>Mack <macckone@a_nospamjunk123_ol.com> wrote in message news:<ec1o61hqbd370dtidhcr2hli44h78rgooe@4ax.com>...
>
>
> "much more orderly" meaning what ? Does it mean that their periodicities
> are less as compared to original sequence or more ? Please elaborate.
When you group the numbers into bins they fill too evenly.
After rereading your question I am not certain what you mean
by less periodic. An output constructed from by binning the
output of a generator can only have a period equal to or shorter
than the period of the generator.
>
>
> I have read this paper already. It is about how, when one groups the
> output sequences into n-tuples, points lie in a set of hyperplanes
> governed by the recurrence relation of the LCG.
> Hopefully, I'm missing something subtle in the paper. Please elaborate.
>
>
> thanx,
> chax.
Leslie 'Mack' McBride
remove text between _ marks to respond via e-mail
|
|
|
|
|