¿Cuál es el número más alto con el que una PC ha podido contar?

Esta es una pregunta fundamental de la máquina de Turing, por lo que considerar el conteo es una función, según la tesis de Church-Turing, no se trata de un problema de poder calcular o no, sino de la complejidad del tiempo y el espacio. Cualquier cosa es computable, es solo una cuestión de cuánto tiempo tomará. ¿Tiene tiempo para ejecutar su algoritmo para siempre y observar el mayor resultado?

Un matemático húngaro llamado Tibor Radó intentó resolver esto, inventó los números de castores Busy, algo similares a los números de Ackermann pero mucho más exponenciales, simbolizados como BB ( n ) donde n es la entrada, para tener una idea:

BB (1) = 1

BB (2) = 6

BB (3) = 21

BB (4) = 107

Y BB (5) = 8,690,333,381,690,951 (sí, ¡eso aumentó rápidamente!)

BB (10) =? Todavia no sabemos

Entonces, hay una forma matemática definida de que está inventando estos números, para que no caigamos en la falacia de “el número más grande que un humano puede decir”, entonces mi hermano pequeño piensa en sumar uno y arruinar las cosas … Sr. Rado usó esta función BB para almacenar los números y descubrió que la única limitación es la memoria y el tiempo, aparte de que todo es computable.


Para obtener más información al respecto, consulte este interesante artículo: Busy Beavers y Quest for Big Numbers.

Responder a los detalles de la pregunta, lo que implica contar en sentido literal, es decir, uno a la vez … depende del idioma y del sistema operativo, y muy raramente está limitado por el hardware.

Muchos lenguajes de programación ofrecen una representación de enteros que usan 64 bits. El número más alto que puede ser representado por un entero de 64 bits sin signo es 18,446,744,073,709,551,615. Si agrega 1 a este valor, entonces (dependiendo de la implementación) obtendrá un error o el valor pasará a 0.

Sin embargo, otros lenguajes de programación, o por ejemplo, sistemas de álgebra computacional, ofrecen representaciones numéricas de “precisión arbitraria”. En este caso, la limitación es la memoria disponible. Tampoco memoria física, ya que partes de la variable pueden intercambiarse a disco (memoria virtual). En las versiones de Windows de 64 bits, el espacio de memoria máximo direccionable dentro de una aplicación es de 8 terabytes. Dejando de lado el hecho de que parte de esta memoria se usa para cosas como otras variables, el código del programa en sí, la pila, etc., esto es 147,573,952,589,676,412,928 bytes o 1,180,591,620,717,411,303,424 bits. El número de valores posibles, entonces, es dos elevado a este poder; o aproximadamente [matemáticas] 10 ^ {3.5539 \ veces 10 ^ {20}} [/ matemáticas]. Ese es un número con aprox. [matemática] 3.5539 \ por 10 ^ {20} [/ matemática] dígitos decimales.

Es posible diseñar un esquema para contar más allá de este número, por supuesto, mediante el uso de una granja de discos duros e ideando un esquema para extender la representación del número más allá de la memoria virtual, a este almacenamiento adicional.

En resumen, dado que no hay límite en principio para la cantidad de almacenamiento que uno puede conectar a una PC, en realidad no hay límite en cuanto a cuánto puede contar. Por supuesto, puede llevar mucho tiempo completar el conteo, pero ese es otro asunto.

Depende exactamente de lo que quieres decir.

Si por conteo, quiere decir que la computadora tiene que ser capaz de representar cada número que le precede, como es el caso en el código de ejemplo que proporcionó, entonces descartamos números racionales e irracionales (o números de coma flotante como los llamaría) en informática). En ese caso, lo que usaríamos es algo así como la Estructura BigInteger. Sin embargo, a pesar de que esa documentación dice que “representa un entero con signo arbitrariamente grande”, puede arrojar una excepción OutOfMemoryException, porque eventualmente, no hay suficiente memoria para contener toda la información que necesitamos para representar un número. Stack Overflow tiene un tema sobre esto: ¿Hay un límite superior para BigInteger?

