Columns

Questions & Answers

More on rand ( )

Pete Becker

Pete Becker is Senior QA Project Manager for C++ at Borland International. He has been involved with C++ as a developer and manager at Borland for the past six years, and is Borland's principal representative to the ANSI/ISO C++ standardization committee.

Q

How do I write a function to simulate rolling a die? That is, I want to get numbers from 1 to 6 with equal probability.

A

The key to this sort of simulation is the function rand. According to the ANSI C standard, rand "computes a sequence of pseudo-random integers in the range 0 to RAND_MAX." In my September column I talked about the behavior of rand and srand. This time I'll talk about how to actually use rand in real programs.

Once you've seen the definition of rand, the obvious way to use it to simulate rolling a die is to call it and then adjust the result so that it fits in the desired range. Most people, when they first try this approach, come up with code something like this:

#include <stdlib.h>
#include <stdio.h>

int roll( void )
{
const int min_val = 1;
const int max_val = 6;
const int range = max_val-min_val+1;
return rand()%range+min_val;
}

int main( int argc, char *argv[] )
{
int n;
if( argc != 1 )
    srand( atoi(argv[1]) );
for( n = 0; n < 10; n++ )
    printf( "%2d: %d\n", n+1, roll() );
return 0;
}

Unfortunately, this technique introduces a significant distortion: it produces more low values than high ones. That effect is not significant when we're trying to roll a die because we are dealing with such a small range of generated values. For larger ranges, however, the effect will become important.

To see what the problem is, let's consider what roll would do if we had an implementation of rand that generated values evenly distributed from zero to six. The function roll as written above will translate each of these values as follows:

0 -> 1
1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> 6
6 -> 1

This means we will get twice as many ones as any other value when we roll this die. That would certainly get you thrown out of any self-respecting crap game.

The problem arises because we can't uniformly map the range of values returned by rand onto the range that we want to create with roll: rand returns seven possible values, and roll needs to produce six. The extra value that rand produces throws off the distribution. The easiest way to fix this is to throw3 away any extra values: whenever rand gives us a value we can't use we call rand again, like this:

int next_roll( void )
{
const int min_val = 1;
const int max_val = 6;
int result = rand();
while( result < min_val || result > max_val )
     result = rand();
return result;
}

In our hypothetical case where rand returns values from zero to six this technique works fine. In more general cases, however, it is horribly inefficient; it will typically throw away far more values than it keeps. If rand produced values from 0 to 32,767 this algorithm would have to call rand about five thousand times, on average, for every value that it generated.

With a little thought we can do much better. Rather than restrict the values that we use to the range we're looking for, we should restrict them to a range that can be uniformly mapped over the range we're looking for. Numbers ranging from one to twelve work fine: we can map them into the range we need by mapping the values from one to six directly, and mapping the values from seven to twelve down to one to six. This would let us use twice as many generated values, and would reduce the inefficiency of the algorithm significantly. More generally, we can extend this technique a great deal further, and only restrict our input range to the largest range that maps uniformly to the range we're looking for. With this change, roll ends up looking like this:

int roll( void )
{
const int min_val = 1;
const int max_val = 6;
const int range = max_val-min_val+1;
const int max_input_value =
    (long)RAND_MAX+1 - ((long)RAND_MAX+1)%range;
int temp = rand();
while( temp > max_input_value )
    temp = rand();
return temp%range+min_val;
}

If you use this implementation of roll in our earlier program, compile it with Borland's compiler and run it with no command-line arguments, you'll get this result:

1: 5
2: 5
3: 3
4: 5
5: 5
6: 2
7: 4
8: 2
9: 5
10: 5

With all those five's in there it sure looks like this die is loaded, but this is a rather small sample. Table 1 shows the results of several runs of the same program with different command-line arguments.

An honest die would produce a five an average of once in six rolls, or sixteen and two-thirds times out of one hundred. If you look at the entire table you'll see that five came up sixteen times in the one hundred entries. That's about as close as you can get to the theoretical value.

