¿Por qué los números decimales no se pueden representar exactamente en binario?

Se han publicado varias preguntas en SO sobre la representación de punto flotante. Por ejemplo, el número decimal 0.1 no tiene una representación binaria exacta, por lo que es peligroso usar el operador == para compararlo con otro número de coma flotante. Entiendo los principios detrás de la representación de punto flotante.

Lo que no entiendo es por qué, desde una perspectiva matemática, ¿los números a la derecha del punto decimal son más "especiales" que los de la izquierda?

Por ejemplo, el número 61.0 tiene una representación binaria exacta porque la parte integral de cualquier número siempre es exacta. Pero el número 6.10 no es exacto. Todo lo que hice fue mover el decimal un lugar y de repente me fui de Exactopia a Inexactville. Matemáticamente, no debería haber una diferencia intrínseca entre los dos números, son solo números.

Por el contrario, si muevo el decimal un lugar en la otra dirección para producir el número 610, todavía estoy en Exactopia. Puedo seguir en esa dirección (6100, 610000000, 610000000000000) y siguen siendo exactos, exactos, exactos. Pero tan pronto como el decimal cruza algún umbral, los números ya no son exactos.

¿Que esta pasando?

Editar: para aclarar, quiero alejarme de la discusión sobre las representaciones estándar de la industria, como IEEE, y seguir con lo que creo que es la forma matemáticamente "pura". En la base 10, los valores posicionales son:

... 1000  100   10    1   1/10  1/100 ...

En binario, serían:

... 8    4    2    1    1/2  1/4  1/8 ...

Tampoco existen límites arbitrarios para estos números. Las posiciones aumentan indefinidamente hacia la izquierda y hacia la derecha.

Los números decimales se pueden representar exactamente, si tiene suficiente espacio, solo que no mediante números de punto binario flotantes . Si usa un tipo de coma decimal flotante (p. Ej.System.Decimal en .NET), muchos valores que no se pueden representar exactamente en coma flotante binaria se pueden representar exactamente.

Miremos de otra manera: en la base 10 con la que es probable que te sientas cómodo, no puedes expresar 1/3 exactamente. Es 0.3333333 ... (recurrente). La razón por la que no puede representar 0.1 como un número de punto flotante binario es exactamente por la misma razón. Puede representar 3, 9 y 27 exactamente, pero no 1/3, 1/9 o 1/27.

El problema es que 3 es un número primo que no es un factor de 10. Eso no es un problema cuando quieres multiplicar un número por 3: siempre puedes multiplicar por un número entero sin tener problemas. Pero cuando divide entre un número que es primo y no es un factor de su base, puede tener problemas (y lo hará si intenta dividir 1 entre ese número).

Aunque 0.1 generalmente se usa como el ejemplo más simple de un número decimal exacto que no se puede representar exactamente en coma flotante binaria, posiblemente 0.2 es un ejemplo más simple ya que es 1/5, y 5 es el primo que causa problemas entre decimal y binario .

Nota al margen para tratar el problema de las representaciones finitas:

Algunos tipos de coma decimal flotante tienen un tamaño fijo como System.Decimalotros como java.math.BigDecimal"arbitrariamente grandes", pero alcanzarán un límite en algún momento, ya sea la memoria del sistema o el tamaño máximo teórico de una matriz. Sin embargo, este es un punto completamente separado del principal de esta respuesta. Incluso si tuviera un número de bits genuinamente arbitrariamente grande con el que jugar, no podría representar el decimal 0.1 exactamente en una representación de punto binario flotante. Compare eso con lo contrario: dado un número arbitrario de dígitos decimales, puede representar exactamente cualquier número que sea exactamente representable como un punto binario flotante.

Por ejemplo, el número 61.0 tiene una representación binaria exacta porque la parte integral de cualquier número siempre es exacta. Pero el número 6.10 no es exacto. Todo lo que hice fue mover el decimal un lugar y de repente me fui de Exactopia a Inexactville. Matemáticamente, no debería haber una diferencia intrínseca entre los dos números, son solo números .

