Re: random generator for a given period

On 2009-02-16 10:26:21 -0400, Art Kendall <Arthur.Kendall@xxxxxxxxxxx> said:

Well mostly I'm in this for the intellectual challenge, but I'll note
> that memory seems cheap without being so. Memory is slow. Tighter
> algorithms are often significantly faster.


but that is relevant only if you are going to execute the code a huge number of times. The machine time saved over years might well be less than the wall time it is taking to write

If you should ever want to maintain the program (say in a couple weeks time after
you have stopped been absolutely on top of all details), or someone else is required
to, then the saving will quickly disappear. Simple effective and transparent is
relevant for all but very few exceedingly demanding applications. Tight fast super
efficient, but obscure, code sounds really good over beer with the boys where you
can easily ommit the obscure part.

The efficiency game it all about algorithms and rarely about polishing the code. And
even then good algorithms are only required on central parts of the code. Elsewhere
things just need to not be terribly bad. Sometimes it is not obvious where the central
part is so good measuring tools are needed but that is getting into serious software
engineering.

You can generate 2 arrays, one with the indices, and one with the out put of a pre-existing prng. Then you can sort on the random numbers with the array of indices passive.

for purposes of generating a few thousand random permutations of an array of indices a crude prng would likely do the job although very good quality prngs are widely available so there would be no need to use the crude one.

Art Kendall

Andrei Alexandrescu wrote:
Gordon Sande wrote:
On 2009-02-15 01:35:28 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@xxxxxxxxxx> said:

Allen McIntosh wrote:
Andrei Alexandrescu wrote:
I've looked into the problem of randomly covering an array. Given an
array of length m, generate a succession of m random indices into that
array such that the same index is never visited more than once (and consequently the entire array is visited in m steps). So what I'm looking for is a random numbers generator of a given period and with the range equal to the period.

It sounds like what you need is a random permutation. The Wikipedia article on "random permutation" should get you started.

If you are using this for anything serious, you should read
http://www.cigital.com/papers/download/developer_gambling.php
(google "computer shuffle card deck" for more)

I am familiar with shuffling via e.g. the Fisher-Yates algorithm. However I am not looking for that. The original array is supposed to remain untouched, I just need to generate a random sequence of indices to walk it. Again, a simple approach is to generate a separate array of indices and shuffle that. But I'd like to do it in constant space, e.g. by using a special random number generator.


Andrei

If you literally want a pseudo random number generator with an arbitrary user specified
length implelemented with the usual modular arithmetic you will find that things are
very awkward technically as most modulii will be composite with multiple distinct
prime factors. The usual theory covers prime or prime power modulus only as these
lead to very tractable finite groups with only a few subgoups. (That is why the
seed for use with prime power is restricted. It picks the desired subgroup!) You can
keep track of the subgroups but that requires bookkeeping that looks more like
log n space.

(I'll note that log n space is really just an integer. :o))

I'm not sure I understand most of what you say. In case you are referring (at least in part) to linear congruential generators, my understanding is that it's not that hard to find good parameters for a given period. Consider the recurrence x = (a * x + c) mod m, where m is given. According to Wikipedia, for that to have period exactly m, my understanding is that

1. c and m are relatively prime,
2. a - 1 is divisible by all prime factors of m,
3. a - 1 is a multiple of 4 if m is a multiple of 4.

So let's say m is given and we need to choose "good" a and c values.

1. Draw c at random from {1, 2, 3, ..., m - 1} until gcd(m, c) == 1.

2. Factor m into primes and obtain the number d = p1 * p2 * ... * pn, where pk are m's prime factors. If the power of 2 in the factorization is greater than 1, assign d = d * 2.

3. Choose a = r * d + 1, where r is a random number between 2 and an upper limit conveniently chosen such that overflow on 32 or 64 bits is avoided.

Now we have the parameters for the linear congruential engine, all we have to do is seed it and off we go. Is that correct? Would this approach generate good LCGs? How does this connect with your discussion of subgroups?

If development time is at all valued the use of a conventional permutation algorithm
with a marker array would seem sensible. Memory is very chearp anymore except for
folks doing rather special hardware.

Well mostly I'm in this for the intellectual challenge, but I'll note that memory seems cheap without being so. Memory is slow. Tighter algorithms are often significantly faster.


Andrei


.

Relevant Pages

  • Re: random generator for a given period
    ... > that memory seems cheap without being so. ... Then you can sort on the random numbers with the array of indices passive. ... So what I'm looking for is a random numbers generator of a given period and with the range equal to the period. ... Tighter algorithms are often significantly faster. ...
    (sci.stat.math)
  • Re: STL - Vector - Normalization ?
    ... > algorithms min_element etc in the function and did not use functors. ... My initial test used an array of 100 million integers. ... Which means my system ran out of memory and so ... you're short on memory and the computer has to swap RAM with disk space, ...
    (comp.lang.cpp)
  • Re: Long lists
    ... Keep data in memory whenever you can in order to preserve flexibility. ... will need special implementations of algorithms that talk to disk. ... to get the respective string. ... like an array of strings. ...
    (comp.programming)
  • Re: random generator for a given period
    ... array such that the same index is never visited more than once. ... So what I'm looking for is a random numbers generator of a given period and with the range equal to the period. ... How does this connect with your discussion of subgroups? ... Well mostly I'm in this for the intellectual challenge, but I'll note that memory seems cheap without being so. ...
    (sci.stat.math)
  • Re: How to create multiple threads?
    ... the memory would be depleted only if the threads never stopped running. ... could use an array). ... generator would eventually use up the memory of the computer as the ...
    (microsoft.public.dotnet.languages.vb)