Hasta Cuanto sabe contar el Ordenador?

Mi hijo de 2 años sabe contar hasta 10, despues comienza a "improvisar", por lo que puedo decir que sabe contar hasta 10.
En el computador es similar, sumas repetidas veces 1 a un número, eventualmente el pc se equivocará, si, el computador se puede equivocar, de hecho existe toda una ciencia dedicada a acotar errores en los calculos del PC, llamada error numérico.

Para entender como se puede equivocar un computador, primero tenemos que diferenciar como este entiende los números, para ellos existen 2 formas, los Integer (enteros) y los float (decimales o punto flotante), como todos los datos de un PC, ambos son almacenados como secuencias de bit, (0 o 1) y estos difieren en como se interpretan los bits.

Para el primer caso (integer) es bastante simple, pero nos ayudará a entender los tipo float.

integer

Los integer vienen en distintos tamaños dependiendo del numero de bits que se utilizan para almacenarlos, por ejemplo un integer de 4 bits escribirá los números del siguiente modo:

0=0000
1=0001
2=0010
3=0011
4=0100
5=0101
6=0110
7=0111

con 4 bits, podemos contar solo hasta 7 por que el ultimo bit es utilizado para denotar el signo del número (positivo o negativo), de este modo, los números negativos se escribirían del siguiente modo

-1=1000
-2=1001
-3=1010
-4=1011
-5=1100
-6=1101
-7=1110
-8=1111

en general podemos decir que para en un integer de n bits, podemos representar números de hasta 2^{n-1}-1 para el caso positivo y 2^{n-1} para el negativo.

Los integer del pc puede ser de distintos tamaños, en general de 32, 64 o 128 bits, donde los tamaños máximos son los siguientes:

32 bit: 2^{31}-1 = 2.147.483.647
64 bit: 2^{63}-1 = 9.223.372.036.854.775.807
128 bit: 2^{127}-1 = 170.141.183.460.469.231.731.687.303.715.884.105.727

Ahora que sucede cuando excedemos este número? bueno depende del lenguaje de programación.

Python

Python 3.x es un caso especial, maneja los integer de otro modo, por lo que no tiene limite, esto lo hace considerablemente más lento, pero puede calcularlos tan largos como quiera (al menos eso obtuve en mis resultados).

>>> n = (2**1000)
>>> print(n)
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
>>> type(n)
<class 'int'>

lo anterior es bastante comodo, pero lo hace lento, por eso python tiene la librería numpy que trabaja de la forma que funciona nativamente la CPU, obteniendo cálculos mas rápidos, lo primero que es interesante es que cuando un integer de 32 bits supera su tamaño máximo, para a ser uno de 64 bits

>>> n = np.int32(2**31-1)
>>> print(n)
2147483647
>>> type(n)
<class 'numpy.int32'>
>>> print(n+1)
2147483648
>>> type(n + 1)
<class 'numpy.int64'>

si forzamos que n+1 sea de 32 bits el contador comienza desde el número mas negativo que se puede representar:

>>> np.int32(n + 1)
-2147483648

lo anterior se debe a que en binario 2147483647 = 011111111111111111111111111111111, por lo que al sumar 1, da el resultado 1000000000000000000000000000000, el cual es -2147483648.

por otro lado, el int más grande en numpy es de 64 bits, ¿que hará si no puede aumentar su tamaño?,¿pasará a otro tipo de integer de mayor capacidad o comenzará desde el negativo?

>>> n = np.int64(2**63-1)
>>> print(n)
9223372036854775807
>>> type(n)
<class 'numpy.int64'>
>>> print(n+1)
-9223372036854775808
>>> type(n + 1)
<class 'numpy.int64'>

claramente comienza desde el negativo por que el integer más grante que está implementado en numpy es el de 64 bits.

R

