Generating Full Period/Full Cycle Random Numbers or Permutations Similar to LCG but without odd/even

Question

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:

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

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

5. Sequence does not have to terribly random or secure - I do not need cryptographic randomness, just 'good' randomness or apparent randomness, without odd/even sequences.

Any thoughts appreciated - thanks in advance.

Answer 1

If odd/even alternation is your only problem, then you could either shift the lower bits out or swap the the bits around.

Answer 2

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.