PRNG with adjustable period

问题:

I need to build an in-place pseudo-random number generator with an adjustable period. In addition, there must be no collisions within one period. That is, the following must return true:

// prng is "generated" at run-time
// (though a by-hand solution would work)

bool test(func prng, int period) {
    int seed = 0;  // Any number should work
    int cur = seed;

    for (int i = 0; i <= period; ++i) {
        cur = prng(cur);

        if (cur == seed) {
            if (i == period) {
                // We hit our period on target
                return true;
            }

            // Period too low (we hit our seed already!)
            return false;
        }
    }

    // Period too high
    return false;
}

(Example is pseudocode; an answer in any commonly readable language (C++, Python, Haskell, etc.) is acceptable.)

The PRNG must not depend on mutable static state when generating the numbers. That is, I can't have a large table of already-returned numbers or something like that. It should only rely on the given input for generating the next term.

The algorithm does not have to be cryptographically strong (of course), or "strongly" random. However, x % period is not acceptable; it has to be at least somewhat random.

I have looked into linear congruential generators, but that seems to be the wrong path to take for my specific constraints.

(Brute-forcing is not an option, unless it's relatively quick (a few seconds).)

回答1:

I think a good candidate is a Fibonacci Linear Feedback Shift Register (LFSR).

You can get the relevant info and algorithms from Wikipedia.

Just an excerpt:

The initial value of the LFSR is called the seed, and because the operation 
of the register is deterministic, the stream of values produced by the 
register is completely determined by its current (or previous) state. 
Likewise, because the register has a finite number of possible states, it must 
eventually enter a repeating cycle. However, an LFSR with a well-chosen 
feedback function can produce a sequence of bits which appears random and 
which has a very long cycle.

The only problem is that the periods for the LFSR are always of the form 2^N-1.
You could overcome this noting that for any wanted period P, choosing the N that gives you the "next" 2^N-1 value leaves potentially 2^(N-1)-1 numbers to supress from the cycle (because if you need to supress more than that, just generate with N-1).

So, to supress k values (k = ((2^N-1) - P) ⋳ {1 ... ,2^(N-1)-1}) you can add a little logic such as

    If (Mod(cur,2(N-1)+1-k) == 0) Then
       cur=Mod(cur+1,2N-1)