13 Defining New Generators

More complex changes may be made by deriving new generators from the abstract classes. At this level of complexity you may have to create a token class to deal with saving and restoring the generator's state. The most knowledgeable programmers may wish to create entirely new types of PRNGs by creating new abstract classes derived from RandomGenerator.

13.1 General Design Considerations

Many of the design criteria for this library are not immediately obvious. Most of these criteria evolved as the library grew and changed. Some of the design criteria are general:

1. Reduce compiler dependencies (portability).
2. Must be easy to begin using.
3. Must be extensible.
4. Should supply functionality that would be hard for average programmer to provide for him/herself.
5. Must be hard to misuse.

These criteria relate to most class libraries and should not be too difficult to understand. The main instrument to ensure portability in the library code is the environ.h file. This file contains macros which allow the rest of the code to be defined without consideration of certain compiler deficiencies. These deficiencies include handling of exceptions, the new C++ casting styles, differing return types on overridden member functions, the bool type, and the string class. At the time this library was written, not all compilers supported all of these C++ language features. In addition, the environ.h file also contains macros to exploit compiler features that may be helpful. The Gnu C++ compiler's support of 64-bit integers is abstracted and available in the environ.h file.

Where possible, ThinAir uses the const keyword to declare any member function which does not logically modify an object. Any member data which never changes is also declared const. I have found that this keyword has reduced certain kinds of errors in my code. In addition, it is easier for another programmer to determine some of my intent by seeing which functions promise not to change the object.

On a slightly different note, the ANSI C++ standard has added a new keyword, explicit. The compiler is forbidden to use any constructor marked with this keyword in an implicit conversion from one type to another. This compiler behavior only applies to constructors with just one argument. In the ThinAir library, there are no classes which reasonably should be implicitly converted in this fashion. I have, therefore, been careful to use the macro EXPLICIT everywhere the explicit keyword would apply. Any compiler which supports this new keyword uses it, in all other cases the macro disappears.

Other design criteria relate to the specific problem space.

1. It must be easy to change generators without extensive recompilation.
2. All generators in the library must have equivalent interfaces.
3. You must be able to reset generator to initial state.
4. You must be able to save/restore state of generator.
5. It would be nice to be able to save/restore generator state from a file.
6. A generator must provide a range of integer values for use.
7. A Generator must be capable of providing doubles in the range [0.0,1.0).
8. Copying a generator is not important to the design.
9. Assignment of one generator to another makes little or no sense.
10. Cloning a generator may be a useful function.

In order to meet the first two criteria, I have derived every generator in the library, either directly or indirectly, from the RandomGenerator class. A programmer can then assign the address of any generator to a RandomGenerator pointer and none of the code needs to know which particular generator is used. (Except of course the code at the point of creation.) More importantly, if you wish to change generators, only the module containing the code creation needs to be recompiled.

The next criterion is provided by the Reset() member function which restores any generator to its initial state. The next two criteria are handled by the RandGenToken classes. These classes allow the current state of the generator to be stored. (See [3] for more information on the Token design pattern.) In spite of the fact that each kind of generator requires saving/restoring different amounts of state, the RandGenToken classes abstract the concept very neatly. A token can only be generated by a generator type which can use it. The token classes contain support for reading and writing themselves on streams. One important thing to remember about Tokens is that any time you create a new generator that has a different amount of state than its parent, you must create a Token class for it as well.

The main purpose of the generator classes is described by criteria 5 and 6. The member functions Number() and LimitedNumber() provide generator output in the form of integers in some range. The FloatNumber() member function provides doubles in the range [0.0,1.0).

In order to simplify design and debugging, I decided that the generators would not need to be copied or assigned. (Criteria 7 and 8) In order to prevent the compiler from building default versions of these functions, I followed James Coplien's advice from page 45 of [1]. Both of these member functions are declared private and not defined in the classes in the ThinAir library.