If we count the number of times each possible value comes up we get the distribution shown in Table 2.

I won't present all the data here, but when I rolled this die 10,000 times I came up with the distribution in Table 3.

As you can see, the distribution of values is quite uniform. If you are concerned about the slight variances that still remain and you know something about statistical analysis you can look at whether these variances indicate that the process isn't truly random. For an adventure game, though, this is certainly good enough.

Q

Are there such things as private virtual functions? I want to design an abstract base class with some pure virtual functions that should be private in the derived class. Do I make the pure virtual definition private in the base class to enforce this?

A

Yes, there is such a thing as a private virtual function. All you need to do to create one is put its definition in the private section of your class definition:

class Base
{
private:
    virtual void func();
};

However, doing this does not guarantee that an overriding function in a derived class will also be private. That is, it is perfectly valid to write a derived class that looks like this:

class Derived : public Base
{
public:
    void func();
};

Despite the difference in access specifiers, Derived::func overrides Base::func. If you call func through a pointer to Base that actually points to an object of type Derived you will call Derived::func:

Base *bp = new Derived;
bp->func();    // calls Derived::func

Some people are uncomfortable with this behavior. They feel that being able to make the overriding function public somehow violates privacy. This just isn't so. Making func private in Base means that only members and friends of Base can call it. Overriding func with a public function in a derived class does not change this restriction: Base::func can still only be called by members and friends of Base.Base still has exactly the same properties as its designer originally gave it. The designer of Derived hasn't violated the design of Base by making Derived::func public.

One of the most common design mistakes software engineers make is trying to control things that they don't need to control. The designer of Base needs to decide what Base should do, and needs to tell users of Base how its behavior will be affected by derived classes that they write. As long as derived classes behave appropriately, the details of how they implement that behavior are irrelevant to the designer of Base. In short, whether the overriding virtual function is private is none of your business. Design Base correctly, and let the designer of Derived worry about getting Derived right.

Q

Do constructors and destructors have to be public? If so, why?

A

No. You are free to use whatever access specifiers are appropriate in your classes. In most cases, you'll want to make your constructors and destructors public. There are, however, situations in which you might make them protected or private.

For example, if you had a class that shouldn't be copied, you'd probably prevent copying by making its copy constructor and its assignment operator private. Doing so makes code like this invalid:

class CannotBeCopied
{
private:
   CannotBeCopied( const CannotBeCopied& );
   CannotBeCopied& operator =( const CannotBeCopied&);
};

int main()
{
CannotBeCopied c1;
// invalid: copy constructor
// not accessible
CannotBeCopied c2(c1);
CannotBeCopied c3;
// invalid: assignment operator
// not accessible
c3 = c1;
}

You should make a constructor protected if it is intended only for use by derived classes. For example, a derived class might specialize the base class in ways that can be specified in the constructor, but shouldn't be available to outside users.

class TreeIterator
{
protected:
    enum Order { PreOrder, InOrder, PostOrder };
    Base( Tree *, Order );
};

class PreOrderIterator : private
   TreeIterator
{
public:
   PreOrderIterator( Tree *tree ) : TreeIterator( tree, PreOrder ) {}
};

In addition, if you make a destructor protected then users cannot create auto objects or global objects of your class. However, they can create auto objects and global objects of types derived from your class. This sort of thing might occasionally be useful.

If your class has only a private destructor then there is no valid way for users to destroy objects of your type. Like a protected destructor, this also prevents users from creating auto objects. But defining only a private destructor also makes it impossible for users to derive from your class, because their classes will always have destructors, whether explicit or compiler-generated, and those destructors will try to call your destructor. Since their destructors cannot access yours, they will not compile. Of course, members of your class can invoke the destructor.

Just as in any other aspect of design, you should think about the sort of thing you expect users of your class to do. If you need to prevent users from doing things that are ordinarily done with classes, access control may help you.