¿Es razonable suponer que cualquier cantidad física puede ser representada por un número entero de 64 bits sin desbordamiento o subflujo?

31

El algoritmo de búsqueda binario original en el JDK usaba enteros de 32 bits y tenía un error de desbordamiento si (low + high) > INT_MAX( http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html ) .

Si reescribimos el mismo algoritmo de búsqueda binaria usando enteros (firmados) de 64 bits, ¿podemos suponer que low + highnunca excederá INT64_MAX porque es físicamente imposible tener 10 ^ 18 bytes de memoria?

Cuando se usan enteros (con signo) de 64 bits para representar cantidades físicas , ¿es razonable suponer que no puede ocurrir un desbordamiento y desbordamiento?

design algorithms Siqi Lin
fuente
44
Mire cualquier fenómeno físico que tenga un número irracional asociado. Círculos y pi por ejemplo. Los números de punto flotante son inherentemente racionales, por lo tanto, no puede representarlo perfectamente sin error.
Thomas Eding
92
El número de átomos en el sol es aproximadamente 1.2e57, que cabe en un entero sin signo de 190 bits. Por contradicción, 64 bits no pueden ser lo suficientemente grandes como para representar cualquier cantidad física.
66
El título de su pregunta es engañoso. Debería preguntar "¿hay cantidades para las cuales uno podría esperar una aplicación que usa una matriz ordenada de tamaño mayor que 2 ^ 64?"
Doc Brown
77
o la cantidad de yoctosegundos desde que comenzó a leer este comentario.
Jodrell
44
Hubo un tiempo en que todos pensaban que nunca habría una computadora 2 ^ 32 conectada entre sí. No quieres que tus átomos tengan que usar NAT, ¿verdad?
Sebb

Respuestas:

58

La respuesta corta es no. Sin embargo, para algunas aplicaciones, su suposición podría ser correcta.

Suponiendo un int firmado, 2 ^ 63, con comas agregadas para mayor claridad, = 9,223,372,036,854,775,808. Entonces es aproximadamente 9 * 10 ^ 18. 10 ^ 18 es un "Exa".

Wikipedia dice "A partir de 2013, se estima que la World Wide Web alcanzó 4 zettabytes. [12]", que es 4000 Exabytes. Por lo tanto, la WWW es aproximadamente 400 veces más grande que 2 ^ 63 bytes.

Por lo tanto, hay al menos una cantidad física que es mucho mayor que un entero de 64 bits con signo (o sin signo). Suponiendo que sus unidades son bytes . Si sus unidades fueran algo mucho más grandes, como GigaBytes, entonces estaría bien, pero su precisión de medición sería baja.

Para otro ejemplo, considere galaxias lejanas. La galaxia de Andrómeda es en realidad una de las más cercanas, y está a 2.5 * 10 ^ 6 años luz de distancia. Si sus unidades fueran millas , eso sería 14.5 * 10 ^ 18, más de un entero con signo de 64 bits. Ahora, obviamente, depende de las unidades que use para sus mediciones, pero algunas galaxias están mucho más lejos que Andrómeda. ( El más conocido se encuentra a 13 * 10 ^ 9 LY de distancia ) . Dependiendo de la precisión que desee para su medición, podría desbordar un entero de 64 bits.

( Agregado ) Sí, las millas son una pésima unidad para la distancia astronómica. Una unidad más normal podría ser una Unidad Astronómica , aproximadamente 93 millones de millas. Usando esa unidad de medida, la galaxia más lejana conocida es aproximadamente 10 ^ 15 UA (si mis cálculos son correctos), lo que cabría en un int de 64 bits. Sin embargo, si desea medir también la distancia a la Luna, a los satélites en órbita cercanos, esa unidad es demasiado grande.

Un ejemplo más de la electrónica: el Farad (F), una unidad de capacitancia . Los condensadores grandes varían hasta 5kF. Y este número probablemente aumentará con el tiempo a medida que mejoren los automóviles híbridos, las "redes inteligentes", etc. Una vez puede medir capacitancias tan pequeñas como 10 ^ -18 F. Por lo tanto, el rango general en capacitancia "real" que podemos medir hoy es 5 * 10 ^ 21, mayor que un entero de 64 bits.

