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:

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.

Answer 1

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.