Random Numbers in a Range Using Generic Programming
by Michael Orlov 

Listing One

class Random
{
public:
   typedef unsigned value_t;
   Random(value_t seed) : mtrand(seed) { }
   virtual ~Random() { }
   value_t next() { return mtrand(); }
private:
   MTRand_int32 mtrand;
};

Listing Two

class SimpleRange : public Random
{
public:
   SimpleRange(value_t seed) : Random(seed) { }
   using Random::next;
   value_t next(value_t max);
};
// Implementation
SimpleRange::value_t SimpleRange::next(value_t max)
{
   const value_t M    = std::numeric_limits<value_t>::max();
   const value_t rem  = (M - (max - 1)) % max;
   const value_t last = M - rem;
   value_t rnd;
   // Once rnd is in the safe range of
   // [0 .. last], return rnd % max
   do
      // rnd <- [0 .. M]
      rnd = next();
   while (rnd > last);
   return rnd % max;
}
   

Listing Three


template <typename> struct traits;

template <> struct traits<unsigned>
{ static const unsigned max_value = UINT_MAX; };

template <> struct traits<int>
{ static const int max_value = INT_MAX; };

  
Listing Four

template <uintmax_t a, uintmax_t b> struct gcd
{ static const uintmax_t value = gcd<b, a%b>::value; };
template <uintmax_t a> struct gcd<a, 0>
{ static const uintmax_t value = a; };

 
Listing Five

namespace random_dispatch
{
   enum dispatch_t
   {
     NO_LOOP,    // rem == 0
     RETRY_SAME, // gcd == 1
     REDUCE_MAX  // gcd != 1
   };
}
template <typename value_t, value_t max>
struct random_traits
{
private:
   static const value_t M   = traits<value_t>::max_value;
   static const value_t rem = (M - (max - 1)) % max;
public:
   static const value_t last = M - rem;
   static const value_t gcd  = gcd<max,rem>::value;
   static const random_dispatch::dispatch_t dispatch =
      rem == 0 ? random_dispatch::NO_LOOP
      : (gcd == 1 ? random_dispatch::RETRY_SAME
         : random_dispatch::REDUCE_MAX);
};

  

Listing Six

class SmartRange : public Random
{
public:
   SmartRange(value_t seed) : Random(seed) { }
   using Random::next;
   template <value_t max> value_t next()
   { return detail::SmartRange::Dispatch<max>::next(*this); }
};
namespace detail { namespace SmartRange
{
   template <Random::value_t max,
      random_dispatch::dispatch_t =
      random_traits<Random::value_t, max>::dispatch>
   class Dispatch;
}}
  

Listing Seven

template <Random::value_t max>
class Dispatch<max, random_dispatch::NO_LOOP>
{
   typedef Random::value_t value_t;
public:
   static value_t next(Random& random)
   {
      // rnd <- [0 .. M]
      const value_t rnd = random.next();
      return rnd % max;
   }
};
   

Listing Eight

template <Random::value_t max>
class Dispatch<max, random_dispatch::RETRY_SAME>
{
   typedef Random::value_t             value_t;
   typedef random_traits<value_t, max> random_traits;
public:
   static value_t next(Random& random)
   {
      value_t rnd;
      // Once rnd is in the safe range of
      // [0 .. last], return rnd % max
      do
         // rnd <- [0 .. M]
         rnd = random.next();
      while (rnd > random_traits::last);
      return rnd % max;
   }
};
   

Listing Nine

template <Random::value_t max>
class Dispatch<max, random_dispatch::REDUCE_MAX>
{
   typedef Random::value_t value_t;
   typedef random_traits<value_t, max> random_traits;
public:
   static value_t next(Random& random)
   {
      // rnd <- [0 .. M]
      const value_t rnd = random.next();

      // If rnd is in the safe range of
      // [0 .. last], return rnd % max
      if (rnd <= random_traits::last)
         return rnd % max;
      // Otherwise, we have the partial random value
      // in [last+1 .. M] range, and use it if possible
      // (this can happen only once, but it doesn't
      // matter for the implementation).
      else
         return max/random_traits::gcd
            * ((rnd - (random_traits::last + 1))
               % random_traits::gcd)
            + Dispatch<max/random_traits::gcd>::next(random);
   }
};



