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

d04orlov_p5ds 2/13/08 8:56 AM Page 48 Core Technology RANDOM NUMBERS IN A RANGE USING GENERIC PROGRAMMING Listing Six class SmartRange : public Random { public: SmartRange(value_t seed) : Random(seed) { } using Random::next; template value_t next() { return detail::SmartRange::Dispatch ::next(*this); } }; namespace detail { namespace SmartRange { template <Random::value_t max, random_dispatch::dispatch_t = random_traits ::dispatch> class Dispatch; }} Approach SimpleRange SmartRange next()/next(max) 1.99976 1.50794 Time 1.30s (0.53s w/inlining) 0.35s Table 1: Comparing SimpleRange with SmartRange on m = 231 + 32, with 10,000,000 iterations. Listing Seven template class Dispatch { 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 class Dispatch { typedef Random::value_t value_t; typedef random_traits 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 random_traits::last); return rnd % max; } }; next() per each call to next(max) when the probability of rejection is 1/2, to 1.5 expected calls to next() when the probability of the first rejection is 1/2 , and after reduction of m the probability of another rejection is 0 (one call × probability of 1/2 , plus two calls × probability of 1/2). This result is what happens with the chosen Mersenne Twister implementation, when defining, for instance, m=231+32 on 32-bit platforms. Actually, SmartRange favors even better than the aforementioned 25 percent, probably due to more information being available to the compiler in this case; see Table 1. Conclusion The computation of the remainder range size rem is carefully written to avoid overflows when value_t is an unsigned integer (as it is in the Random wrapper class). Mathematically, if you define m as the desired range exclusive maximum, M as the maximum number representable by value_t plus 1 (that is, making the previously used M greater by 1), and r as the remainder range size, then r=M mod m. Moreover, the GCD value that we compute in random_traits is actually: g=gcd(m,r)=gcd(m,M mod m)=gcd(M,m) Listing Nine template class Dispatch { typedef Random::value_t value_t; typedef random_traits 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 ::next(random); } }; Because on most architectures M is a power of 2 (do you know a platform on which it is not true?), g is actually 2 to the power of the number of trailing zeros in the binary representation of m. Thus, if we wish to forgo platform neutrality, the approach I present in this article might be efficient even when m is not known at compile time, especially if appropriate bit-twiddling hacks are employed (graphics.stanford.edu/~seander/ bithacks.html). Can REDUCE_MAX happen more than once for a single call to next(max)? The answer is no, but proving it is left as an exercise to interested readers. DDJ 48 Dr. Dobb’s Journal l www.ddj.com l April 2008 http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html 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.