Why my linear congruential generator generate low quality random numbers?

Question

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.

Answer 1

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.