Alejémonos por un momento de los detalles de las bases 10 y 2. Preguntemos, en base b, ¿qué números tienen representaciones finales y qué números no? Un momento de reflexión nos dice que un número xtiene una brepresentación de terminación si y solo si existe un número entero ntal que x b^nsea ​​un número entero.

Entonces, por ejemplo, x = 11/500tiene una representación final de 10, porque podemos elegir n = 3y luego x b^n = 22, un número entero. Sin embargo x = 1/3, no, porque lo nque sea que elijamos no podremos deshacernos del 3.

Este segundo ejemplo nos lleva a pensar en factores, y podemos ver que para cualquier racional x = p/q (se supone que está en los términos más bajos), podemos responder la pregunta comparando las factorizaciones primarias de by q. Si qtiene algún factor primo que no esté en la factorización prima b, nunca podremos encontrar un adecuado npara deshacernos de estos factores.

Por lo tanto, para la base 10, cualquier lugar p/q donde qtenga factores primos distintos de 2 o 5 no tendrá una representación final.

Entonces, volviendo a las bases 10 y 2, vemos que cualquier racional con una representación final de 10 tendrá la forma p/qexactamente cuando qsolo tiene 2s y 5s en su factorización prima; y ese mismo número tendrá una representación de terminación 2 exactamente cuando qsolo tiene2 s en su factorización prima.

¡Pero uno de estos casos es un subconjunto del otro! Cuando

qsolo tiene 2s en su factorización principal

obviamente también es cierto que

qsólo tiene 2S y 5S en su mejor momento factorización

o, dicho de otra manera, siempre que p/qtenga una representación final de 2, p/qtenga una representación final de 10 . Sin embargo, lo contrario no se cumple : siempre que qtenga un 5 en su factorización prima, tendrá una representación final de 10, pero no una representación final de 2. Este es el0.1 ejemplo mencionado por otras respuestas.

Entonces, tenemos la respuesta a su pregunta: dado que los factores primos de 2 son un subconjunto de los factores primos de 10, todos los números que terminan en 2 son números que terminan en 10, pero no al revés.No se trata de 61 versus 6.1, se trata de 10 versus 2.

Como nota de cierre, si por alguna gente capricho utilizados (por ejemplo) de base 17, pero nuestros ordenadores utilizados base 5, su intuición nunca habría sido desviados por esto - no habría ninguna (no cero no enteros,) los números que terminó ¡en ambos casos!

La razón raíz (matemática) es que cuando se trata de enteros, son infinitamente contables .

Lo que significa que, aunque hay una cantidad infinita de ellos, podríamos "contar" todos los elementos de la secuencia, sin omitir ninguno. Eso significa que si queremos obtener el artículo en el610000000000000 colocar posición n de la lista, podemos resolverlo mediante una fórmula.

Sin embargo, los números reales son infinitamente infinitos . No puedes decir "dame el número real en la posición 610000000000000" y obtener una respuesta. La razón es porque, incluso entre 0y1 , hay un número infinito de valores, cuando está considerando valores de coma flotante. Lo mismo es válido para dos números de coma flotante.

Más información:

http://en.wikipedia.org/wiki/Countable_set

http://en.wikipedia.org/wiki/Uncountable_set

Actualización: Mis disculpas, parece que he malinterpretado la pregunta. Mi respuesta es sobre por qué no podemos representar cada valor real , no me había dado cuenta de que el punto flotante se clasificaba automáticamente como racional.

Para repetir lo que dije en mi comentario al Sr. Skeet: nos podemos representar 1/3, 1/9, 1/27, o cualquier racionales en notación decimal. Lo hacemos agregando un símbolo adicional. Por ejemplo, una línea sobre los dígitos que se repiten en la expansión decimal del número. Lo que necesitamos para representar números decimales como una secuencia de números binarios son 1) una secuencia de números binarios, 2) un punto de raíz y 3) algún otro símbolo para indicar la parte repetitiva de la secuencia.

La notación de citas de Hehner es una forma de hacerlo. Utiliza un símbolo de cita para representar la parte repetida de la secuencia. El artículo: http://www.cs.toronto.edu/~hehner/ratno.pdf y la entrada de Wikipedia: http://en.wikipedia.org/wiki/Quote_notation .

