[cs13001] on random number generators

[Mikhail Nesterenko]

CSI students,

This is due to one of the students in the course. The information is
certainly above what would be required on tests.

Remember I mentioned that numbers generated by rand() function are in
fact not truly random? If you keep invoking rand() in your program,
then eventually the sequence of returned numbers is going to
repeat. Hence, the numbers are called "pseudo-random numbers", and the
algorithm coded inside rand() is called pseudo-random number
generation algorithm.  In particular, Microsoft Visual Studio uses
Linear Congruental Generator (LCG) algorithm.

The period of this repetition is quite large, so for most purposes,
including the games you code for this course, the quality of
pseudo-random numbers is quite good. One interesting quirk of LCG is
that the period of the repetition of the lower digits of the generated
psedo-random numbers is less than of the numbers overall. That is,
they will repeat sooner. See more information on that in this wiki
page:

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

In class, I described the idiom of limiting the range of the random
number with a remainder operator. This technique uses the lower digits
of the generated number. Therefore, if the pseudo-random generation
algorithm is LCG, this technique decreases the quality of the
generated sequence.

The quality of the obtained results is still quite good for most
applications so the described idiom is used often. 

However, here is a question for you. Knowing RAND_MAX, the constant
that states the largest possible generated pseudo-random number, how
would you get the highest digits of this number for your limited range
(rather than the lowest)?

Thanks,
-- 
Mikhail