CODEWITHSUNDEEP
algorithmrandom
Mathematics Lover
Mathematics Lover

Reputation: 195

Generate a random vector from a linear congruential RNG

If I'm having a linear congruential generator such that every time given a specific seed, I can know exactly we can generate a fixed sequence of pseudorandom numbers that are known to be uniformly distributed between [1, K], how should I use such an RNG to generate a M-dimensional random vector that is evenly distributed between [1, K^M]?

Upvotes: 0

Views: 165

Answers (2)

sh1
sh1

Reputation: 4731

If you're satisfied with LCG for everything but the M-dimensional case, then the most basic solution would be to use M separate seeds for M separate generators. This can at least ensure the elements of a given vector are independent (to the limits of your seeding algorithm).

However, what you probably really want is a PRNG with a state at least M*log_2(K) bits which can guarantee some mixing between all parts of the vector. If that's more than 64 bits then using an LCG for this seems like a lot of effort to implement something which will be weaker than a lot of simpler solutions.

If M is constant and not unreasonably large then you might look at xorshift, multiply-with-carry, or WELL. Otherwise you're probably stuck with using a well-known huge-period generator or a cryptographic algorithm and turning a blind eye to the theoretical limitations.

Upvotes: 1

MattG
MattG

Reputation: 1426

I don't know what programming language you intend to use or what the range of K and M is, but if K is a power of two, you can simply append the binary representation of M pseudo-random numbers to get one pseudorandom number uniformly distributed over [1, K^M]. If K is not a power of two, you can use some sort of partitioning function or re-roll for certain values to construct the bits of your [1, K^M] distributed numbers.

Upvotes: 0

Related Questions