Linear congruential generators

The linear congruential generator is defined in the <boost/random/linear_congruential.hpp> header. The fundamental equation of this generator is:

where is both the state of the generator and the random number. All of the parameters of the generator are user-adjustable by passing parameters to the template which defines the generator.

The linear congruential generator however works very poorly unless specific parameters are used, and it is therefore recommended to use one of the predefined generators:

• , and is the so called minimum standard generator, available as minstd_rand0
• , and available as minstd_rand

A simple example of using the linear congruential generator from boost is below:

#include <iostream>
#include <boost/random/linear_congruential.hpp>

int main(void)
{
  boost::minstd_rand gen;
  
  const size_t n=10;
  for(size_t i=0; i<n; ++i)
  {
    std::cout<<gen()
	     <<std::endl;
  }
}

Since the initial state of the generator is always the same (it is one of the template parameters), the output of this program is exactly the same every time you run it.

There are a few important points to note about linear congruential method and the minimum standard generators which are described in the sections below.

Short cycle length

The cycle length of the linear-congruential minimum standard generator is far too short for more involved calculations and therefore it should not be used unless you are really sure you do not need a long sequence.

The following program illustrates how quickly the linear congruential minimum standard generators will get back to its original state:

#include <iostream>
#include <boost/random/linear_congruential.hpp>

int main(void)
{
  boost::minstd_rand gen;
  const boost::int32_t first=gen();
  while (gen() != first)
  {
    // Do nothing, just want to see how long it takes to get back to
    // the first number
  }
}

on a modern PC this program completes in less than 20 seconds.

Sensitivity to algorithm parameters

As mentioned above, the linear congruential generator is only reasonably good for very specific choices of the parameters of the algorithm. For other, even slightly different, parameter choices the algorithm can be very poor.

This effect is illustrated by the program below which investigates the uniformity of distribution by binning the generated random numbers into 16 bins.

#include <iostream>
#include <vector>
#include <boost/random/linear_congruential.hpp>
#include <boost/format.hpp>

// Bin each generated random number into one of 16 bins based on the
// last 4 bits of the number
template<class T> void bingen(T &gen,
                              std::vector<int32_t> &bins)
{
  int32_t n;
  const int32_t first=gen();
  while ( (n=gen()) != first)
  {
    ++ (bins[n % 16]);
  }
}

// Print the bins produced by the two algorithms
void printresults(const std::vector<int32_t> &stdbin, 
                  const std::vector<int32_t> &modbin)
{
  std::cout<<"Bin number     Standard generator    Modified generator"<<std::endl
           <<"----------     ------------------    ------------------"<<std::endl;
  for(size_t i=0; i<stdbin.size(); ++i)
  {
    std::cout<<boost::format("%10i  %12i      %12i") % i % stdbin[i] % modbin[i]
             <<std::endl;
  }
}

int main(void)
{
  std::vector<int32_t> 
    stdbins(16,0), 
    modbins(16,0);

  // This is the minimum standard generator 
  boost::random::linear_congruential
    <int32_t, 48271, 0, 2147483647, 399268537> stdgen;

  // This is a very slightly modified minimum standard generator. Note
  // that the last digit 7 in the third parameter (m) has been changed
  // to the digit 4
  boost::random::linear_congruential
    <int32_t, 48271, 0, 2147483644, 399268537> modgen;

  bingen(stdgen, stdbins);
  bingen(modgen, modbins);

  printresults(stdbins, modbins);
}

The output of this program is:

Bin number     Standard generator    Modified generator
----------     ------------------    ------------------
         0     134217727                 0
         1     134217728              4963
         2     134217728                 0
         3     134217728              4972
         4     134217728                 0
         5     134217728              4885
         6     134217728                 0
         7     134217728              4951
         8     134217728                 0
         9     134217728              5027
        10     134217728                 0
        11     134217728              4876
        12     134217728                 0
        13     134217728              4961
        14     134217728                 0
        15     134217726              5036

The first column shows the bin number, the second is the number of samples from the standard linear congruential generator that fall into each bin and the third column is the number of samples from the linear congruential generator with slightly modified parameters.

As can be seen, the standard generator with the carefully chosen values of and fills all of the bins almost exactly uniformly. The generator with a slightly changed value of however has a very un-even filling, with every other bin completely empty. It can also be seen that this second generator has a total of far fewer samples – this is because we’ve set the algorithm to stop when it detect a complete cycle in the random being generated, and the generator with modified has a very short cycle length.