As the construction of the generator classes continued, I found a few places where copying a generator could be useful in very limited circumstances. In order to make this copying well-defined, I added the ReCreate() member function (which recreates the current generator in its initial state) and the Clone() member function (which duplicates the current generator and its state. If you create a new generator which changes the functionality of its base class in any way, you must define a ReCreate() function for it. The default Clone() member function supplied by RandomGenerator should be sufficient for almost all classes in the ThinAir library.

13.2 Instantiating a new concrete generator

The text describes this generator as a linear congruential generator without a constant term. This narrows our choices down to the MultConRandGen class and the MultConModRandGen class. Since the required modulus is the default for the MultConRandGen class of generators, we use this class as a base. The derived class only needs a new constructor since all other member functions do exactly what is needed. It seems reasonable to allow the users of the new generator to specify a seed at construction time, so all we need to fill in is the multiplier. So we derive MarsagliaMCRandGen publicly from MultConRandGen. The constructor is defined as having a single argument, seed. The constructor must pass our multiplier and the user's seed to the constructor for the base class. The body of the constructor does nothing. The only other thing to remember is to make the constructor for MarsagliaMCRandGen public so that this class can actually be constructed.

The actual MarsagliaMCRandGen class is defined in the file erndmcon.h.

  class  MarsagliaMCRandGen : public MultConRandGen
   {
  public:
    explicit MarsagliaMCRandGen( size_rand seed=1 ) :
       MultConRandGen( 69069UL, seed )
     { }
   } ;

13.3 The RNGFuncAdaptorRange Function Object

To build this class, we need data members for storing the limits, and the PRNG object pointer. We also need to define the operator() member function, a constructor, and a destructor. The destructor is the easy one. All it needs to do is delete the PRNG object pointer. The constructor must store the parameters for use by the operator() member function. The easiest way to define the operator() member function uses the LimitedNumber() member of the PRNG object. Unfortunately, the upper and lower limits are not as useful for LimitedNumber() as a lower limit and a range. After realizing this, I redesigned the class to store the range instead of an upper limit. The resulting class definition is shown below.

  class RNGFuncAdaptorRange
   {
    RandomGenerator  *myRNG;
    const size_rand    myLower;
    const size_rand    myRange;

  public:
    RNGFuncAdaptorRange( RandomGenerator *pRNG, size_rand lower,
                         size_rand upper ) :
     myRNG(pRNG), myLower(lower), myRange(upper-lower+1)
     { }
    ~RNGFuncAdaptorRange( void ) { delete myRNG; }

    size_rand operator()( void )
     {
      return myLower + myRNG->LimitedNumber( myRange ));
     }
   } ;

This class is easy to use. Let's say you wanted to design a class to emulate a six-sided die. Let's also say we want to base it on the MarsagliaMCRandGen class described in the last section. The following code fragment shows how to construct the die object and roll it 3 times.

int main( void )
 {
  RNGFuncAdaptorRange  die( new MarsagliaMCRandGen( 5 ), 1, 6 );

  for( int i=1;i<4;i++)
   {
    cout << "Roll #" << i << " = " << die() << endl;
   }

  return 0;
 }

13.4 Minor Modifications to a generator

In order to build this class, we start out by using the technique described in Section 13.2, above. This time we publicly derive the StdCRandGen class from LinConRandGen. The multiplier (1103515245) and increment (12345) were taken from the C Standard. Because we are limiting the range of output values, it is also necessary to limit the size of the seed. This change is handled as the parameters are passed to the base constructor.

Since the output range is modified in the StdCRandGen class, we must redefine the MaxRandom() member function to return the new largest number returned by a generator of this class. Likewise, we must modify the IntSeed() member function so that it only uses the lower 15 bits of seed. Next, we need to actually implement the difference between this class and its base class. The Number() member function needs to be modified to return 15 of the upper 16 bits of the current seed.

The last change needed to this class is a new ReCreate() function. This is the change that is easiest to forget. Since we are changing the functionality of the class and not just providing parameters, we need a new ReCreate() function. The entire class is shown below:

  class  StdCRandGen : public LinConRandGen
   {
  public:
    EXPLICIT StdCRandGen( size_rand seed=1 ) :
      LinConRandGen( 1103515245L, 12345L, (seed&0x7fff) )
      { }
    virtual  void       IntSeed( size_rand seed )
     {
      LinConRandGen::IntSeed( (seed & 0x7fff) );
     }
    virtual size_rand   Number( void )
     {
      //  The example uses ((Number/65536)
      return ((unsigned)(LinConRandGen::Number() >> 16) & 0x7fff);
     }
    virtual  size_rand   MaxRandom( void ) const { return 0x7fff; }
    virtual  DIFFRET(StdCRandGen)  *ReCreate( void ) const
     {
      return new StdCRandGen( Seed() );
     }
   } ;

13.5 Deriving the Quadratic Congruential generator

In keeping with our need-to-know policy on member data, all of these values are declared private. Since the values will never change, they are also declared constant. It is possible that someone may want to derive from this class one day, so we provide the protected accessor functions QuadMultiplier(), LinMultiplier(), and Increment() to allow read-only access to this data.

