Today I needed some non-uniform random numbers. Most pseudo random number generators such as the rand(3) function return numbers that are drawn from a uniform distribution, so for example with rand(3) you have an approximately equal chance of getting and number between 0 and RAND_MAX. However in many real world situations some numbers occur much more frequently than others. For example, on average most programs make many more small memory allocations than large ones. Graphing the distribution of allocation sizes you get something that looks like a power law distribution. I don’t know if allocations always follow this type of pattern in all applications or whether it is in fact a true power law distribution, but it seems like a reasonable approximation.

So how can we generate random numbers that are drawn from a power law distribution? The easiest way is to use the standard uniform random number generator and transform the results. Below is some code in C that does that. It looks quite complex but gcc handles the constant propagation and the generated code is quite simple with only a single call to drand48.