user949300
fuente
3
Todo esto es cierto, pero desde un punto de vista práctico podemos cuestionar el punto de medir la distancia de la galaxia de Andrómeda a la Vía Láctea en millas (¿dónde están exactamente el punto de referencia?) O la WWW completa en bytes (con esta precisión, cambia cada milisegundo)
Jivan
45
@Jivan Desde un punto de vista práctico, no puedo ver ninguna razón por la que alguna vez necesites abordar más de 640kB de memoria. Seguramente es más de lo que NUNCA necesitarías.
ArTs
2
Otro inconveniente de medir distancias astronómicas en millas: es probable que te golpeen con un gato.
Williham Totland
2
@Jivan Buen punto. Eso me recuerda a Richard Feynman despotricando sobre la tontería de sumar la temperatura de un grupo de estrellas. Ya veo por qué querrías el promedio, el mínimo, el máximo, ¿pero la suma? ¿Qué significado físico es eso?
piojo
66
@piojo: es cierto que la suma es útil cuando se calcula la media.
Scott Whitlock
20

Ni siquiera necesita volverse cósmico cuando se trata de combinatoria. Hay 2 ^ 95 ofertas posibles en un juego de bridge y eso es un poco pequeño de la complejidad.

msw
fuente
Uno podría preguntarse si eso cuenta como una "cantidad física".
Paul Draper
2
Por otro lado, la combinatoria involucrada en química o matemáticas calificaría como "física".
rwong
@PaulDraper si tienes suficientes barajas de cartas para colocar en el suelo todas esas ofertas, sería físico. Entonces tendrías incluso más de 2 ^ 95 cartas involucradas.
Brad
1
@Brad, creo que el OP está pidiendo una cantidad que "existe" (bueno, la existencia es un concepto difuso). 2 ^ 95 tarjetas que satisfacen un concepto matemático no existen (llame a Guinness si lo hacen). Es difícil decir qué "cuenta" y qué no. Esta respuesta simplemente no satisface mi noción blanda de una cantidad física.
Paul Draper
17

La cantidad física más relevante para su pregunta es la RAM de la computadora .

Windows Server 2012 admite hasta 4 TB de memoria física. Eso es 2 42 bytes. Si las capacidades de RAM continúan duplicándose cada año, entonces, en solo 17 años a partir de ahora, "Windows Server 2032" admitirá 2 62 bytes de memoria física, momento en el cual low + highalcanzará 2 63-2 y besará el número entero de 64 bits con signo máximo.

Espero que ningún sistema crítico para la seguridad falle, suponiendo que 64 bits siempre serán suficientes.

Para un uso un poco más general, la cantidad física más relevante es el espacio de direcciones de memoria . (Es útil tener un espacio de direcciones mucho más grande que la memoria física, por ejemplo, poner muchas pilas en la memoria, todo con espacio para crecer). Las implementaciones x86-64 actuales admiten direcciones virtuales de 48 bits, por lo que solo tenemos 14 años antes de que estas CPU alcancen el límite de espacio de direcciones de 2 62 bytes.

Y luego está la memoria compartida distribuida "donde las memorias (físicamente separadas) se pueden direccionar como un espacio de direcciones (lógicamente compartido)".

Jerry101
fuente
44
+1 Su respuesta es casi exactamente correcta, excepto que ciertos tipos de software de hoy ya están encontrando direcciones de memoria en el rango de 0xFFFFFFFFxxxxxxxx(es decir, la mitad superior ), por ejemplo, el sistema operativo o los controladores de dispositivo.
rwong
2
@SiqiLin probablemente no en lo que respecta a la informática personal. Sin embargo, la memoria compartida distribuida, o la DGAS (mencionada en el artículo) son reales; Las supercomputadoras han estado operando en ese estilo durante años, y es posible que se convierta en la norma para la infraestructura de computación en la nube multinacional. Aparentemente, el código de software típico escrito por el programador típico no se ejecutará en dicho entorno: los entornos inusuales ejecutan software inusual (es decir, infraestructura). Pero una fracción de los lectores de P.SE podría aterrizar en esa carrera; por si acaso.
rwong
1
@Joshua: con la tecnología actual (DDR4 de 32 GB) serían 7m o 23 ns para que la luz viaje, lo que parece estar perfectamente en línea con las latencias CAS modernas. Si lo lleva al principio extremo de Landauer, con la densidad del silicio obtendrá 31 nm o 10 ^ -16 segundos para el límite físico. Eso no parece demasiado loco ... bueno, tal vez solo un poco.
Charles
3
@Joshua Ese es un límite tecnológico, no físico. (Como en el caso, el problema es que no sabemos cómo hacerlo prácticamente, no es que alguna ley física lo prohíba). Por lo tanto, si bien es relevante esta semana, podría cambiar en cualquier momento con algún nuevo avance. Hace unos 60 años, las personas habrían hecho comentarios muy similares a los suyos, aproximadamente 50 kilobytes de memoria se consideran RAM, debido a que las bobinas de alambre enrolladas a mano y luego utilizadas como partes de los núcleos de memoria no solo podrían volverse tan pequeñas e inmóviles. función, pero requiere espacio entre ellos para evitar la diafonía EM.
Matthew Najmon
2
Recuerdo cuando 24 bits de espacio de direcciones (16 megabytes) eran más de lo que cualquiera podría necesitar, o ser capaz de pagar. :-)
Bob Jarvis - Restablece a Monica
10