No hay nada que diga que no podemos agregar un símbolo a nuestro sistema de representación, por lo que podemos representar racionales decimales exactamente usando la notación de comillas binarias, y viceversa.

BCD: decimal codificado en binario : las representaciones son exactas. No son muy eficientes en cuanto al espacio, pero eso es una compensación que debe hacer para la precisión en este caso.

Es la misma razón por la que no puede representar 1/3 exactamente en la base 10, debe decir 0.33333 (3). En binario, es el mismo tipo de problema, pero solo ocurre para un conjunto diferente de números.

(Nota: agregaré 'b' para indicar números binarios aquí. Todos los demás números se dan en decimal)

Una forma de pensar sobre las cosas es en términos de algo como la notación científica. Estamos acostumbrados a ver números expresados ​​en notación científica como, 6.022141 * 10 ^ 23. Los números de coma flotante se almacenan internamente usando un formato similar: mantisa y exponente, pero usando potencias de dos en lugar de diez.

Su 61.0 podría reescribirse como 1.90625 * 2 ^ 5, o 1.11101b * 2 ^ 101b con la mantisa y los exponentes. Para multiplicar eso por diez y (mover el punto decimal), podemos hacer:

(1.90625 * 2 ^ 5) * (1.25 * 2 ^ 3) = (2.3828125 * 2 ^ 8) = (1.19140625 * 2 ^ 9)

o con la mantisa y los exponentes en binario:

(1.11101b * 2 ^ 101b) * (1.01b * 2 ^ 11b) = (10.0110001b * 2 ^ 1000b) = (1.00110001b * 2 ^ 1001b)

Tenga en cuenta lo que hicimos allí para multiplicar los números. Multiplicamos las mantisas y sumamos los exponentes. Luego, dado que la mantisa terminó más de dos, normalizamos el resultado golpeando el exponente. Es como cuando ajustamos el exponente después de hacer una operación con números en notación científica decimal. En cada caso, los valores con los que trabajamos tenían una representación finita en binario, por lo que los valores generados por las operaciones básicas de multiplicación y suma también produjeron valores con una representación finita.

Ahora, considere cómo dividiríamos 61 entre 10. Comenzaríamos dividiendo las mantisas, 1.90625 y 1.25. En decimal, esto da 1.525, un buen número corto. Pero, ¿qué es esto si lo convertimos a binario? Lo haremos de la manera habitual: restando la mayor potencia de dos siempre que sea posible, al igual que convertir decimales enteros en binarios, pero usaremos potencias negativas de dos:

1.525 - 1 * 2 ^ 0 -> 1
0.525 - 1 * 2 ^ -1 -> 1
0,025 - 0 * 2 ^ -2 -> 0
0,025 - 0 * 2 ^ -3 -> 0
0,025 - 0 * 2 ^ -4 -> 0
0,025 - 0 * 2 ^ -5 -> 0
0,025 - 1 * 2 ^ -6 -> 1
0.009375 - 1 * 2 ^ -7 -> 1
0.0015625 - 0 * 2 ^ -8 -> 0
0.0015625 - 0 * 2 ^ -9 -> 0
0.0015625 - 1 * 2 ^ -10 -> 1
0.0005859375 - 1 * 2 ^ -11 -> 1
0.00009765625 ...

UH oh. Ahora estamos en problemas. Resulta que 1.90625 / 1.25 = 1.525, es una fracción que se repite cuando se expresa en binario: 1.11101b / 1.01b = 1.10000110011 ... b Nuestras máquinas solo tienen tantos bits para contener esa mantisa y así redondearán la fracción y asume ceros más allá de cierto punto. El error que ve cuando divide 61 por 10 es la diferencia entre:

1.100001100110011001100110011001100110011 ... b * 2 ^ 10b
y, digamos:
1.100001100110011001100110b * 2 ^ 10b

Es este redondeo de la mantisa lo que conduce a la pérdida de precisión que asociamos con los valores de coma flotante. Incluso cuando la mantisa se puede expresar exactamente (por ejemplo, al sumar solo dos números), aún podemos obtener una pérdida numérica si la mantisa necesita demasiados dígitos para ajustarse después de normalizar el exponente.