En R los enteros son por defecto de 32 bits, existen librerias para trabajar enteros de 64 bits, pero no son nativos. podemos ver que R avisará que se superó el máximo, por lo que podemos estar tranquilos de que no habrán comportamientos extraños.

> n = 2147483647L
> n+1L
[1] NA
Warning message:
In n + 1L : NAs produced by integer overflow
Julia

Julia comete el mismo error de python, sin avisar que cometerá un error.

julia> n = Int32(2147483647)
2147483647

julia> n + Int32(1)
-2147483648

por ultimo Juia puede manejar enteros de hasta 128 bits, permitiendoles contar hasta: 170.141.183.460.469.231.731.687.303.715.884.105.727, ;uego de eso, volverá al negativo.

Floats o punto flotante

El general el PC usa floats en vez de integers, pero la explicación anterior sirve como ayuda para entender este caso.

Acá se pone un poco mas compleja la cosa, imagina que tienes un número muy muy largo, no tiene mucho sentido utilizar todos lo digitos, solo los ultimos serán los significativos o relevantes, por eso existe la notación cientifica, donde por ejemplo: 123.456.789.012.345.678.901.234.567.890 se escribir como 1,23456 * 10^{29}, descartando los números no significativos, lo mismo hace el PC para almacenar números tipo float pero en binario.

En general el pc usa floats de 64 bitts llamados doubles, pero para este ejercicio lo haremos con floats de 32 bits o single. En un float de 32 bits, de los 32 bits, 24 se utilizan para escribir los dígitos significativos, mientras que los 8 restantes se utilizan para el exponente de la notación científica.

Teoricamente, el número más grande que puede almacenar un float de 32 bits es del orden de 2^{2^{7}-1} = 2^{127} \sim 10^{38}, pero la pregunta no es cual es el número más grande, es hasta cuanto puede contar el PC.

Cuando cotamos vamos sumando 1 a un número hasta que ya no sabemos calcular el número siguiente. ¿En que momento al sumar 1 a un float, entregará un resultado erroneo?

Respondamos a la pregunta usando Julia que tiene un excelente manejo de tipos de datos, para ello, contaremos desde 0 en integer de 64 bitsy float de 32, cuando estos en alguna suma arrojen resultado distintos, significa que el float se equivoco, por lo que no puede contar más.

Esto se debe a que la suma de 1 a un número muy grande termina siendo no significativa.

julia> float = Float32(0)
0.0f0

julia> int = Int64(0)
0

julia> while int == float
           float = float + 1
           int = int + 1
       end

julia> Int64(float)
16777216

julia> int
16777217

exactamente en 16.777.216 al sumar 1, el 1 es tan insignificante que el resultado de la suma sera el mismo número anterior, por lo que dejará de contar quedandose pegado en: 16.777.216.

en python es la misma historia (pero demora muuuucho tiempo):

>>> i = np.int64(0)
>>> f = np.float32(0)
>>> while i == f:
...   i = i + np.int64(1)
...   f = f + np.float32(1)
... 
>>> print(i)
16777217
>>> print(f)
16777216.0

este número 16.777.216 corresponde a 2^24, donde justamente 24 es la cantidad de bit utilizados para almacenar las cifras significativas.

No se ve como un número tán grande, pero el pc en verdad utiliza floats de doble presición, osea de 64 bits, los cuales usan 12 bits para el exponente y 56 para las cigras significativas, por lo que extrapolando este experimento el número más grande sería $$ 2^52$$ = 4.503.599.627.370.495

Que sudecerá en excel al sumar 1 a ese número?

file

bueno, podemos ver que Excel se equivicó, asi que ten cuidado se te pones a contar trigo para adquirir la licencia del ajedréz, por que con Excel no podrás contar la cantidad de granos que necesitaras. (si no entendiste el chiste, puedes ver este video: https://www.youtube.com/watch?v=ziWYaYjJ8zk)

Saludos, espero que les haya gustado.

Print Friendly, PDF & Email