4
$\begingroup$

I am implementing an arbitrary bits random number generator (in [$0,2^n$)) and also want to ensure that the generator always generate unique numbers until all possible numbers generated, so I implement it using LCG (I also considered the linear feedback shift register method, but it cannot be scaled to arbitrary number of bits because the dependence on primitive polynomial).

The algorithm as follows:

  1. create an array length $n$
  2. using random bits to fill the array. This array is $X_0$
  3. generate the second length-$n$ array ($a$) and fill in three lowest bits with $1,0,1$ (to ensure $a-1$ is divisible by $4$) and use random bits to fill other cell.
  4. generate the third length-$n$ array ($c$) and set the lowest bit to $1$ (other cell random), so this array is odd and relatively prime to $m=2^n$.
  5. Generate random numbers by $X_n=(aX_{n-1}+c) \mod m$ ( the mod is by keeping only $n$ bits in add and multiply operations).

As the result, this LCG's repeating period is always maximum, however, I find that the $i$-th lowest bit always have the repeating period of $2^{i}$. For example, the lowest bit is in sequence of 1,0,1,0,..., the second lowest bit is like1,0,0,1,1,0,0,1,..., and so on. This makes me wonder if somewhere wrong in my implementation or it is actually the weakness of LCG. I tested the rand in C and did not find this pattern, so I guess this problem is from my implementation. Can anyone gives me some advice about this? Thanks.

$\endgroup$
  • 3
    $\begingroup$ This a feature of LCG. Your rand() implementation should use the high-order bits of $X_n$ not the low order bits, and do not use $X_n \bmod r$ or $rand() \bmod r$ do get random values from $0,1,\dots r-1$ because this introduces a bias. $\endgroup$ – gammatester Oct 14 '17 at 9:04
  • 3
    $\begingroup$ LCG output has a lot of structure as first noticed 50 years ago: G. Marsaglia. "Random numbers fall mainly in the planes." Proceedings of the National Academy of Sciences 61, no. 1 (1968): 25-28. (online). My advice: Don't use an LCG but a modern PRNG e.g. Philox: Salmon, John K., Mark A. Moraes, Ron O. Dror, and David E. Shaw. "Parallel random numbers: as easy as 1, 2, 3." In 2011 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp. 1-12. IEEE 2011 $\endgroup$ – njuffa Oct 15 '17 at 4:14
1
$\begingroup$

This is simply how LCG works.

You can reduce the problem for your application by simply exclusive-or-ing some of the high bits over some of the low bits in the output (but do not use this modified output as the next input to the generator loop). This will retain the full period of the counter, but it improves the period of the low bits to be the same period as the high bits.

It's not a very good tweak and still has substantial flaws as a PRNG, but it gets a basic job done for cheap. You can make it a lot better by multiplying by another odd constant and doing another shifted exclusive-or, but it depends on what you really need and how much time you want to spend on it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.