As part of our design criteria, we do not allow copying or assignment of generator objects. This means we need to declare private prototypes for the copy constructor and assignment operators. These member functions have no implementation.

The public interface of the class contains only four functions: the constructor, destructor, ReCreate(), and Number(). All of the other public functions are provided by either CongruentialRandGen or RandomGenerator. The constructor and destructor for this class are both quite simple and are, therefore, defined inline. Likewise ReCreate() is a simple function, so it is also declared inline in the header.

The class declaration in randquad.h now looks like this:

  class  QuadConRandGen : public CongruentialRandGen
   {
  private:
    const unsigned long   myQuadMultiplier;
    const unsigned long   myLinMultiplier;
    const unsigned long   myIncrement;

  private:
    // protect the = operator and copy constructor so they cannot be used.
    QuadConRandGen& operator=( QuadConRandGen const & );
    QuadConRandGen( QuadConRandGen const & );

  protected:
    // access methods for private data.
    unsigned long   QuadMultiplier() const { return myQuadMultiplier; }
    unsigned long   LinMultiplier()  const { return myLinMultiplier; }
    unsigned long   Increment()      const { return myIncrement; }

  public:
    QuadConRandGen( unsigned long quad, unsigned long lin, unsigned long incr,
                     size_rand seed=1 )
     : CongruentialRandGen(seed), myQuadMultiplier(quad), myLinMultiplier(lin),
       myIncrement(incr)
     { }

    virtual   ~QuadConRandGen() { }

    virtual DIFFRET(QuadConRandGen)  *ReCreate( void ) const
     {
      return new QuadConRandGen( QuadMultiplier(), LinMultiplier(),
                                 Increment(), Seed() );
     }

    virtual  size_rand   Number( void );
   } ;

Now we need to provide an implementation for the remaining function in the class. In the implementation file RandQuad.cpp, we define the Number() member function. This function just implements the equation listed in the documentation from Section 7.9. The Number() function is shown below.

size_rand   QuadConRandGen::Number( void )
 {
  size_rand  RandNum = QuadMultiplier() * CurrSeed() * CurrSeed()
                     + LinMultiplier()  * CurrSeed()
                     + Increment();
  SetCurrSeed( RandNum );

  return RandNum;
 }

The member functions CurrSeed() and SetCurrSeed() are provided by the CongruentialRandGen base class. I am also using this class's own accessor functions for the private data, even though that is not required. I have found that this practice simplifies my task if I need to derive a new class from this one. By accessing the private data through the accessor functions, I have made more certain that I have provided all of the access that a derived class needs. Sometimes, I have found that a derived class needs more access. But I make fewer mistakes, if I do it this way.

13.6 Creating a generator from scratch

In this section, we cover the creation of the CompilerRandGen. Unlike the other generators in this library, CompilerRandGen just wraps an interface around the Standard Library's generator. This means that the class cannot take advantage of the code from any other class. The main design criterion is simple: Provide as much of the ThinAir functionality and interface as possible for the Standard Library PRNG.

A quick look at the RandomGenerator interface shows that we need to implement several functions. We must create the following functions:

• RandomGenerator      *ReCreate() const;
• void      Reset();
• size_rand      IntSeed( size_rand seed );
• size_rand      MaxRandom() const;
• size_rand      Number();
• size_rand      LimitedNumber( size_rand limit );
• RandGenToken      CreateToken() const;
• int      SetToken( const RandGenToken &pToken );

Of these, only LimitedNumber() is truly optional. But, since the standard implementation already supports a function that does this exactly, we will use that function to make the CompilerRandGen mimic the standard PRNG as far as possible. The other issue we must consider early is the need for a Token class. This Token must be capable of storing as much of the state of the generator as we can manage.

Let's start by matching the requirements and interface of the standard PRNG with those of a ThinAir PRNG. This would give us a starting point for the new class. As described in Section 5.2, the stardard PRNG's interface/implementation consists of four functions (or function-like macros) and a constant. This interface is reproduced below.

• RAND_MAX
• size_rand      rand();
• size_rand      random( size_rand lim );
• size_rand      srand( size_rand seed );
• void      randomize( void );

It's easy to see where some of these items connect to the ThinAir interface. Obviously, MaxRandom() should be implemented using RAND_MAX. Number() should just be a call to rand(). LimitedNumber() should be defined as a call to random(). Finally, IntSeed() is defined as a call to srand(). The randomize() function does not appear to have any use for our purposes so we'll drop it for now.

