# Solved Debate for the MathHeads

Discussion in 'Plugin Development' started by Scimiguy, Oct 15, 2015.

Thread Status:
Not open for further replies.
1. Offline

### Scimiguy

I suppose it's not strictly Bukkit related.. but I'm going to end up using it in a Bukkit plugin so...

I already know a method or two, but I'm curious to see how other people here would approach this.

Given a list of numbers 1-10, how would code it so that the chance of randomly returning any number is less than any number lower than it?

So the idea is to be able to randomly provide a number between 1 and 10, but the higher the number, the rarer the chance must be.
The actual scale of chances can be anything.. if you do it so that 10 is 10x more rare than 1, that's fine. If you want 10 to be exponentially more rare than 1, that's fine too.

Best answer will be chosen based on code efficiency

#1
2. Offline

### Xerox262

So you're trying to do something like, there's a 1 in 10 % chance that it's a 10 item, a 1 in 9 for a 9 item and so on, with 1 being always if they didn't get something before it?

#2
3. Offline

### Scimiguy

@Xerox262
More or less.
You must return a number from the range 1-10, but the higher the number, the lower the chance.
You'd want to look into weighted randoms, and weighted sampling to get the idea

As for the scale (I.E. 10=1/10. 9=1/9), it doesn't matter. If you want to use that scale, it's fine. If you want to make it like 10=1/10000000000, 9=1/1000000000, etc.. That's fine too
It's all about coming up with the most efficient way to do scaled weighted random sampling

#3
4. Offline

### LucasEmanuel

Use a weighted RNG.

#4
5. Offline

### Xerox262

Make a random, get an int between 0 and 9, if it's exactly 0 then it's a 10 number, make an else if, get an int from the random between 0 and 8, if it's exactly 0 then it's a nine number, continue this until you get to your 1 number then make it an else.

#5
6. Offline

### LucasEmanuel

No, this is very inefficient.

Here i use this for weighted randoms:
https://github.com/Chilinot/LucasUt...ucasarnstrom/lucasutils/RandomCollection.java

EDIT:
It has an O(log n) time complexity for the lookup.

#6
Xerox262 likes this.
7. Offline

### mythbusterma

@LucasEmanuel

Clever, but nowhere near as good as a simple math trick.

@Scimiguy

You could chose a random and take the square root of it, then round down. As the number gets higher, they get progressively more likely to happen. For example, 1 can only be gotten if the value is less than 2.4 or so.

This is always run in constant time (O(1)).

#7
LucasEmanuel likes this.
8. Offline

### Scimiguy

@mythbusterma
Taking the square root programmatically is very inefficient

#8
9. Offline

### mythbusterma

@Scimiguy

In theory, yes. It is an O(n) operation. However, since Java works with a constant number of bits (either 32 or 64, depending on your runtime) it can be considered constant time, as it will always take the same amount of time, not matter the size of the number.

In all reality, on modern hardware (read: on my outdated i7 running Windows) it takes around 17 nanoseconds (and this never changes), which is far faster than any data structure is.

So in theory, it could be slow. In practice, it is by far and away the fastest method.

#9
10. Offline

### Scimiguy

@Xerox262
Yeah I know your method, it's not the best..

@mythbusterma

I'm not sure I understand what your method is exactly, I think I'm misinterpreting it

#10
11. Offline

### LucasEmanuel

Since the value you are taking the root of has a fixed size-limit (32 or 64 bit) it will always take a constant time to produce a result. I.e. the time it takes to calculate the root of a value on your machine will not change no matter the value, since all values will be of the same size.

#11
12. Offline

### Scimiguy

@LucasEmanuel

I mean the method itself -- how it's performed

#12
13. Offline

### LucasEmanuel

Ah, my misstake.

#13
14. Offline

### mythbusterma

@Scimiguy

Something like:

Code:
```int number = new Random().nextInt(100);

int value = (int) Math.floor(Math.sqrt(number));

switch (value) {
case 1:
// do something
case 2:
// do something slightly more likely
........
case 9:
// do something most likely
}```

#14
Scimiguy likes this.
15. Offline

### Scimiguy

@mythbusterma
Definitely the most efficient for low scaling coefficients.

#15
Thread Status:
Not open for further replies.