random - ¿Cuántos números dobles hay entre 0.0 y 1.0?

floating-point double

Question

Esto es algo que he tenido en mente durante años, pero nunca me tomé el tiempo para preguntar antes.

Muchos (pseudo) generadores de números aleatorios generan un número aleatorio entre 0.0 y 1.0. Matemáticamente hay números infinitos en este rango, pero el double es un número de punto flotante, y por lo tanto tiene una precisión finita.

Entonces las preguntas son:

1. ¿Cuántos números double hay entre 0.0 y 1.0?
2. ¿Hay tantos números entre 1 y 2? Entre 100 y 101? Entre 10 ^ 100 y 10 ^ 100 + 1?

Nota: si hace una diferencia, me interesa la definición de Java del double en particular.

Answer 1

1. 2 ^ 53 - el tamaño de la significación / mantisa de un número de punto flotante de 64 bits, incluido el bit oculto.
2. Aproximadamente sí, ya que el sifnificand está fijo pero el exponente cambia.

Vea el artículo de Wikipedia para más información.

Answer 2

Cada valor double cuya representación es entre 0x0000000000000000 y 0x3ff0000000000000 encuentra en el intervalo [0.0, 1.0]. Eso es (2 ^ 62 - 2 ^ 52) valores distintos (más o menos un par dependiendo de si cuenta los puntos finales).

El intervalo [1.0, 2.0] corresponde a representaciones entre 0x3ff0000000000000 y 0x400000000000000 ; eso es 2 ^ 52 valores distintos.

El intervalo [100.0, 101.0] corresponde a representaciones entre 0x4059000000000000 y 0x4059400000000000 ; eso es 2 ^ 46 valores distintos.

No hay dobles entre 10 ^ 100 y 10 ^ 100 + 1 . Ninguno de esos números es representable con doble precisión, y no hay dobles que caigan entre ellos. Los dos números de precisión doble más cercanos son:

99999999999999982163600188718701095...

y

10000000000000000159028911097599180...

Answer 3

El doble de Java es un número binary64 de IEEE 754.

Esto significa que debemos considerar:

1. Mantissa tiene 52 bits
2. El exponente es un número de 11 bits con un sesgo de 1023 (es decir, con 1023 agregados)
3. Si el exponente es todo 0 y la mantisa no es cero, entonces se dice que el número no está normalizado

Esto significa básicamente que hay un total de 2 ^ 62-2 ^ 52 + 1 de posibles representaciones dobles que de acuerdo con el estándar están entre 0 y 1. Tenga en cuenta que 2 ^ 52 + 1 es para eliminar los casos de los no normalizados números.

Recuerde que si la mantisa es positiva pero el exponente es negativo, el número es positivo, pero menor que 1 :-)

Para otros números es un poco más difícil porque los números enteros del borde pueden no representarse de manera precisa en la representación IEEE 754, y porque hay otros bits utilizados en el exponente para poder representar los números, por lo tanto, cuanto mayor sea el número, más bajo los diferentes valores

Answer 4

Las nuevas matemáticas del artículo Java, Parte 2: Números flotantes de IBM ofrecen el siguiente fragmento de código para resolver esto (en flotantes, pero sospecho que también funciona en dobles):

public class FloatCounter {
public static void main(String[] args) {
float x = 1.0F;
int numFloats = 0;
while (x <= 2.0) {
numFloats++;
System.out.println(x);
x = Math.nextUp(x);
}
System.out.println(numFloats);
}
}

Ellos tienen este comentario al respecto:

Resulta que hay exactamente 8,388,609 carrozas entre 1,0 y 2,0 inclusive; grande pero difícilmente la infinidad incontable de números reales que existen en este rango. Los números sucesivos son aproximadamente 0.0000001 aparte. Esta distancia se denomina ULP para la unidad de menor precisión o unidad en el último lugar.

Answer 5

Las double Java están en IEEE-754 , por lo tanto tienen una fracción de 52 bits; entre cualesquiera dos poderes adyacentes de dos (incluido uno y exclusivo del siguiente), habrá por lo tanto 2 a la 52 potencia diferentes double (es decir, 4503599627370496 de ellos). Por ejemplo, ese es el número de double s distintas entre 0.5 incluido y 1.0 excluido, y exactamente que muchas también se encuentran entre 1.0 incluido y 2.0 excluido, y así sucesivamente.

Contar los doubles entre 0.0 y 1.0 es más difícil que hacerlo entre potencias de dos, porque hay muchos poderes de dos incluidos en ese rango, y, además, uno se mete en los asuntos espinosos de los números desnormalizados. 10 de los 11 bits de los exponentes cubren el rango en cuestión, por lo que, incluidos los números desnormalizados (y creo que algunos tipos de NaN ), tendrías 1024 veces la double s, ya que está entre potencias de dos: no más de 2**62 en total de todos modos. Excluyendo desnormalizados & c, creo que el recuento sería 1023 veces 2**52 .

Para un rango arbitrario como "100 a 100.1" es incluso más difícil porque el límite superior no se puede representar exactamente como un double (no siendo un múltiplo exacto de ninguna potencia de dos). Como una aproximación útil, ya que la progresión entre las potencias de dos es lineal, se podría decir que dicho rango es 0.1 / 64 th del lapso entre las potencias circundantes de dos (64 y 128), por lo que se espera

(0.1 / 64) * 2**52

distintos double s - que viene a 7036874417766.4004 ... dar o recibir uno o dos ;-).

Answer 6

Otros ya han explicado que hay alrededor de 2 ^ 62 dobles en el rango [0.0, 1.0].
(No es realmente sorprendente: hay casi 2 ^ 64 dobles finitos distintos, de los cuales, la mitad son positivos, y aproximadamente la mitad de ellos son <1.0).

Pero mencionas generadores de números aleatorios: ten en cuenta que un generador de números aleatorios que genera números entre 0.0 y 1.0 no puede en general producir todos estos números; por lo general, solo producirá números de la forma n / 2 ^ 53 con n un número entero (consulte, por ejemplo, la documentación de Java para nextDouble ). Por lo general, solo hay alrededor de 2 ^ 53 (+/- 1, según los puntos finales incluidos) valores posibles para la salida random() . Esto significa que la mayoría de los dobles en [0.0, 1.0] nunca se generarán.