random cover of a range

[Andrei Alexandrescu]

Jason House wrote:
> I bet a special random generator could be built for O(1) memory at
> the sacrifice of less random sequences. I think it should be possible
> to pick seed numbers to a generator that will cycle through all
> values in a set order.
> 
> I'll think more to see if I can come up with something creative.

A linear congruential generator

http://en.wikipedia.org/wiki/Linear_congruential_generator

with the recurrence

x[n] = (x[n-1] * a + c) % m

has period exactly m if:

a) c and m are relatively prime

b) (a-1) divisible by all prime factors of m

c) (m-1) % 4 == 0 <= (a-1) % 4 == 0

Now most of the times people want the period to be as long as possible 
so they choose m = 2^32 and work some "good" a and m from there. In our 
situation, m is given (the length of the input range) and we need to 
compute a and c. Here's a simple method:

1. Factor m into primes. Obtain arrays p[], the prime factors, and w[], 
their powers. For example, say m = 125, then p[] = [ 3, 5 ] and w[] = [ 
1, 2 ].

2. Replace each element w[i] with a number between 1 and w[i] inclusive.

3. Construct a1=a-1 as the pointwise product w[] * p[]. If m-1 is 
divisible by 4 and a1 is not, multiply a1 by 2 or 4 as needed.

4. Construct a = a1 + 1

5. Construct c as a product of random powers of prime numbers, paying 
attention that all powers of the primes in p[] are 0.

Now we have a linear congruential generator that covers the range 0 .. m 
exactly.


Andrei