0

I need to develop a function that has a one in a million chance to change one value in my application.

What I first thought was picking a number at the beginning, let's say 10 for example. Then, I call the function that uses Math.Random() to generate a number between 1 and 1000000. I then compared the generated number to the number previously defined (10) and if they are equal the value changes, otherwise it remains the same.

However, I soon realized this did not work due to Math.Random() working with doubles.

Is there any way I can do this? Or is there an alteration to what I've tried that I'm missing?

Thanks, guys!

kyrers
  • 489
  • 1
  • 6
  • 22
  • 7
    You can use java.util.Random.nextInt() (best solution). But you can also use simple arithmetics: if you multiply the random double by 1 million, then suddenly it's a number between 0 and 1 million. – JB Nizet May 02 '19 at 12:08
  • 1
    A very easy way to do this is `if (Math.random() < 1/1000000)` – Daniele Torino May 02 '19 at 12:09
  • @DanieleTorino: You're using integer division there, so `1/1000000` is zero. – jsheeran May 02 '19 at 12:11
  • @jsheeran: You are right about the integer division. Correct would be `if (Math.random() < 1.0/1000000)`. But your other argument is not really correct. Of course, there are not exactly 10^-6 numbers between 0 and 10^-6. But the **probability** of a random number between 0 and 1 to be smaller than 10^-6 is 10^-6. This is because the random numbers are uniformly distributed. And your argument about small floats (doubles) is valid but 10^-6 is not really a small number. – Daniele Torino May 02 '19 at 12:27
  • @Daniele That wouldn't work even with double division. Floats are not distributed linearly. Meaning the number of floats between [a,b) and [a+1,b+1) is **not** identical. Floats are weird like that. Admittedly the bias would be reasonably small, but why introduce unnecessary errors? – Voo May 02 '19 at 13:15
  • There's also a very simple thought experiment to convince yourself that floats cannot possibly be uniformly distributed. Floats are 32-bit values but can describe numbers much larger than 2^32. Since you can't even express all integers using floats, it's clear that floats are not uniformly distributed. You can also do the argument for small numbers, but that requires more in-depth knowledge of IEEE-754. – Voo May 02 '19 at 13:35
  • @JBNizet I did multiply the `Math.random()` by 1 million. But since they're doubles that means there are more than 1 million possible numbers or am I wrong? I might be overlooking something or I just don't know math at all. – kyrers May 02 '19 at 13:59
  • Cast the double to an int. – JB Nizet May 02 '19 at 14:22
  • @JBNizet and that doesn't affect the probabilities? – kyrers May 02 '19 at 15:05
  • 1
    @Diogo It very much does and is a bad idea. You want an integer in a specific range, use the function that exists for exactly that purpose. Anything involving PRNGs is incredibly hard to get right. Although it is well known that million-to-one-chances [succeed nine out of ten times](https://wiki.lspace.org/mediawiki/Million-to-one_chance) so there's that ;) – Voo May 02 '19 at 16:00
  • @Voo Thanks, man! I was starting to feel really dumb. You're suggesting `Random().nextInt()` am I right? Wow, I had never seen that. – kyrers May 02 '19 at 16:19
  • @Voo I agree that using Random.nextInt() would be a better idea. That's what I advised in my very first comment. But why would it affect the probabilities. Math.random generates a random which is uniformly distributed between 0 and 1. Multiplying it by 1000000 will make it uniformly distributed between 0 and 1000000. Where's the problem? – JB Nizet May 02 '19 at 16:21
  • @JBNizet "Math.random generates a random which is uniformly distributed between 0 and 1" there's your mistake. As the documentation so nicely says: "Returned values are chosen pseudorandomly with **(approximately)** uniform distribution from that range" – Voo May 02 '19 at 16:22
  • Of course it's approximately uniformly distributed. So is nextInt(): *All bound possible int values are produced with **(approximately)** equal probability* – JB Nizet May 02 '19 at 16:26
  • @JB Why "of course"? There are PRNGs that manage to produce a uniform distribution, i.e. every int is just as likely to appear as every other. For floats this is harder since there are not uniformely many floats in the range [0,1). if there are more floats in [0,0.5) than in [0.5,1) then even if every value appears exactly as often you wouldn't get exactly 50% distribution. – Voo May 02 '19 at 16:28
  • @JB Actually I just tried with a simple Java program using Math.nextAfter and there are 1056964608 floats in `[0,0.5)` but only 8388608 floats in `[0.5,1)`. So if each one of those floats appears equally likely, numbers closer to 0 should appear more often. Or is it actually the case that not every fp value has equal chances to be chosen? That could certainly change things. [Here's](https://gist.github.com/danstur/a59d53fe4cabcf13741aeafb16d801c2) the gist if you want to double check my work (never a bad idea). – Voo May 02 '19 at 16:51
  • Ah I see, next doesn't return *all* possible floating point values between 0 and 1, but just a handful which guarantees the same distribution as for integers. Yeah in that case there might be no difference between those two approaches - the only problematic cases might be cases with high upper bounds (> 2^24). – Voo May 02 '19 at 17:02
  • @JB Yup while the distribution in [0,1) *is* fine, you still can't use `floor(rand() * n)` without introducing a bias for large values of n. [I actually asked a question about this years ago](https://stackoverflow.com/questions/32360671/uniform-distribution-of-integers-using-floating-point-source) which I apparently only remembered subconsciously. The example given by Mark Dickinson and the Python bug report show this quite well. – Voo May 02 '19 at 17:21
  • @Voo you got it: uniform distribution doesn't mean that every double value in the range has the same chance to be picked. It means that if you split the range, let's say, in 1000000 intervals, a random number has 1/1000000 chance of falling into a given interval. – JB Nizet May 02 '19 at 17:22

1 Answers1

1
int result = new Random().nextInt(1000000) + 1; // will give an int between 1 - 1000000
nullPointer
  • 4,419
  • 1
  • 15
  • 27