![]() ![]() > Why are they multiplying them together? I guess it could have been because the web version has to use JavaScript, and they wrote it before Crypto.getRandomValues() was designed and sufficiently widely supported (apparently it was in all browsers by 2014 but some users may have been running older versions for years), so the only API for randomness was Math.random() which returns double-precision floats. You also can't characterize it as a "discrete uniform" distribution, because the discrete uniform distribution over the floating point values from 0.0 to 1.0 should generate all of them with equal probability, which in practice means that it should be strongly biased towards small floats (precision increases as you get closer to zero, so there are far more small floats than large floats within that interval). Besides, the continuous distribution would include irrational numbers and other values which don't exist in the floating point universe. You can't say that a continuous distribution is equal to a uniform distribution, because those are different kinds of object altogether. In short, please just use the usual method and don't actually try to implement this. Also, while we *can* generate zero this way, I'm not sure if its probability is correct, or even what that probability ought to be in the first place.ĥ. I'm not sure if it's 100% correct because you probably have to do some finessing to handle denormal numbers (whose range is different from the other exponential buckets), and I can't be bothered to figure out how that works. It is much slower, harder to code correctly, and therefore of little use.Ĥ. The outputs do not all have the same probability of being generated.ģ. The usual method cannot generate most of them.Ģ. All possible floats between zero (inclusive) and one (exclusive) can be generated. This algorithm still produces 2^n possible results, but:ġ. If this would result in a negative biased exponent, throw it out and start over. Set the exponent field to n plus the bias. ![]() For each tails (zero), decrement n by one.Ĥ. Flip a fair coin (generate a random bit) until you get heads (one). Fill the significand with random bits, and set the sign bit to zero (positive).ģ. However, you could instead use the following algorithm, which would give you a different discrete distribution that *also* closely resembles the same continuous uniform distribution:ġ. * The usual algorithm for generating a "uniform" float works by generating an integer up to 2^N for some N, then (float) dividing by 2^N for the right value of N, this gives you the maximum amount of entropy that can be squeezed into a float, and exhibits a (discrete) distribution extremely similar** to the (continuous) uniform distribution over the real interval from zero to one. Therefore, whatever "simple" method we came up with is biased in some fashion and should not be used for cryptographic purposes.īasically, if (3) describes your method, then your method is wrong and you should throw it out and use the library random integer functions instead. There is no way to assign all 2^n possible random values to the k output buckets evenly, because 2^n is not necessarily divisible by k.ĥ. We sample from our "source" random function exactly once and then run it through some kind of fixed formula to turn it into an output value.Ĥ. We want to output k different values with equal probability, and k is not necessarily a power of 2.ģ. In particular, this is (nearly*) always the case for "choose a uniform random float from 0 to 1," as well as "choose a uniform random integer from 0 to INT_MAX."Ģ. Whatever random function we start with generates 2^n possible outputs with equal probability, for some n. The proof sketch will usually look like the following:ġ. It's not at all uncommon for students to be taught an incorrect method of generating (uniform) random integers from 0 to n (or 1 to n, or whatever).Īs a rule of thumb, most "simple" methods for generating (uniform) random integers are incorrect, except for "call a library function that does the hard work for you." Most of the time, it's not even difficult to prove that a given method is incorrect. Why are they sampling *floats*? Why are they multiplying them together? Is this witchcraft? ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |