From 5 dice rolls, generate a random number in the range [1 - 100]

Question

I was going through some coding exercises, and had some trouble with this question:

From 5 dice (6-sided) rolls, generate a random number in the range [1 - 100].

I implemented the following method, but the returned number is not random (called the function 1,000,000 times and several numbers never show up in 1 - 100).

public static int generator() {

     Random rand = new Random();
     int dices = 0;

     for(int i = 0; i < 5; i++) {
         dices += rand.nextInt(6) + 1;
     }

     int originalStart = 5;
     int originalEnd = 30;
     int newStart = 1;
     int newEnd = 100;

     double scale = (double) (newEnd - newStart) / (originalEnd - originalStart);
     return (int) (newStart + ((dices - originalStart) * scale));
}

Taliped

Don't create a new instance of Random each time, maintain a single instance for each method call. While you may still get "lost" numbers, the range will be far more random. – Vote

just use the first dice roll. It will return a random number between 1-100. That or please clarify your question. – Scherer

he needs to simulate dice rolls. When's the last time you saw a dice with 99 faces? – Judgemade

I've seen a die with 100 faces before. – Alpenglow

@Judgemade unfortunately, they exist – Lulualaba

Answer 1

Ok, so 5 dice rolls, each with 6 options. if they are un-ordered you have a range of 5-30 as mentioned above - never sufficient for 1-100.

You need to assume an order, this gives you a scale of 1,1,1,1,1 - 6,6,6,6,6 (base 6) assuming 1 --> 0 value, you have a 5 digit base 6 number generated. As we all know 6^5 = 7776 unique possibilities. ;)

For this I am going to give you a biased random solution.

int total = 0;
int[] diceRolls;
for (int roll : diceRolls) {
    total = total*6 + roll - 1;
}

return total % 100 + 1;

thanks to JosEdu for clarifying bracket requirement

Also if you wanted to un-bias this, you could divide range by the maxval given in my description above, and subsequently multiply by your total (then add offset), but you would still need to determine what rounding rules you used.

Truehearted

Amusingly similar to Slavics answer which he must have been writing at the same time as I wrote this, only I use integers not decimals. :) – Truehearted

Dont need brackets, the % operator have precedence over +. – Louanneloucks

To clear up the confusion here. I've seen programmers that thought they knew precedence rules. Took me days to untangle their mess and arrive at the conclusion that they did indeed not know precedence rules. Program for clarity, use parenthesis when stacking several of the less common operators (anything but +-*). It's not like your program will run 10 times slower because you added parenthesis, but the mess you create when you and others think they understand your code might add 10 times the hours... – Hame

Answer 2

Rolling a 6 sided die 5 times results in 6^5 = 7776 possible sequences, all equally probable. Ideally you'd want to partition those sequences into 100 groups of equal size and you'd have your [1 - 100] rng, but since 7776 isn't evenly divisible by 100 this isn't possible. The best you can do to minimize the bias is 76 groups mapped to by 78 sequences each and 24 groups mapped to by 77 sequences each. Encode the (ordered) dice rolls as a base 6 number n, and return 1 + (n % 100).

Not only is there no way to remove the bias with 5 dice rolls, there is no number of dice rolls that will remove the bias entirely. There is no value of k for which 6^k is evenly divisible by 100 (consider the prime factorizations). That doesn't mean there's no way to remove the bias, it just means you can't remove the bias using a procedure that is guaranteed to terminate after any specific number of dice rolls. But you could for example do 3 dice rolls producing 6^3 = 216 sequences encoded as the base 6 number n, and return 1 + (n % 100) if n < 200. The catch is that if n >= 200 you have to repeat the procedure, and keep repeating until you get n < 200. That way there's no bias but there's also no limit to how long you might be stuck in the loop. But since the probability of having to repeat is only 16/216 each time, from a practical standpoint it's not really much of a problem.

Ectoblast

Answer 3

The problem is there aren't enough random values in 5-30 to map one to one to 1-100 interval. This means certain values are destined to never show up; the amount of these "lost" values depends on the size ratio of the two intervals.

You can leverage the power of your dice in a way more efficient way, however. Here's how I'd do it:

Approach 1

1. Use the result of the first dice to choose one subinterval from the 6 equal subintervals with size 16.5 (99/6).
2. Use the result of the second dice to choose one subinterval from the 6 equal sub-subintervals of the subinterval you chose in step one.
3. Use... I guess you know what follows next.

Approach 2

Construct your random number using digits in a base-6 system. I.E. The first dice will be the first digit of the base-6 number, the second dice - the second digit, etc.
Then convert to base-10, and divide by (46656/99). You should have your random number. You could in fact only use 3 dice, of course, the rest two are just redundant.

Judgemade

Why not? There are equal chances for any number in 1-100 to be present. Or at least it so seems to me now. – Judgemade

you're going to have to take a floor function and the intervals you wind up chopping into aren't going to space evenly with respect to the lines between integers. Try writing the ticks 3,6,9,12,15... on a line then tick 2,4,6,8,... and you'll see what I mean. – Scherer

Or more numerically, any combination of integers (a,b,c,d,e,f) --> a number 1-100. Do you really think you can do that evenly? No; it's the same as the original mathematical problem, and the floating point approach is just a detour for computation's sake. – Scherer