Re: random numbers in fortran

Mark:

What I hear you asking for are some practical solutions to this problem.

In words one solution is to generate random permutations (sampling
without replacement). For N=52 this will produce a random shuffling
of a 52-card deck. The code to do this requires two parts:

1) A Random number generator with "decent" properties.
The built-in Random_Number intrinsic will do. Or you can use one
of several good quasi-random number generators. This latter
strategy would enable one to generate the same quasi-random
sequence across compilers (and platforms). For example:

http://users.bigpond.net.au/amiller/random.html
(Cycle lengths of these are documented in the leading comments;
for example TAUS88.F8=90 has a cycle length of about 3E+26).

http://ftp.cac.psu.edu/pub/ger/fortran/hdk/byterand.f90
(Cycle Length of this one is: 6953607871644 > 6.95E+12)
Also see: http://www.cs.berkeley.edu/~daw/rnd/

2) A Random Permutation code. Knuth provides this. See Subroutine
RPERM within the code: http://ftp.cac.psu.edu/pub/ger/fortran/hdk/byterand.f90
The sample driver here prompts for N and 3 seeds. Choose N=52 for example.

Unless I'm missing something in this thread, there is no need to
worry about the number 52!, the number of different permutations of N=52.

Skip Knoble


On 28 Nov 2006 12:01:27 -0800, "Mark Morss" <mfmorss@xxxxxxx> wrote:

-|Actually I was not the person who made the original post, but in any
-|case, my question was, what are the >practical< implications of your
-|point? This being a forum devoted to Fortran, not combinatorics, I was
-|hoping for an explanation of how, in Fortran, one would make sure that
-|this criterion were satisfied.
-|
-|How, for example, would one set "cycle length" to be sure that each one
-|of 52! combinations had the same chance of coming up? My Fortran
-|reference is Chapman's _Fortran 90/95 for Scientists and Engineers_,
-|and in its brief discussion of the RANDOM_SEED and RANDOM_NUMBER
-|intrinsics, it makes no mention of "cycle length."
-|
-|But also on a practical level, given the uncertain randomness of
-|pseudo-random numbers, how could anyone know that each one of so many
-|combinations had the same chance of coming up? I would have thought
-|that if a very large number of simulated deals satisfied apparent
-|randomness, that would be sufficient for most practical purposes --
-|even if it were known >a priori< that certain outcomes possible in
-|reality were impossible in the simulation.
-|
-|Gordon Sande wrote:
-|> On 2006-11-28 10:07:31 -0400, "Mark Morss" <mfmorss@xxxxxxx> said:
-|>
-|> > You said:
-|> >
-|> > "The basic statistical property that you should worry about first is
-|> > the
-|> > cycle length. To shuffle cards you want all 52! permutations to have a
-|> > chance of happening. With a short cycle length that does not happen.
-|> > A rather critical issue if you are going to pretend that the results
-|> > have any relevance to real card games."
-|> >
-|> > Would you please elucidate? I am not sure of the practical
-|> > implications of this remark.
-|>
-|> You are trying to shuffle cards, or so you said.
-|>
-|> There are 52! possible shuffles. Get a high precision calculator and
-|> do the many precision arithmetic. Or just use an approximation. It is
-|> more than you can count on your fingers! Or even your fingers and toes.
-|>
-|> With a short cycle length the PSEUDO random number generator will not
-|> be able to represent all those permutations. Even if it had a chance it
-|> still might not actually have the permutation somewhere on its cycle.
-|> The first is elementary combinatorics and the second is a more subtle
-|> issue on the quality of the pseudo random number generator.
-|>
-|> If there are permutations missing then anything you do based on
-|> the "random" permutations will be at best "hap-hazard". That is
-|> fine for games for young children with short memories but is a bit
-|> short on quality for most other applications.
-|>
-|> You dropped the piece where it said
-|>
-|> > It turns out that this "trivial example" is in fact quite demanding of
-|> > a pseudo random number generator.
-|>
-|> which comes as a big surprise to many who do not try to do the simple
-|> combinatorics. You have lots of company on that.
-|>
-|> If all you are doing is a game for young children then fine. Otherwise
-|> you should read some real literature on the topic which your question
-|> indicates that you have not yet done.

.

Relevant Pages

  • Re: random numbers in fortran
    ... How, for example, would one set "cycle length" to be sure that each one ... combinations had the same chance of coming up? ... With a short cycle length the PSEUDO random number generator will not ... be able to represent all those permutations. ...
    (comp.lang.fortran)
  • Re: LCM of all cycle lengths
    ... Then, without much warning, the third and fourth paragraphs change the subject to "all possible E". ... The set of keys could just be the set of permutations on, ... since every cycle length from 1 to B appears somewhere. ... If I have a chosen-plaintext oracle for AES256, I can decrypt a given ciphertext after an expected 2**127 inquiries. ...
    (sci.crypt)
  • Re: random numbers in fortran
    ... I make sure that I have a generator capabable of producing any of the ... I understand also that with a short cycle, ... Generally in practice then, could I not compensate for a short cycle by ... In words one solution is to generate random permutations (sampling ...
    (comp.lang.fortran)
  • Re: random numbers in fortran
    ... To shuffle cards you want all 52! ... With a short cycle length that does not happen. ... be able to represent all those permutations. ... Even if it had a chance it ...
    (comp.lang.fortran)
  • Re: Expected average cycle length...
    ... >> in a random permutation of N elements, all N cycle lengths are ... > "over all permutations and elements ... I think that corresponds to your second choice, ... Thus all the possible cycle lengths are equally likely, ...
    (sci.crypt)