Realmente hacemos este tipo de cosas todo el tiempo cuando redondeamos los números decimales a un tamaño manejable y solo le damos los primeros dígitos. Debido a que expresamos el resultado en decimal, se siente natural. Pero si redondeamos un decimal y luego lo convertimos a una base diferente, se vería tan feo como los decimales que obtenemos debido al redondeo de coma flotante.

Esta es una buena pregunta.

Toda su pregunta se basa en "¿cómo representamos un número?"

TODOS los números se pueden representar con representación decimal o con representación binaria (complemento de 2). Todos ellos !!

PERO algunos (la mayoría de ellos) requieren un número infinito de elementos ("0" o "1" para la posición binaria, o "0", "1" a "9" para la representación decimal).

Como 1/3 en representación decimal (1/3 = 0.3333333 ... <- con un número infinito de "3")

Como 0.1 en binario (0.1 = 0.00011001100110011 .... <- con un número infinito de "0011")

Todo está en ese concepto. Dado que su computadora solo puede considerar un conjunto finito de dígitos (decimal o binario), solo algunos números pueden representarse exactamente en su computadora ...

Y como dijo Jon, 3 es un número primo que no es un factor de 10, por lo que 1/3 no puede representarse con un número finito de elementos en la base 10.

Incluso con aritmética con precisión arbitraria, el sistema de posición de numeración en la base 2 no puede describir completamente 6.1, aunque puede representar 61.

Para 6.1, debemos usar otra representación (como la representación decimal, o IEEE 854 que permite la base 2 o la base 10 para la representación de valores de coma flotante)

Si haces un número lo suficientemente grande con coma flotante (como puede hacer exponentes), entonces también terminarás con inexactitud frente al punto decimal. Por lo tanto, no creo que su pregunta sea completamente válida porque la premisa es incorrecta; no es el caso de que el desplazamiento por 10 siempre cree más precisión, porque en algún momento el número de coma flotante tendrá que usar exponentes para representar la amplitud del número y también perderá algo de precisión de esa manera.

Me sorprende que nadie haya dicho esto todavía: use fracciones continuas . Cualquier número racional puede representarse finitamente en binario de esta manera.

Algunos ejemplos:

1/3 (0.3333 ...)

0; 3

5/9 (0.5555 ...)

0; 1, 1, 4

10/43 (0.232558139534883720930 ...)

0; 4, 3, 3

9093/18478 (0.49209871198181621387596060179673 ...)

0; 2, 31, 7, 8, 5

A partir de aquí, hay una variedad de formas conocidas de almacenar una secuencia de enteros en la memoria.

Además de almacenar su número con perfecta precisión, las fracciones continuas también tienen otros beneficios, como la mejor aproximación racional. Si decide terminar la secuencia de números en una fracción continua antes, los dígitos restantes (cuando se combinan en una fracción) le darán la mejor fracción posible. Así es como se encuentran las aproximaciones a pi:

La fracción continua de Pi:

3; 7, 15, 1, 292 ...

Terminando la secuencia en 1, esto da la fracción:

355/113

lo cual es una excelente aproximación racional.

En la ecuación

2^x = y ;  
x = log(y) / log(2)

Por lo tanto, me preguntaba si podríamos tener un sistema base logarítmico para binarios como,

 2^1, 2^0, 2^(log(1/2) / log(2)), 2^(log(1/4) / log(2)), 2^(log(1/8) / log(2)),2^(log(1/16) / log(2)) ........

Eso podría resolver el problema, así que si quisieras escribir algo como 32.41 en binario, eso sería

2^5 + 2^(log(0.4) / log(2)) + 2^(log(0.01) / log(2))

O

2^5 + 2^(log(0.41) / log(2))

El problema es que realmente no sabes si el número es exactamente 61.0. Considera esto:

float a = 60;
float b = 0.1;
float c = a + b * 10;

¿Cuál es el valor de c? No es exactamente 61, porque b no es realmente .1 porque .1 no tiene una representación binaria exacta.

