# Random Numbers in a Range Using Generic Programming

### Evaluation

The supplied code (available online at www.ddj.com/code/) can be used to estimate the runtime optimization resulting from the use of SmartRange. The theoretical limit is 25 percent off the original runtime: Going down from the expected 2 calls to 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.

 Approach next()/next(max) Time SimpleRange 1.99976 1.30s (0.53s w/inlining) SmartRange 1.50794 0.35s

Table 1: Comparing SimpleRange with SmartRange on m = 231 + 32, with 10,000,000 iterations.

### 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)

```

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.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>