Para resumir y simplificar lo que hay en esa publicación, un entero normal está representado por 64 bits por una computadora (al menos en un sistema de 64 bits, también hay sistemas de 32 bits que solo usan 32 bits). Cada bit representa una potencia diferente de 2, que aumenta a medida que avanzamos hacia la izquierda, comenzando con [matemática] 2 ^ 0 = 1 [/ matemática]. Si piensa en números decimales, hacen lo mismo, excepto que usan potencias de 10 y cada potencia puede tener un factor de hasta 9. Como ejemplo, si solo tuviéramos dos bits para trabajar, entonces nuestro número más grande sería 0b11 (el 0b al frente significa que es un número binario, no un número base 10), o [matemáticas] 1 * 2 ^ 1 + 1 * 2 ^ 0 = 3 [/ matemáticas]. Otra forma de encontrar que 3 es el máximo es darse cuenta de que [matemáticas] \ text {0b100} – \ text {0b001} = (1 * 2 ^ 2 + 0 * 2 ^ 1 + 0 * 2 ^ 0) – (0 * 2 ^ 2 + 0 * 2 ^ 1 + 1 * 2 ^ 0) = 2 ^ 2 – 1 = 3 = \ text {0b11} [/ math] (recuerde que estos son números binarios, restando 1 del 0 más a la derecha) arrastrado “el 1). Entonces, si volvemos al caso de 64 bits como en las computadoras modernas, esto significa que el número entero más grande que podemos representar en un número entero normal es [matemática] 2 ^ {64} – 1 [/ matemática], o 18,446,744,073,709,551,616. Eso es bastante grande, pero usando la idea detrás de BigInteger, podemos llegar aún más alto.

La forma en que funciona BigInteger es que aumenta la cantidad de bytes que usamos para representar el entero mediante la concatenación de múltiples bits de múltiples enteros normales. Esto es diferente de decir que 2 y 2 son 22. En cambio, está concatenando la representación de bits. Entonces, si nuestros enteros normales tuvieran 2 bits de longitud, entonces 2 y 2 serían 0b10 y 0b10 => 0b1010 en binario, que es 10 en decimal. Esto aumenta nuestro número máximo de [matemáticas] 2 ^ 2 – 1 [/ matemáticas] con solo 2 bits a [matemáticas] 2 ^ 4 – 1 [/ matemáticas] con 4 bits. Dado que nuestro entero normal más grande es [math] 2 ^ {64} – 1 [/ math], solo podemos hacer un seguimiento de [math] 2 ^ {64} – 1 [/ math] enteros normales (dando a cada uno un número único como un identificador). Eso significa que podemos tener [math] 2 ^ {64} – 1 [/ math] conjuntos de 64 bits o [math] 64 * (2 ^ {64} – 1) [/ math] bits. El número máximo que todos esos bits podrían representar sería [matemática] 2 ^ {64 * (2 ^ {64} – 1)} – 1 [/ matemática]. Como han dicho otras respuestas, en realidad contar hasta ese número llevaría una eternidad y sería bastante tonto.

Sin embargo, si está menos preocupado por contar hasta ese número y le importa más cuál es el número más grande que podemos representar, entonces no tenemos límite, ya que somos libres de definir cualquier representación para los números. Por ejemplo, si en lugar de que cada bit sea una potencia de 2, podríamos decir que es una potencia de 10. Ya no podríamos representar todos los enteros como nuestro primer número … 0001 sería 1, pero nuestro segundo número … 00010 sería 10. Pero ahora podríamos representar un número hasta [matemáticas] 10 ^ {64 * (2 ^ {64} – 1)} – 1 [/ matemáticas].

Un ejemplo más práctico son los números de coma flotante que mencioné antes. También suelen usar 64 bits para representar un número decimal. Representan números haciendo que algunos bits sean una base y algunos bits sean un exponente de esa base, pero esto significa que no pueden representar exactamente todos los números dentro de su rango. Esto, en cambio, permite que su rango aumente a [matemáticas] 10 ^ {38} [/ matemáticas], mucho más grande que el número entero máximo de [matemáticas] 2 ^ {64} [/ matemáticas].

