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

d04orlov_p5ds 2/13/08 8:56 AM Page 44 Core Technology by Michael Orlov Random Numbers in a Range Using Generic Programming Greatest Common Divisor algorithm for efficient random-number generation Consider the generation of random numbers in an interval, say the generation of an integer in Michael is a doctoral candidate in the Computer Science Department of Ben-Gurion University. He can be contacted at orlovm@cs.bgu.ac.il. {0,1,…,m–1} where the probability of each integer is 1/m. Usually, you have a source of randomness that provides random bits in chunks of architecture word size—something like the wrapper around the mtrand library (bedaux.net/mtrand); see Listing One. Mtrand implements the Mersenne Twister randomnumber generator (www.math.sci.hiroshima-u.ac.jp/ ~m-mat/MT/emt.html), which is a high-quality source of randomness. By “high quality,” I mean that you don’t need to consider low-order bits of words produced by the generator to be of inferior quality than high-order bits. In principle, you can take the value returned by next() modulo m to produce an integer in the range [0,m–1]. However, this approach is problematic when m is comparable in size to the number of values representable by value_t. For instance, assume that the type of value_t is an unsigned 10-bit integer, and can thus contain values in the [0,1023] range. Consider m=684, which is approximately 2/3 of 1024. Taking a random value_t modulo m results in the lower half of [0,m–1] range having twice the probability of its upper half. The regular approach to this problem is to ignore it (effectively assuming that m is low enough that the difference in probabilities is insignificant), or to reject the values in the “remainder” portion of the value_t range; see Listing Two. Taking the previous example with m=684, the constants in Listing Two are: • M=1023, the maximal value representable by value_t. • rem=340, the remainder size. • last=683, the last value in the range of “safe” values returned by next(). Is the remainder values rejection approach costly? It is, especially for values of m close to, but above, the half-range of value_t. For such values, the expected number of calls to next() for each call to next(max) is 2 (this follows from the probability of rejection being 1/2). Because the cost of random bits varies between “moderate” (for Mersenne Twister) to “expensive” (for cryptography-oriented generators, especially hardware implementations), the running time of the relevant program portions doubles in such cases (unless you settle for the low-quality linear congruential generators). Is it wasteful? The rejected values are thrown away, but perhaps their inherent entropy can still be used—maybe to reduce the probability of rejection on the next iteration of the do/while loop? For instance, in the example, once rnd is rejected, and just before the next loop iteration, rnd-last-1 is uniformly distributed in the [0,rem–1] range. You could partition the [0,m–1] range into exact rem buckets, 44 Dr. Dobb’s Journal l www.ddj.com l April 2008 http://bedaux.net/mtrand http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.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.