Dr. Dobb's Journal - April 2008 - (Page 46)

d04orlov_p5ds 2/19/08 11:35 AM Page 46 Core Technology RANDOM NUMBERS IN A RANGE USING GENERIC PROGRAMMING 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; }; continued from page 44 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 ::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 last); return rnd % max; } Listing Three template struct traits; template struct traits { static const unsigned max_value = UINT_MAX; }; template struct traits { static const int max_value = INT_MAX; }; Listing Four template { static template { static struct gcd const uintmax_t value = gcd ::value; }; struct gcd 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 struct random_traits { private: static const value_t M = traits ::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 ::value; static const random_dispatch::dispatch_t dispatch = rem == 0 ? random_dispatch::NO_LOOP : (gcd == 1 ? random_dispatch::RETRY_SAME : random_dispatch::REDUCE_MAX); }; and in the next iteration draw a value in the corresponding bucket using m=rem. What’s problematic in this solution is that the conditions for its application are quite rare because it requires that rem divides m. It can happen—with a value_t type of 10 bits, two possibilities are m=768 and m=320—however, it is possible to do a little better using the Greatest Common Divisor (GCD) algorithm. Recall that the GCD algorithm computes the maximal number that divides its two arguments, in logarithmic number of arithmetic operations. Let’s return to m=684 and rem=340. Both are divisible by 4 (which is the GCD). Thus, if rnd is rejected in the first loop iteration, you can find out in which quarter of the remainder values rnd is located, map it to the corresponding quarter of values in the [0,m–1] range, and let m=684/4=171 in the next iteration. Then, the probability of rejection becomes 1/6 instead of 1/3 (and can in general drop to a much lower value). It turns out, however, that for randomness sources that are only moderately expensive, the GCD computation cancels any running time benefit attained by reducing the expected number of calls to next(). If you are writing this code for a library, you could specify that it assumes usage with only “expensive” random-number generators, or implement memoization. However, in the first case, the code’s generic nature suffers, and in the second case, a penalty is incurred on users who don’t need perfect distribution of values in the [0,m–1] range. This gloomy situation does have a winwin solution if you are using a language that allows compile-time computations (C++, for instance), and if you are willing to limit the approach outlined earlier to values of m known at compile time. 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. 46 Dr. Dobb’s Journal l www.ddj.com l April 2008 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - April 2008

Dr. Dobb's Journal - April 2008 Contents Hmmmm Alia Vox Developer Diaries Dr. Dobb's Excellence in Programming Award Conversations Fast String Search on Multicore Processors The Byzantine Generals Problem Optimizing Math-Intensive Applications with Fixed-Point Arithmetic Random Numbers in a Range Using Generic Programming The Agile Edge Effective Concurrency Swaine's Flames

Dr. Dobb's Journal - April 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.