|
|
| Author |
Message |
Guest
|
 Posted: Tue May 24, 2005 1:11 am Post subject:
Seeds for PRNG's
|
|
|
I am writing an application that needs to select about 300 people
randomly from a population of roughly 125,000. The requirements state
that a generator with at least 92 seed values should be used. All of
the generators that I have found, take a single long value as its seed
including George Marsaliga's Mother of all
Pseudo-Random-Number-Generators.
Are there generators in use that take multiple seed values? Am I
misunderstanding what it means to provide mutiple seeds to a
generator?
Thanks... |
|
| Back to top |
|
 |
George Marsaglia
science forum beginner
Joined: 24 May 2005
Posts: 21
|
| Posted: Tue May 24, 2005 9:19 am Post subject:
Re: Seeds for PRNG's
|
|
|
<jgulisano@aeontec.net> wrote in message
news:1116904281.734749.35070@f14g2000cwb.googlegroups.com...
| Quote: | I am writing an application that needs to select about 300 people
randomly from a population of roughly 125,000. The requirements state
that a generator with at least 92 seed values should be used. All of
the generators that I have found, take a single long value as its seed
including George Marsaliga's Mother of all
Pseudo-Random-Number-Generators.
Are there generators in use that take multiple seed values? Am I
misunderstanding what it means to provide mutiple seeds to a
generator?
|
Here is a complimentary-multiply-with-carry (CMWC) RNG
implemented in C, requiring 4097 seeds.
It will return 32 bit random integers
in the range [0,b), with b=2^32-1. The period of the
RNG is 18782*b^4096 > 10^39460, and every possible sequence
of 4096 successive integers in the range [0,b) will appear
somewhere in that full period.
static unsigned long Q[4096], c=362436;
unsigned long CMWC4096(void){
unsigned long long t, a = 18782LL;
static unsigned long i = 4095;
unsigned long x, r = 0xfffffffe;
i = (i+1)&4095;
t = a*Q[i]+c; c = (t>>32); x = t+c;
if(x<c){x++;c++;} if((x+1)==0) {c++; x=0;}
return(Q[i] = r-x); }
It requires 4096 seeds and an initial "carry" c<18782.
For any such seed set, the RNG produces, in reverse order,
the base-b digits of the expansion of k/p for some 0<k<p,
with b=2^32-1 and p=18782*b^4096+1.
Because b is a primitive root for the prime p,
any two such expansions are just circular rotations
of one another.
An initial seed c<18782 and the 4096 elements
in the static array Q[4096] should be assigned values
before calls to the function CMWC4096( ),
otherwise the first few thousand returned values will be
zeros. (That is consistent with the view that the choice
of seeds merely chooses a random starting point in a huge
circle of over 10^39460 base-b digits. Failing to initialize
the Q[4096] array (set by C's default to 0's) merely provides
a default starting point at a long string of zeros, which
should be occasionally encountered in any random string,
but of course in practice you want to choose a random
starting point in that immense loop.)
George Marsaglia |
|
| Back to top |
|
|
Jose G.
science forum beginner
Joined: 24 May 2005
Posts: 3
|
| Posted: Tue May 24, 2005 1:50 pm Post subject:
Re: Seeds for PRNG's
|
|
|
Would you know of any resources that may have the above generator
available in Java. I am not a seasoned C programmer and don't trust
myself doing the conversion. I also don't feel I have the background to
implement your algorithm on my own in Java.
The application I am writing must adhere to Florida Supreme Court
statutes that specifically refer to your random number generators so I
very much appreciate you taking the time to answer this post!
Thank you!
Jose Gulisano. |
|
| Back to top |
|
|
Peter Spellucci
science forum Guru
Joined: 29 Apr 2005
Posts: 702
|
| Posted: Tue May 24, 2005 4:44 pm Post subject:
Re: Seeds for PRNG's
|
|
|
In article <1116904281.734749.35070@f14g2000cwb.googlegroups.com>,
jgulisano@aeontec.net writes:
| Quote: | I am writing an application that needs to select about 300 people
randomly from a population of roughly 125,000. The requirements state
that a generator with at least 92 seed values should be used. All of
the generators that I have found, take a single long value as its seed
including George Marsaliga's Mother of all
Pseudo-Random-Number-Generators.
Are there generators in use that take multiple seed values? Am I
misunderstanding what it means to provide mutiple seeds to a
generator?
Thanks...
|
what about these:
14. Zbl 0917.65005 Matsumoto, Makoto; Nishimura, Takuji
Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. (English)
ACM Trans. Model. Comput. Simul. 8, No.1, 3-30 (1998)
9. Zbl 1042.65505 L'Écuyer, Pierre
Good parameters and implementations for combined multiple recursive random number generators. (English)
Oper. Res. 47, No.1, 159-164 (1999). MSC 2000: *65C10
13. Zbl 0932.65004 Kao, Chiang; Tang, Hui-Chin
Several extensively tested multiple recursive random number generators. (English)
Comput. Math. Appl. 36, No.6, 129-136 (1998). MSC 2000: *65C10
28. Zbl 0703.65007 Eddy, William F.
Random number generators for parallel processors. (English)
J. Comput. Appl. Math. 31, No.1, 63-71 (1990). MSC 2000:
(and more ... -> search in Zentralblatt)
hth
peter |
|
| Back to top |
|
|
Herman Rubin
science forum Guru
Joined: 25 Mar 2005
Posts: 730
|
| Posted: Tue May 24, 2005 5:15 pm Post subject:
Re: Seeds for PRNG's
|
|
|
In article <1116904281.734749.35070@f14g2000cwb.googlegroups.com>,
<jgulisano@aeontec.net> wrote:
| Quote: | I am writing an application that needs to select about 300 people
randomly from a population of roughly 125,000. The requirements state
that a generator with at least 92 seed values should be used. All of
the generators that I have found, take a single long value as its seed
including George Marsaliga's Mother of all
Pseudo-Random-Number-Generators.
Are there generators in use that take multiple seed values? Am I
misunderstanding what it means to provide mutiple seeds to a
generator?
Thanks...
|
How long is long? Personally, I would never use such a
short seed; many pseudo-random generators have seeds
extending into the tens of thousands of bits, or which
do this upon extension. Seeding them with small amounts
of information puts in all sorts of weaknesses.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 |
|
| Back to top |
|
|
George Marsaglia
science forum beginner
Joined: 24 May 2005
Posts: 21
|
| Posted: Thu May 26, 2005 11:53 am Post subject:
Re: Seeds for PRNG's
|
|
|
"Jose G." <jgulisano@aeontec.net> wrote in message
news:1116949844.243759.108050@g14g2000cwa.googlegroups.com...
| Quote: | Would you know of any resources that may have the above generator
available in Java. I am not a seasoned C programmer and don't trust
myself doing the conversion. I also don't feel I have the background to
implement your algorithm on my own in Java.
The application I am writing must adhere to Florida Supreme Court
statutes that specifically refer to your random number generators so I
very much appreciate you taking the time to answer this post!
Thank you!
Jose Gulisano.
|
I don't know java, but those who do should
be able to provide, in java, a 1000+seed MWC
RNG with if java instructions permit direct
implementation of these simple operations,
available in the instruction set of most modern CPUs:
given a multiplier 'a' and current values 'x' and 'c',
32-bit (unsigned) integers, form
t = a*x+c in 64 bits
then the new 'c' is the top 32-bits of 't',
the new 'x' the bottom 32-bits of 't'.
Do java instructions permit direct
implementation of such? Fortran does not,
one of the main reasons I switched to C years
ago when developing AWC and MWC RNGs.
The other instructions in the CMWC version
have to do with converting the automatic
reductions modulo 2^32 to modulus 2^32-1,
since the latter can be a primitive root,
while 2^32 cannot.
The MWC versions seem to behave as well as
CMWC RNGs, but all the base-b expansions
of k/p are not circular rotations of a
single one, so the theory is not as elegant.
You are apparently required to conform with
requirements that I proposed as a consultant
for the Florida Supreme Court: in using a RNG
to select a jury venire, (a random subset of k
from a set of n eligibles), you must have
at least as many choices for the seeds as there
are possible subsets of k from n, that is,
n!/(k!*(n-k)!).
In your case, k=300 from n=125000, so there
are more than 10^914 possible subsets.
Florida law requires that selection be
by lot and at random---that is, every subset
must have the same probability of being chosen.
So, assuming seeds of 10 digits, you would need
a RNG with more than 92 seeds.
Suggestions for getting such a set of seeds
by means of procedures that can be determined
in advance---and documented afterward---are in
"Seeds for random number generators",
Commun. ACM v46(5), 2003, 90--93.
which suggests use of suitably modified data
from forthcoming stock market reports.
In the technical journal of The American Bar
Association, I described the difficulties
in using RNGs to choose, by lot and at random,
one of many possibilities:
"Problems with the use of computers
for selecting jury panels",
Jurimetrics v41, Summer 2001, 425--427.
This led to concern that convicted felons or
losers of civil cases might demand new trials
because their jury panel selections were made
with RNGs having only one or a few seeds, and
thus were not chosen, as the law requires,
by lot and at random.
I will ask colleagues who know java as well as
methods for impementing MWC RNGs to
look into providing a java version.
George Marsaglia
> |
|
| Back to top |
|
|
Jose G.
science forum beginner
Joined: 24 May 2005
Posts: 3
|
| Posted: Thu May 26, 2005 7:09 pm Post subject:
Re: Seeds for PRNG's
|
|
|
Again, thank you very much. I look forward to any information you can
provide. |
|
| Back to top |
|
|
Allen McIntosh
science forum beginner
Joined: 27 May 2005
Posts: 20
|
| Posted: Fri May 27, 2005 7:46 pm Post subject:
Re: Seeds for PRNG's
|
|
|
| Quote: | I don't know java, but those who do should
be able to provide, in java, a 1000+seed MWC
RNG with if java instructions permit direct
implementation of these simple operations,
available in the instruction set of most modern CPUs:
given a multiplier 'a' and current values 'x' and 'c',
32-bit (unsigned) integers, form
t = a*x+c in 64 bits
then the new 'c' is the top 32-bits of 't',
the new 'x' the bottom 32-bits of 't'.
Do java instructions permit direct
implementation of such?
Java has 64 bit signed integers. That's about as close as you can get |
to the hardware (deliberately).
In the OP's shoes, given the possibility of legal challenge that the
Java implementation is correct, I think I would just access the C code
using JNI. |
|
| Back to top |
|
|
Jose G.
science forum beginner
Joined: 24 May 2005
Posts: 3
|
| Posted: Tue May 31, 2005 4:38 pm Post subject:
Re: Seeds for PRNG's
|
|
|
I havn't worked with JNI, I took a quite glance at it and it seems like
an option. Thanks for the tip, I'll take a closer look at that. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Sep 09, 2010 1:11 pm | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums |
send newsletters
|
| |
|
Ipod Shuffle | Ipod Touch 64gb | Plane Tickets | Shower Enclosures | Cheap Home Insurance
|
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
num-analysis