Y, por último, como un caso de uso práctico para números realmente grandes, el número primo más grande que hemos descubierto se hizo usando computadoras. Este número es [matemática] 2 ^ {74207281} – 1 [/ matemática]. Eso sí que es grande.

El factor limitante no es de lo que es capaz la PC. El factor limitante es usted , su esperanza de vida y la del universo.

Las PC modernas admiten de forma nativa variables de 64 bits. Los lenguajes de nivel superior como Python admiten de forma nativa enteros largos que se almacenan en matrices grandes, tan grandes como lo permita la capacidad de memoria, pero comencemos con el conteo utilizando un registro simple de 64 bits, digamos en un lenguaje de bajo nivel como C.

Si tiene una PC fuerte y loca a su disposición, capaz de 250,000 MIPS (millones de instrucciones por segundo), esperará aproximadamente 2.5 años para que se produzca un desbordamiento con su registro único. Eso todavía es factible, más o menos. Entonces podemos imaginar que las PC cuenten hasta [math] 2 ^ {64} [/ math].

Pero supongamos que escribe su programa de conteo en Python, por ejemplo, y para facilitar las cosas, supongamos que su sistema limita las variables a solo 1 KB de almacenamiento (eso es aproximadamente una millonésima parte de lo que los procesadores pueden manejar realmente). Así que ahora estás contando todo el camino

[matemáticas] 2 ^ {8000} [/ matemáticas].

Su PC puede manejar fácilmente dicho conteo, en cuanto a memoria. De hecho tu teléfono puede. Pero no puedes. Incluso con la supercomputadora más grande del mundo, tal vez puedas hacer 200 mil millones de MIPS. Eso es

200,000,000,000,000,000

instrucciones por segundo. Pero ya ve, eso afeita un mero [matemático] 2 ^ {57} [/ matemático] de su objetivo cada segundo, o [matemático] 2 ^ {82} [/ matemático] cada año, incluso si su código de bytes compilado incrementa un entero largo en una sola instrucción. Eso significa que todavía estás viendo alrededor de [matemáticas] 2 ^ {7918} [/ matemáticas] años. Si prefiere la base 10, eso es más de [matemáticas] 10 ^ {2300} [/ matemáticas] años.

Tenga en cuenta bien: eso no es 2.300 años. Eso es diez para el poder 2.300 años.

Ninguna PC real contó más de [math] 2 ^ {70} [/ math], y dudo que incluso haya estado cerca de eso.

Dado que la implementación de este algoritmo no tiene ningún valor, aparte de hacer un calentador de ambiente no muy bueno, también podría calcular el límite teórico.

Si ‘contador’ es una variable entera sin signo en un registro de 64 bits, entonces su valor máximo sería [matemática] 2 ^ {64} [/ matemática]. Podrías medir el tiempo que lleva hacer unos cientos de iteraciones y extrapolarlo para encontrar cuánto tiempo llevaría hacer todo. Por supuesto, también podría simplemente establecer todos los bits en 1 en ese registro, probablemente en una instrucción, por lo que el tiempo necesario para ‘contar’ sería de un ciclo de instrucciones. No es muy interesante.

Si ‘contador’ es realmente algún tipo de valor dinámico que se expande usando la memoria para ser tan grande como sea necesario, el conteo real tomará más tiempo. Pero todavía hay un atajo: configure cada bit de memoria en 1 (suponiendo que todos los 1 representen el valor máximo). Todavía podría hacerlo en un tiempo bastante corto (segundos en lugar de años). Entonces tendría que determinar qué número era, pero sería una función simple de la cantidad de memoria virtual asignada a mi proceso, o la RAM disponible, o el espacio disponible en el disco, dependiendo de su implementación.

Todavía no es muy interesante.

Si la verdadera pregunta es “qué tan rápido es esta PC”, hay formas más fáciles y rápidas de llegar a una cifra.

Con la clase Java BigInteger no hay un máximo obvio.

http://docs.oracle.com/javase/7/

Pero realmente, depende de la implementación de esta clase. Sería un ejercicio divertido determinar la fórmula real.

Además, podría pensar en una clase numérica que utilice el disco duro o la nube como almacenamiento de respaldo para el número. Sospecho que el límite podría ser infinito.