¿Es razonable suponer que cualquier cantidad física puede ser representada por un número entero de 64 bits sin desbordamiento o subflujo?

No exactamente. Hay muchos números que son más grandes y más pequeños que eso, por eso tenemos números de coma flotante. Los números de punto flotante intercambian menor precisión para un mejor rango

En el ejemplo específico que citó, es muy poco probable que alguna vez necesite un número mayor que ese. 64 bits corresponden a aproximadamente 18 quintillones de elementos. Pero nunca digas nunca.

Robert Harvey
fuente
7

Su suposición no manejará cantidades físicas que solo pueden representarse mediante números de coma flotante. E incluso si decidió escalar todos los números, digamos multiplicando todos los números por 10000 (por lo que los valores siguen siendo enteros pero pueden representarse en diez milésimas), este esquema todavía falla para números muy cercanos a cero, por ejemplo, la masa de electrones (9.1094 * 10⎻³¹ kg).

Esa es una cantidad física muy real (y extremadamente pequeña) , aquí hay algunas más con las que tendrá problemas. Y si argumenta que no es una cantidad física real (aunque esté en kg), considere:

10 kg (obviously physical quantity)
1 kg (same)
10⎻² kg (1/100 kg, or about 1/3 ounce) (also quite real)

Entonces ves a dónde voy con esto. El último que no puedes manejar tampoco.

Por supuesto, podría tener un campo especial dentro del número para escalar una porción entera hacia arriba o hacia abajo por un multiplicador variable; Dios, ahora acabas de inventar el punto flotante.

tcrosley
fuente
1
Pero puede asignar un valor físico mínimo (IIRC, para la masa era la masa equivalente a 1 electrón-voltio). Por ejemplo, puede medir la longitud del universo utilizando unidades de longitud de Planck con (IIRC) 200 dígitos. Puede hablar mentalmente sobre 1/10 de una longitud de Planck, pero físicamente no tiene sentido.
SJuan76
¿No quieres decir dividir por 10000? Multiplicar por 10000 solo haría que la suposición del abridor de hilo sea más probable que falle. También tal vez mi dispositivo no muestre la masa de electrones correctamente, pero debería ser 10 ^ -31
Mike
Me refiero a multiplicar por 10000. Si desea almacenar 1.0001 como un entero, debe multiplicarlo por 10000 antes de almacenarlo como 10001. Estaba usando caracteres de superíndices para el -31, tal vez no se muestran correctamente en todos los navegadores . Luce bien en Firefox.
tcrosley
@ SJuan76 Hay algo llamado a prueba del futuro. En 1850, podríamos hablar de una unidad de 10 ^ -20 metros (mucho más pequeña que un átomo, pero aún mucho más grande que la longitud de Planck), pero físicamente, hacerlo no tenía sentido. Entonces la gente descubrió la estructura interna de un átomo. Claro, los quarks parecen fundamentales, pero todo lo que realmente podemos decir es (a) que actúan de manera consistente con la forma en que esperamos que se comporten las partículas fundamentales, y (b) todavía no hemos encontrado una próxima tortuga. En 1850, podríamos decir las mismas dos cosas sobre los átomos. Si encontramos una próxima tortuga, las unidades de 1/10 Planck se vuelven bastante útiles.
Matthew Najmon
¡Es un error común pensar que el espacio o el tiempo se cuantifican en unidades de Planck! No puede representar el universo mediante una matriz de 4 dimensiones, al menos no en las teorías actuales ... Entonces, las fracciones de longitudes de Planck son físicamente significativas (pero los resultados que surgen de la Relatividad General y / o QM comienzan a explotar o contradiciéndose entre sí).
yatima2975
5

Primero, respondería a la pregunta ¿qué valores físicos pueden / deberían estar representados por un número entero?

