Re: Which Bits to Use From a Linear Congruential Pseudo-Random Number Generator?

In article <bqOdnYdqYsVWWkfVnZ2dnUVZ_szinZ2d@xxxxxxxxxxxx>,
"David T. Ashley" <dta@xxxxxxxx> wrote:
I'm developing a small embedded system and plan to implement an LCG as
described here:

http://en.wikipedia.org/wiki/Linear_congruential_generator

The function I have in mind is

X(n+1) = (1664525 * X(n) + 1013904223) mod 2**32

which naturally lends itself to a 32-bit seed.

The random number function will only return 16 bits of the 32-bit seed ...
the question is which 16 bits to choose?

The web page hints that the least significant bits will have a shorter
period than 2**32 ... should I choose bits above those ... but how should I
decide which ones?

In linear congruential random number generators such as you describe,
bit k has a period of 2^{k+1}. That is, bit 0 has a period of 2, bit
1 has a period of 4, bit 2 has a period of 8, etc. Thus, bit 31 has
a period of 2^32. In other words, you want to use the highest order
bits possible.

Rob Johnson <rob@xxxxxxxxxxxxxx>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
.

Relevant Pages