Alex Rivera | Logout

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

Asked 2010-08-27T11:30:00.130
13

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 '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 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.

algorithm random numerical-methods
Edit
Report

1 Answer

12

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.

answered 2011-06-10T01:50:36.803

Your Answer