Java- Math.random(): Selecting an element of a 13 by 13 triangular array

java, math, probability, random

Solution

The `int roll = random.next(91)` strategy will work just fine. You get guaranteed, worry-free uniform distribution, and better performance to boot, since you're only picking 1 random number. You simply need to find a formula that identifies where one "row" ends and another begins. Look for the pattern:

0, 1, 3, 6, 10, 15, ...

There's a reason they're called "triangular numbers..."

Let's flesh this out a bit more. You want to actually find the nearest triangle number smaller than the random `roll` that you picked: that gets you to the right row, and the difference of that triangle number and `roll` gets you the offset into that row.

Given that the `n`th triangle number is given by `n*(n+1)/2`, how do you find the largest one smaller than `roll`? Given the small size of the array, a naïve implementation should be plenty fast:

int largestTriangleNumberSmallerThan(int x) {
    int i = 0;
    int last = 0;
    while (true) {
        int triangle = i*(i+1)/2;
        if (triangle > x) return last;
        last = triangle;
        i++;
    }
}

http://ideone.com/vzQEBz

Of course, that's boring and didn't take any thought. We can do better! We can do it in constant* time, regardless of how big the input is! Start by inverting the function (we only care about the positive root, of course):

n = (Math.sqrt(8y + 1) - 1)/2

Then truncate the decimal part, and run it back through:

int largestTriangleNumberSmallerThan(int x) {
    int n = (int) (Math.sqrt(8*x + 1) - 1)/2;
    return n*(n+1)/2;
}

http://ideone.com/1qBHfX

To put it all together:

int roll = random.nextInt(91);
int num1 = (int) (Math.sqrt(8*roll + 1) - 1)/2;
int num2 = roll - num1*(num1+1)/2;

That's it!

*assuming that the native `StrictMath#sqrt(double)` function is constant time - I'm actually not sure about this.

Problem

Original source

Related problems

• Probability in Java