A simple power law pseudo-random number generator

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.

#include <math.h>
#include <stdlib.h>

#define MIN_ALLOCATION_SIZE	4
#define MAX_ALLOCATION_SIZE	8192

size_t
get_block_size (void)
{
  /* Inverse square.  */
  double exponent = -2;
  /* Minimum value of distribution.  */
  double dist_min = MIN_ALLOCATION_SIZE;
  /* Maximum value of distribution.  */
  double dist_max = MAX_ALLOCATION_SIZE;

  double min_pow = pow (dist_min, exponent + 1);
  double max_pow = pow (dist_max, exponent + 1);

  return (size_t) pow((max_pow - min_pow) * drand48 ()
                      + min_pow, 1 / (exponent + 1));
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s