21.6 Random Numbers

Closely tied to sorting and searching is the generation of random numbers. Often, random numbers are used to put lists out of order. They offer the opportunity to create surprise. They allow you to squeeze more information onto a single page by choosing content randomly for each request. You see this every day on the Web in the form of quotes of the day, banner ads, and session identifiers.

There are two important qualities of truly random numbers: Their distribution is uniform, and each successive value is independent of the previous value. To have a uniform distribution means that no value is generated more often than any other. The idea of independence is that given a sequence of numbers returned by the generator, you should be unable to guess the next. Of course, we can't write an algorithm that really generates independent values. We have to have some formula, which by its nature is predictable. Yet, we can get pretty close using what is called a pseudorandom number generator. These use simple mathematical expressions that return seemingly random numbers. You provide a starting input called a seed. The first call to the function uses this seed for input, and subsequent calls use the previous value. Keep in mind that a seed will begin the same sequence of output values any time it's used. One way to keep things seeming different is to use the number of seconds on the clock to seed the generators.

The standard C library offers the rand function for generating random numbers, and PHP wraps it in a function of the same name. You pass upper and lower limits, and integers are returned. You can seed the generator with the srand function, or just let the system seed it for you with the current time. Unfortunately, the standard generator on some operating systems can be inadequate. Fortunately, Pedro Melo added a new set of functions to PHP that use the Mersenne twister algorithm.

I won't attempt to describe the algorithm behind the Mersenne Twister algorithm because it's out of the scope of this text. You can visit the home page for more information <http://www.math.keio.ac.jp/~matumoto/emt.html>. You can read a careful description there to convince yourself of the validity of the algorithm if you wish.

Listing 21.8 is a very simple example that generates 100 random numbers between 1 and 100, using the mt_rand function. It then computes the average and the median. If the distribution of numbers is uniform, the average and median will be very close. The sample set is really small, though, so you will see lots of variance as you rerun the script. The output is shown in Figure 21.5.

Listing 21.8 Getting random numbers

<?php
    // Seed the generator
    mt_srand(doubleval(microtime()) * 100000000);

    // Generate numbers
    print("<h3>Sample Set</h3>\n");
    $size = 100;
    $total = 0;
    for($i=0; $i < $size; $i++)
    {
        $n = mt_rand(1, $size);
        $sample[$i] = $n;
        $total += $n;
        print("$n ");
    }
    print("<br>\n");

    print("Average: " . ($total/$size) . "<br>\n");

    sort($sample);
    print("Median: " . ($sample[intval($size/2)]) . "<br>\n");
?>