1
$\begingroup$

On a practice exam for a course on stochastic simulations I encountered the following question:

Show that the least significant $n$ bits must repeat with a period $2^n$ for a congruential random generator with a period $2^m$ where $m > n$.

I couldn't find an answer on how to do this anywhere. How can I shows this? Is it just that the $n$ bits can only generate $2^n$ numbers?

  • 0
    Try your generator with, say, $x_0 = 1023$, $n=5$, $m = 32$. What are the values of $x_1$, $x_2, \ldots$? Hint: computation by hand is easy, especially if you represent the $x_i$ as $32$-bit words.2011-12-19

1 Answers 1

1

In Chapter 3 of D. E. Knuth's The Art of Computer Programming, vol. 2, (1st edition), it is shown that the low-order $n$ bits repeat with a period of $2^n$ or less for any choice of the multiplier $a$. If you want to prove that the period is exactly $2^n$, then you may need to place restrictions on $a$. You may also need to place restrictions on the modulus $c$ because Knuth also says that if the modulus $c$ is $2^m$ (as in your comment), then the low-order bits are not quite as random as is possible with other choices of $c$.

  • 0
    In short: using the least significant bits for generating "new" random numbers isn't that good an idea. :)2011-12-20