Before we get to the rest of the class, a few words are in order about abstract PRNG classes. If this had been an abstract class, we would not have implemented the Number() or LimitedNumber() member functions. We might not have implemented IntSeed() either. We also would not implement the ReCreate() function described later. In general, none of these functions can have a reasonable implementation for an abstract class.

Okay, now that the preliminaries are out of the way, let's get down to the part of the design that separates ThinAir PRNGs from the crowd. The unimplemented functions are the constructor, ReCreate(), Reset(), CreateToken(), and SetToken().

Let's start with the constructor. The constructor needs to save any object specific data and prepare the generator for use. The only object-specific data we have for this generator is the initial seed value. The constructor needs a single argument and the class needs a private data member to store that seed. As stated in the ANSI Standard ([7]), the default value for the constructor argument is 1.

In keeping with our need-to-know policy on object data, we must create accessor functions (Seed() and SetSeed( size_rand seed )) for this piece of data. Both of these methods are declared protected because only derived classes should need to access them.

Now we have enough information to build the ReCreate() and Reset() functions. ReCreate() uses the new operator to create a new CompilerRandGen, passing it the private seed value. Reset() simply calls srand() with the private seed value.

Most implementations of the rand() function retain 32 bits of state even though the seed values are limited to 16 bits. In order to manage the Token classes we have to add another data item to the CompilerRandGen. The myCount data member stores the number of times rand() is called. We now need a protected data access member Count().

In order to define the CreateToken() and SetToken() functions, we must first define the CompilerRandGenToken token class as a derivative of RandGenTokenImpl (found in randgen.h and randgen.cpp). The only piece of information the token stores is the initial seed. This makes the implementation straightforward. (See randcomp.cpp for the details.) Now CreateToken() is defined as newing an object of type CompilerRandGenToken and passing it to a brand new RandGenToken object which the function returns. SetToken() accepts a RandGenToken reference, from which it extracts the CompilerRandGenToken. From this token it sets its internal data, calls rand() the appropriate number of times and exits.

As with all of the PRNG classes, we handle a little coding hygiene to make the classes complete. As discussed in Section 13.1, we need to prevent copying and assignment of objects of this class. To this end, we declare the assignment operator and copy constructor private and don't implement them.

The complete class interfaces for CompilerRandGen and CompilerRandGenToken are shown below. The implementations can be found in randcom.cpp.

  class  CompilerRandGen : public RandomGenerator
   {
  private:
    size_rand   mySeed;

  private:
    // protect the = operator and copy constructor so they cannot be used.
    CompilerRandGen& operator=( CompilerRandGen const & );
    CompilerRandGen( CompilerRandGen const & );

  protected:
    size_rand      Seed( void )     const { return mySeed; }
    void           SetSeed( size_rand seed ) { mySeed = seed; }
    unsigned long  Count( void )    const { return myCount; }
    void           RunTo( unsigned long cnt );

  public:
    explicit CompilerRandGen( size_rand seed=1 ) : mySeed(seed), myCount(0L)
     { srand((unsigned)seed); }
    virtual   ~CompilerRandGen() { }

    virtual DIFFRET(CompilerRandGen)  *ReCreate( void ) const;

    virtual RandGenToken  CreateToken( void ) const;
    virtual int     SetToken( const RandGenToken &Token );

    virtual void    Reset( void );

    virtual  void        IntSeed( size_rand seed );
    virtual  size_rand   MaxRandom( void ) const;
    virtual  size_rand   Number( void );
   } ;


class  CompilerRandGenToken : public RandGenTokenImpl
 {
public:
  virtual   ~CompilerRandGenToken( void ) { }

  virtual _STRING  CreateInitString( void ) const;
  virtual int   Initialize( istream &InitStream );
  virtual CompilerRandGenToken   *Clone() const
   {
    return new CompilerRandGenToken( mySeed, myCount );
   }

  void       Print( ostream &os ) const
   {
    os << '(' << mySeed << ',' << myCount << ')' << flush;
   }
  void       Read( istream &is )
   {
    char  dummy;
    is >> dummy >> mySeed >> dummy >> myCount >> dummy;
   } 

private:
  friend class CompilerRandGen;
  CompilerRandGenToken( size_rand Seed, unsigned long Count )
   : mySeed(Seed), myCount(Count)
   { }
  size_rand       mySeed;
  unsigned long   myCount;
 } ;

© 1997 G. Wade Johnson. All rights reserved.
http://www.anomaly.org/ThinAir/defining.html