What is the total number of unique values ​​for double in the range [0.0, 1.0]?

Question

Random.NextDouble () (a double from the range [0.0,1.0)) is sometimes multiplied by a large Int64 (let Int64 be large = 9000000000L), and the result is superimposed to obtain a random Int64 value greater than that obtained from Random.Next () (Int32 from the range [0, Int32.MaxValue)).

Random r = new Random(); long big = 9000000000L; long answer = (long) (r.NextDouble() * big); 

It seems to me that the total number of unique values ​​for Double in the range [0.0, 1.0) provides an upper bound for the number of unique Int64 that it can generate. The free upper bound, in fact, like many different pairs, will be mapped to the same Int64.

Therefore, I would like to know: what is the total number of unique values ​​for double in the range [0.0, 1.0)?

Even better, if you can tell me that the largest value of "large" can be taken so that the "answer" can be a value from the range [0, large] and whether the distribution of the values ​​of the "answer" is uniform, assuming that Random.NextDouble ( ) is uniform.

Edit: Double (double) here refers to the IEEE 754 double floating point, while Int64 (long) and Int32 (int) refer to 64-bit and 32-bit subscription 2nd additions, respectively.

---

Inspired by this question: Creating 10 digits of a unique random number in java

While I used C #, this question is a linguistic agnostic and is more related to discrete mathematics than programming, but it bothers me not only because of a sense of mathematical curiosity, but also from a programmer who wants to use the formula only if it does what he has to do, and in terms of security.

Answer 1

As a consequence of your question, I’ll tell you that the Random C # generator uses an internal generator that “gives it” numbers between 0...Int32.MaxValue - 1 . Then it divides the number by Int32.MaxValue (technically multiplied by the inverse of that number) to return a double. So in C # there is only Int32.MaxValue possible doubles ( 0...Int32.MaxValue - 1 )

Answer 2

IEEE-754 has 11 bit exponent and 52 mantissa. Assuming the sign bit is 0 (positive), if the exponent is in the range 0x001 to 0x3FE, the value is a standard floating-point number between 0 and 1. Mantissa is interpreted by the leading 1, which is not saved. For each of these 0x3FE values ​​for the exponent, there are 2 ^ 52 mantissa values. In addition, if the exponent is 0x000, the mantissa is interpreted without this leading value, but as if the exponent was 0x001, a total of 0x3FF = 1023 exponents, where all the mantissas are valid. This is the sum of the values 1023 * 2 ^ 52 . In addition, negative 0 can be considered, which is another value.

If random twins were generated uniformly over all values, then this would really lead to a bias when multiplying to generate Int64. However, any reasonable random library will approximate the uniform distribution by [0, 1), and this will not be biased when it is converted to Int64. The largest value for the "large", which will allow you to get all the integers in [0, big), is 2 ^ 53 - the resolution of 2 ^ 52 between 1/2 and 1 is 2 ^ (- 53). However, it often happens that these numbers are produced by dividing random integers by an integer range (usually Int32), which means that you cannot actually produce more numbers than this source. Consider directly combining two Int32s, for example, by moving one to 32 bits and combining them in Int64. (Although be careful, the state space for a generator can only be 32 bits.)

Answer 3

IEEE754 clearly understands the accuracy of doubling:

http://en.wikipedia.org/wiki/IEEE_754-2008

You have 52 bits of precision plus an additional estimated bit.

You have indicators from -1022 to 1023, about 11 bits, including the sign.

The 64th bit is a common sign for a number.

We will ignore subnormalized numbers.

You ask about exponents between -1022 and 0. This means that you have about 10 available 11 bits exponents available to you.

You have a 52 + 1 bit mantissa.

This is about 62 bits of useful precision for representing 2 ** 62 different values ​​from

Answer 4

@wnoise pretty much nailed it, but here are my two cents.

IEEE floats can be compared and increased as integers with some restrictions, see this question for details. So, if we produce integers +0.0 and from 1.0 to 64 bits, we get the number of steps between zero and one:

 #include <iostream> int main() { double zero = 0.0; double one = 1.0; unsigned long long z = *reinterpret_cast<unsigned long long*>(&zero); unsigned long long o = *reinterpret_cast<unsigned long long*>(&one); std::cout << z << std::endl; std::cout << o << std::endl; } 

This gives me 0 and 4607182418800017408 respectively, that is, there are 4607182418800017408 unique double values ​​in the range [0.0, 1.0).

Answer 5

The total number of unique values ​​for double in the range [0.0, 1.0) depends on the representation of double in a particular environment.

One of the most common representations is that specified by IEEE 754 . This format is e. using Java and C # (see 1.3 Types and Variables for the latter).

Answer 6

It depends on the implementation of double . There are implementations that do not allow denormalized values ​​and exclude the leading one; determining the number of possible values ​​is easy here:

• there are several “special” values ​​(0, +0, -0, + ∞, -∞, silent NaN, signaling NaN) that usually cost you one possible indicator
• there is no way that the mantissa shift and exponent modification produce an equivalent number

If your implementation allows denormalized values, defining this number becomes a little more complicated, but I would start by comparing the possible values ​​in this representation with the equivalent fixed-leading representation (which will use one bit less in the mantissa); if you find an appropriate match, it will be injective , and you have reduced the problem to a simpler one.