Entero es una representación de un número natural (y las diferencias entre ellos) en un sistema informático, por lo que aplicarlo a cualquier otra cosa está mal. Por lo tanto, invocar distancias u otras cantidades que pertenecen al dominio continuo no es un argumento. Para tales cantidades hay representaciones de números reales. Y siempre puede elegir una unidad grande arbitrariamente y ajustar cualquier valor con una precisión dada.

Entonces, ¿cuáles son los valores físicos que son números naturales y pueden desbordar un entero de 64 bits?

Puedo pensar en dos. Número de objetos físicos (como átomos) y niveles de energía en los que puede estar un sistema cuántico. Esas son dos cosas que son estrictamente enteras. Ahora, sé que puedes dividir un átomo, pero aún produce una cantidad entera y no puedes dividirlo indefinidamente. Ambos pueden superar fácilmente el rango de 64 bits de entero sin signo . El número de átomos es mayor, y un átomo puede estar en más de un estado de energía.

Si la información es física o no, es muy discutible. Yo diría que no lo es. Por lo tanto, no diría que la cantidad de información es algo físico. Entonces, no es la cantidad de RAM ni nada de eso. Si permitiera esto, entonces el número de átomos fácilmente supera este número, porque necesita más de un átomo para almacenar un bit con la tecnología actual.

luk32
fuente
El conjunto N de números naturales incluye solo enteros no negativos. Sé lo que querías decir, pero "número natural" tiene una definición matemática específica inconsistente con la forma en que lo estás usando.
No estoy muy seguro. Los tipos enteros representan números naturales (dentro de un rango dado, lo cual está implícito). ¿No es eso cierto? Creo que asumiste que implicaba igualdad entre los conjuntos. Esto no es cierto, cualquier número natural puede ser representado por un número entero. Tenga en cuenta que también dije diferencias entre ellos. No tenía ganas de entrar en firmado / sin firmar era necesario. El tipo chamuscado solo es necesario cuando se trata de diferencias.
luk32
Si bien la fisicalidad de la información almacenada es discutible, y es una pregunta para los filósofos más que para los físicos, la fisicalidad de los mecanismos por los que se almacena es bastante segura. Por lo tanto, mientras que la aplicación de una serie de bits de información es cuestionable, el número de bits pena de chips de memoria RAM no lo es.
Matthew Najmon
@MatthewNajmon Por supuesto, estoy de acuerdo, por eso dejé la última oración. El número de bits de un chip RAM será menor que el número de átomos durante bastante tiempo, por lo que puede usar este último. En otras palabras, ¿por qué usar el número de bits, cuando puede usar el número de átomos del mismo chip RAM? Actualmente, un poco de información está representada por un estado en el que se encuentra un sistema físico, por lo que podría almacenar más de un bit por átomo, pero hoy en día está lejos de ser una aplicación, y todavía no veo cómo puede ser más que un número estados cuánticos de dicho sistema. Pero estoy totalmente de acuerdo con tu premisa.
luk32
4

Además de la respuesta de Jerry101, me gustaría ofrecer esta prueba muy simple y práctica para la corrección:

Suponga que asigna algo de memoria a través mallocde un SO de 64 bits. Supongamos que el asignador de memoria decide devolverle un bloque de memoria válido, del tamaño que solicitó, pero donde está configurado el bit 63.

En otras palabras, supongamos que existen algunos entornos de programación en los que 0xFFFFFFFFxxxxxxxxhay rangos de memoria legítimos a los que se puede devolver una llamada malloc.

La pregunta es, ¿su código seguirá funcionando según lo previsto?

Cuando ocurre una situación análoga a los sistemas operativos de 32 bits, algunos programas no funcionan correctamente si se les da direcciones de memoria "en la mitad superior". Originalmente, se pensaba que dichas direcciones de memoria solo estaban disponibles para el código privilegiado (sistemas operativos, controladores de dispositivos y hardware periférico), pero debido a la restricción del espacio de direcciones de 32 bits, los proveedores de sistemas operativos decidieron poner a disposición parte del espacio reservado para aplicaciones que lo soliciten.

Afortunadamente, es poco probable que ocurra esta situación para los programas de 64 bits por un tiempo, al menos no en una década.

Cuando esa situación finalmente suceda, significa que los procesadores y sistemas operativos direccionables de 128 bits se habrían convertido en la corriente principal para ese momento, y que podrían proporcionar un "entorno de emulación de 64 bits" para permitir que esas "aplicaciones heredadas" funcionen bajo supuestos similares a los actuales sistemas operativos de 64 bits.

