# 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));
}```