### Templatized Implementation

Because all the constants computed in Listing Two need to be available at compile time, you need to replace *std::numeric_limits<...>::max()* with integer traits; see Listing Three.

GCD computation is easy with C++ templates; see Listing Four.

Now you can compute the constants that were defined in Listing Two. Because these constants are derived from *m*, the parameter to *next(max),* they are also kept in a traits structure specialized on *max*; see Listing Five.

You don't just compute *rem*, *last*, and *gcd*, but also determine the dispatch ID, which is used to select one of the three variants of *next(max)* implementations—actually, *next<max>() because* *m* is now a compile-time constant. The NO_LOOP variant is selected when there are no remainder values in the *value_t* range, and no loop is necessary. Unless a very strange platform is used, *m* is a power of 2. The RETRY_SAME variant is actually the *SimpleRange* implementation, and is selected when *m* and *rem* are relatively prime, and *m* cannot be reduced once a random value is rejected. Finally, the REDUCE_MAX variant is selected when *m* and *rem* share a common factor, which allows reduction of *m*—as in the *m=684* and *rem=340* example discussed previously. Because C++ doesn't allow partial specialization for member functions, and you need partial specialization on a dispatch ID, a private class *Dispatch* is used. Because *Dispatch* is specialized on all three values of *dispatch_t*, only a declaration is necessary for the nonspecialized template (see Listing Six).

Listings Seven and Eight show the straightforward specializations for the NO_LOOP and RETRY_SAME dispatch IDs.

Listing Nine shows the REDUCE_MAX specialization, which implements the previously described buckets-based approach, with a small variation—the remainder range is not partitioned into GCD subranges, but instead a modulo GCD value is used. That is, low-order bits of *rnd* are used instead of the high-order bits.

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; };

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; };

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); };

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; }}

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; } };

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; } };

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); } };