Finalmente, tenga en cuenta que esta discusión solo se centra en las direcciones de memoria. Un problema similar con las marcas de tiempo debe tomarse con más precaución, porque ciertos formatos de marcas de tiempo asignan muchos bits de precisión a los microsegundos y, por lo tanto, dejan menos bits disponibles para representar el tiempo en el futuro. Estos problemas se resumen en el artículo de Wikipedia sobre el problema del año 2038 .

rwong
fuente
4

Esta es una pregunta que debe hacer caso por caso. No debe usar una suposición general de que la aritmética de 64 bits no se desbordará, porque incluso cuando las cantidades correctas estén en un rango mucho menor, una fuente de datos maliciosa podría terminar dándole cantidades irracionales que podrían desbordarse, y es mejor ser preparado para esta situación que ser golpeado inesperadamente.

Hay algunos casos en los que tiene sentido escribir código que depende de un desbordamiento de números de 64 bits. La clase principal de ejemplo que conozco son los contadores, donde el contador se incrementa cada vez que se usa. Incluso a un ritmo de un incremento por nanosegundo (no práctico), llevaría más de un siglo desbordarse.

Tenga en cuenta que si bien al principio puede parecer "siempre incorrecto en principio" confiar en el "tiempo hasta el fallo" para la corrección de un sistema, lo hacemos todo el tiempo con autenticación / inicio de sesión. Dado el tiempo suficiente (para el forzamiento bruto), cualquier sistema de este tipo (ya sea basado en contraseñas, claves privadas, tokens de sesión, etc.) está roto.

R ..
fuente
2

¿Es POSIBLE que una cantidad física no se ajuste a 64 bits? Por supuesto. Otros han señalado contar el número de átomos en el sol o el número de milímetros para la próxima galaxia. Si dichos casos son relevantes para su aplicación depende de cuál sea su aplicación. Si está contando el número de artículos en un contenedor determinado en su almacén, 16 bits probablemente serían suficientes. Si está compilando estadísticas sobre la cantidad de personas en el mundo que cumplen varias condiciones, debe poder registrar miles de millones, por lo que necesitará más de 32 bits, momento en el que presumiblemente iría a 64 (como pocas computadoras tienen soporte incorporado para números de 37 bits, etc. Si esta es una aplicación química que cuenta moles por átomos, 64 bits no serán suficientes.

Técnicamente, el hecho de que hoy en día ninguna computadora tenga 2 ^ 64 bytes de memoria no significa necesariamente que un índice de matriz nunca podría ser más de 2 ^ 64. Existe un concepto llamado "matriz dispersa" donde muchos de los elementos de la matriz no se almacenan físicamente en ningún lugar, y se supone que dichos valores no almacenados tienen algún valor predeterminado como nulo o cero. Pero supongo que si está escribiendo una función para buscar una matriz o lista de algún tipo, y el tamaño del campo que está utilizando para mantener el índice en la matriz es más del doble de la dirección más grande posible, luego verificando si hay desbordamiento cuando agregar dos índices no sería estrictamente necesario.

Arrendajo
fuente
Buen punto sobre matrices dispersas. Además, incluso con una matriz que está completamente poblada, todavía es completamente posible, aunque bastante lento, y en algunos casos es bastante necesario, trabajar con una matriz demasiado grande para caber la totalidad de la matriz en la RAM de una vez. Esto se hace simplemente almacenando todo en un medio más lento pero mucho más grande, como un disco duro, y luego tirando a la RAM solo los pocos elementos con los que está trabajando en este momento. Incluso un HDD pequeño es lo suficientemente grande como para contener una matriz mucho más grande de lo que el OP quiere asumir.
Matthew Najmon
0

No es razonable suponer que un entero de 64 bits puede contener todos los números. Múltiples razones:

  1. El entero máximo y mínimo de 64 bits son números finitos. Para cada número finito existe un número finito más grande y más pequeño.

  2. Los cálculos con números de 128 bits y 256 bits se utilizan actualmente en varios lugares. Muchos procesadores tienen instrucciones específicas que funcionan con enteros de 128 bits.

  3. Hace 20 años, un disco de 1 GB se consideraba "grande". Hoy un disco de 1 TB se considera pequeño. Hace 20 años, las computadoras de escritorio promedio tenían aproximadamente 16 MB de RAM. Mi escritorio actual tiene más de 16 GB de RAM. El espacio en disco duro y la RAM han crecido exponencialmente en el pasado, y se prevé que crezca exponencialmente en el futuro. A menos que alguien pueda encontrar una muy buena razón por la que debería dejar de crecer, no tiene sentido suponer que se detendrá.

Peter
fuente