Generating Full Period/Full Cycle Random Numbers o

问题:

I wish to generate psuedo-random numbers/permutations that 'occupy' a full period or full cycle within a range. Usually an 'Linear Congruential Generator' (LCG) can be used to generate such sequences, using a formula such as:

X = (a*Xs+c) Mod R

Where Xs is the seed, X is the result, a and c are relatively prime constants and R is the maximum (range).

(By full period/full cycle, I mean that the constants can be chosen so that any X will occur only once in some random/permuted sequence and will be within the range of 0 to R-1 or 1 to R).

LCG almost meets all of my needs. The problem I have with LCG is the non-randomness of the odd/even result, ie: for a seed Xn, the result X will alternate odd/even.

Questions:

1. Does anybody know how to create something similar that will not alternate odd/even?

2. I believe that a 'Compound LCG' could be built, but I don't have details. Can somebody give an example of this CLCG?

3. Are there alternative formulas that might meet the details above and constraints below?

Constraints:

4. I want something based on a simple seed-based formula. ie: to get the next number, I provide the seed and get the next 'random number' in the permuted sequence. Specifically, I cannot use pre-calculated arrays. (See next points)
5. The sequence absolutely has to be 'full period/full cycle'
6. The range R could be several million or even 32bit/4 billion.

7. The calculation should not suffer overflow and be efficient/fast, ie: no large exponents or dozens of multiplies/divides.

8. Sequence does not have to be terribly random or secure - I do not need cryptographic randomness (but can use it if viable), just 'good' randomness or apparent randomness, without odd/even sequences.

Any thoughts appreciated - thanks in advance.

UPDATE: Ideally the Range variable may not be an exact power of two, but should work in either case.

回答1:

Trivial solution. Make a LCG with R a prime somewhat larger than the range you want, and both a and c somewhere random in that range. If it gives you a number that is larger than you want, iterate again until you are back in range.

The numbers output will not have a particularly simple pattern mod 2, 3, 5, etc up to any prime less than the prime you use.

If the range you want is large then the nearest larger prime will only be a small amount larger, so you'll very rarely need to call it twice. For example if your desired range is a billion, you can use 1000000007 as your prime, and you'll need to skip an extra number less than 0.000001% of the time.

I found this prime by going to http://primes.utm.edu/curios/includes/primetest.php and putting in numbers until I got a prime. I was a little lucky. The odds that n ending in 1, 3, 7, 9 are prime are approximately 2.5/log(n) which out at a billion are about 12%, so I was somewhat lucky to find this number after only 4 tries. But not that lucky - I found it in 3 tries and on average I should have needed 8.

EDIT: This random number generator can have a shorter cycle. See the note by @dzugaru.

回答2:

If odd/even alternation is your only problem, leave the state change computation unchanged. Before using each output you can either shift the lower bits out or swap the the bits around.

Edit:

With the bit-swapping (fixed pattern) variant, you will keep generating whole periods.

Pseudo-Code of initial LCG:

function rand
   state := update(state)
   return state

Pseudo-Code of LCG including swapping:

function rand2
   state := update(state) -- unchanged state computation
   return swapped(state)  -- output swapped state

回答3:

Another easy, efficient, and well-understood PRNG is a Linear Feedback Shift Register. Full period is easy to achieve following the steps in the article.

EDIT:

You might consider some of the techniques developed for Format-Preserving Encryption. I believe these can be readily adapted to generate a permutation.

回答4:

Just because you do not need cryptographic strength, that does not mean you cannot borrow some ideas from cryptography... Like the Feistel network (Luby-Rackoff construction).

The Wikipedia picture is pretty clear.

If you pick a simple and fast F -- it does not even need to guarantee unique output -- then you can just feed a sequence (0, 1, 2, ..., 2^n-1) to a few rounds of the Feistel network. Since the construction is reversible, this guarantees that the output never repeats.

Sample code for 32 bits:

#include <stdint.h>
#include <stdio.h>

/* Just some fixed "random" bits... */
union magic {
    double d;
    uint16_t n[4];
};

const union magic bits = { 3.141592653589793238462643383 };

static uint16_t
F(uint16_t k, uint16_t x)
{
    return 12345*x + k;
}

static uint32_t
gen_rand(uint32_t n)
{
    uint16_t left = n >> 16;
    uint16_t right = n & ((1UL << 16) - 1);

    for (unsigned round=0 ; round < 4 ; ++round) {
        const uint16_t next_right = left ^ F(bits.n[round], right);
        const uint16_t next_left = right;
        right = next_right;
        left = next_left;
    }

    return (((uint32_t)left) << 16) + right;
}

int
main(int argc, char *argv[])
{
    for (uint32_t n = 0 ; n < 10 ; ++n) {
        printf("gen_rand(%lu) == %08lx\n", (unsigned long)n,
               (unsigned long)gen_rand(n));
    }
    return 0;
}

You can mess around with the definition of F(), the number of rounds, etc. to suit your taste. The "full cycle" property is guaranteed no matter what you use there. In other words, if you have the loop in main go from 0 to 2^32-1, each 32-bit integer will occur once and only once, regardless of what you use for F or the number of rounds.

This does not exactly meet your stated requirement, since the input to gen_rand is not the "current random number"... The input is just the next integer. However, this does allow you to generate any element of the sequence at will (random access). And it is easy to invert if you really, really want to pass the "current random number" as input.

Pretty easy to adapt to different numbers of bits, although it does require that your R is a power of 2.

回答5:

Permuted congruential generators seem to have all the qualities you're looking for:

http://www.pcg-random.org

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

There are other varieties available at the website, including a C++ implementation intended to work with the <random> header (e.g., the distributions), a more complete C implementation, and a Haskell implementation.

回答6:

In the following link you can find an example of combined LCG. (Documents and source included) (Note: algorithm is open, but the license of the source is not open (i.e., no derivative code))

http://resource.npl.co.uk/docs/science_technology/scientific_computing/ssfm/documents/wh_rng_version096.zip

You might even try this 7-stage XORshift RNG example:

https://gist.github.com/709285