Non-uniform random numbers in Objective-C

Question

I'd like to calculate a non-uniformly distributed random number in the range [0, n - 1]. So the min possible value is zero. The maximum possible value is n-1. I'd like the min-value to occur the most often and the max to occur relatively infrequently with an approximately linear curve between (Gaussian is fine too). How can I do this in Objective-C? (possibly using C-based APIs)

A very rough sketch of my current idea is:

// min value w/ p = 0.7
// some intermediate value w/ p = 0.2
// max value w/ p = 0.1
NSUInteger r = arc4random_uniform(10);
if (r <= 6) 
    result = 0;
else if (r <= 8)
    result = (n - 1) / 2;
else
    result = n - 1;

Answer 1

I think you're on basically the right track. There are possible precision or range issues but in general if you wanted to randomly pick, say, 3, 2, 1 or 0 and you wanted the probability of picking 3 to be four times as large as the probability of picking 0 then if it were a paper exercise you might right down a grid filled with:

3 3 3 3
2 2 2
1 1
0

Toss something onto it and read the number it lands on.

The number of options there are for your desired linear scale is:

- 1 if number of options, n, = 1
- 1 + 2 if n = 2
- 1 + 2 + 3 if n = 3
- ... etc ...

It's a simple sum of an arithmetic progression. You end up with n(n+1)/2 possible outcomes. E.g. for n = 1 that's 1 * 2 / 2 = 1. For n = 2 that's 2 * 3 /2 = 3. For n = 3 that's 3 * 4 / 2 = 6.

So you would immediately write something like:

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    ... something ...
}

At that point you just have to decide which bin uniformRandom falls into. The simplest way is with the most obvious loop:

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    NSUInteger index = 0;
    NSUInteger optionsToDate = 0;
    while(1)
    {
        if(optionsToDate >= uniformRandom) return index;
        index++;
        optionsToDate += index;
    }
}

Given that you can work out optionsToDate without iterating, an immediately obvious faster solution is a binary search.

An even smarter way to look at it is that uniformRandom is the sum of the boxes underneath a line from (0, 0) to (n, n). So it's the area underneath the graph, and the graph is a simple right-angled triangle. So you can work backwards from the area formula.

Specifically, the area underneath the graph from (0, 0) to (n, n) at position x is (x*x)/2. So you're looking for x, where:

(x-1)*(x-1)/2 <= uniformRandom < x*x/2

=> (x-1)*(x-1) <= uniformRandom*2 < x*x
=> x-1 <= sqrt(uniformRandom*2) < x

In that case you want to take x-1 as the result hadn't progressed to the next discrete column of the number grid. So you can get there with a square root operation simple integer truncation.

So, assuming I haven't muddled my exact inequalities along the way, and assuming all precisions fit:

NSUInteger random_linear(NSUInteger range)
{
    NSUInteger numberOfOptions = (range * (range + 1)) / 2;
    NSUInteger uniformRandom = arc4random_uniform(numberOfOptions);

    return (NSUInteger)sqrtf((float)uniformRandom * 2.0f);
}

Answer 2

What if you try squaring the return value of arc4random_uniform() (or multiplying two of them)?

int rand_nonuniform(int max)
{
    int r = arc4random_uniform(max) * arc4random_uniform(max + 1);
    return r / max;
}

I've quickly written a sample program for testing it and it looks promising:

int main(int argc, char *argv[])
{
    int arr[10] = { 0 };

    int i;
    for (i = 0; i < 10000; i++) {
        arr[rand_nonuniform(10)]++;
    }

    for (i = 0; i < 10; i++) {
        printf("%2d. = %2d\n", i, arr[i]);
    }

    return 0;
}

Result:

0. = 3656
1. = 1925
2. = 1273
3. = 909
4. = 728
5. = 574
6. = 359
7. = 276
8. = 187
9. = 113