Hay un umbral porque el significado del dígito ha pasado de entero a no entero. Para representar 61, tienes 6 * 10 ^ 1 + 1 * 10 ^ 0; 10 ^ 1 y 10 ^ 0 son números enteros. 6.1 es 6 * 10 ^ 0 + 1 * 10 ^ -1, pero 10 ^ -1 es 1/10, que definitivamente no es un número entero. Así es como terminas en Inexactville.

Un paralelo puede estar formado por fracciones y números enteros. Algunas fracciones, por ejemplo, 1/7 no se pueden representar en forma decimal sin montones y montones de decimales. Debido a que el punto flotante se basa en binario, los casos especiales cambian pero se presentan los mismos problemas de precisión.

Hay un número infinito de números racionales y un número finito de bits para representarlos. Ver http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems .

El número 61.0 tiene una operación exacta de coma flotante, pero eso no es cierto para todos los enteros. Si escribiera un bucle que agregara uno a un número de coma flotante de doble precisión y a un entero de 64 bits, eventualmente llegaría a un punto donde el entero de 64 bits representa perfectamente un número, pero el punto flotante no: porque no hay suficientes bits significativos.

Es mucho más fácil llegar al punto de aproximación en el lado derecho del punto decimal. Si comenzaras a escribir todos los números en coma flotante binaria, tendría más sentido.

Otra forma de pensarlo es que cuando observa que 61.0 es perfectamente representable en la base 10, y cambiar el punto decimal no cambia eso, está realizando la multiplicación por potencias de diez (10 ^ 1, 10 ^ -1 ) En coma flotante, multiplicar por potencias de dos no afecta la precisión del número. Intente tomar 61.0 y dividirlo por tres repetidamente para obtener una ilustración de cómo un número perfectamente preciso puede perder su representación precisa.

sabes números enteros ¿verdad? cada bit representa 2 ^ n

2 ^ 4 = 16
2 ^ 3 = 8
2 ^ 2 = 4
2 ^ 1 = 2
2 ^ 0 = 1

bueno, es lo mismo para coma flotante (con algunas distinciones) pero los bits representan 2 ^ -n 2 ^ -1 = 1/2 = 0.5
2 ^ -2 = 1 / (2 * 2) = 0.25
2 ^ -3 = 0.125
2 ^ -4 = 0.0625

Representación binaria en coma flotante:

signo Fracción del exponente (creo que el invisible 1 se añade a la fracción)
B11 B10 B9 B8 B7 B6 B5 B4 B3 B2 B1 B0

La respuesta de alto puntaje anterior lo clavó.

Primero estabas mezclando la base 2 y la base 10 en tu pregunta, luego, cuando pones un número en el lado derecho que no es divisible en la base, tienes problemas. Como 1/3 en decimal porque 3 no entra en una potencia de 10 o 1/5 en binario que no entra en una potencia de 2.

Otro comentario, aunque NUNCA use igual con números de punto flotante, punto. Incluso si se trata de una representación exacta, hay algunos números en algunos sistemas de coma flotante que pueden representarse con precisión de más de una manera (IEEE es malo al respecto, es una horrible especificación de coma flotante para empezar, así que espere dolores de cabeza). No es diferente aquí 1/3 no es IGUAL al número en su calculadora 0.3333333, no importa cuántos 3 haya a la derecha del punto decimal. Está o puede estar lo suficientemente cerca pero no es igual. así que esperaría que algo como 2 * 1/3 no sea igual a 2/3 dependiendo del redondeo. Nunca use igual con punto flotante.

Como hemos estado discutiendo, en aritmética de coma flotante, el decimal 0.1 no puede representarse perfectamente en binario.

Las representaciones de punto flotante y entero proporcionan cuadrículas o retículas para los números representados. A medida que se realiza la aritmética, los resultados se caen de la cuadrícula y deben volver a colocarse en la cuadrícula redondeando. El ejemplo es 1/10 en una cuadrícula binaria.

Si utilizamos una representación decimal codificada en binario como sugirió un caballero, ¿podríamos mantener los números en la cuadrícula?