math - should - floating point representation

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

Question

Se han publicado varias preguntas al SO sobre la representación en 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 punto 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, pasé 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 yendo 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?

Edición: para aclarar, quiero mantenerme alejado de las discusiones sobre representaciones estándares de la industria, como IEEE, y seguir con lo que creo que es matemáticamente "puro". 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 hay límites arbitrarios en estos números. Las posiciones aumentan indefinidamente hacia la izquierda y hacia la derecha.

Answer 1

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, pasé 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 la base b , ¿qué números tienen representaciones de terminación y qué números no? Un pensamiento momentáneo nos dice que un número x tiene una representación b final si y solo si existe un entero n tal que xb^n sea ​​un entero.

Entonces, por ejemplo, x = 11/500 tiene una representación de terminación de 10, porque podemos seleccionar n = 3 y luego xb^n = 22 , un entero. Sin embargo, x = 1/3 no, porque lo que sea que escojamos no podremos deshacernos del 3.

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

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

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

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

q tiene solo 2 s en su factorizacion principal

obviamente también es verdad que

q tiene solo 2 sy 5 s en su factorización prima

o, dicho de otra manera, cada vez que p/q tiene una representación de terminación 2, p/q tiene una representación de terminación 10 . Sin embargo, lo contrario no se cumple : siempre que q tenga un 5 en su factorización prima, tendrá una representación de terminación 10, pero no una representación de terminación 2. Este es el ejemplo 0.1 mencionado por otras respuestas.

Entonces, aquí 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 de 2 terminaciones son números de 10 terminaciones, pero no al revés. No se trata de 61 contra 6.1, se trata de 10 contra 2.

Como nota final, si por alguna razón la gente usara (digamos) la base 17 pero nuestras computadoras usaran la base 5, su intuición nunca se habría desviado por esto: no habría ningún número (que no sea cero ni entero) que terminara ¡en ambos casos!

Answer 2

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

Una forma de pensar 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 punto flotante se almacenan internamente con un formato similar: mantisa y exponente, pero con 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 en la mantisa y exponentes en binario:

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

Note 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 al golpear 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, considera cómo dividiríamos 61 por 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 muchos bits para mantener esa mantisa y por lo tanto redondearán la fracción y asume ceros más allá de cierto punto. El error que ves cuando divides 61 por 10 es la diferencia entre:

1.100001100110011001100110011001100110011 ... b * 2 ^ 10b
y decir:
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 punto flotante. Incluso cuando la mantisa se puede expresar exactamente (por ejemplo, cuando solo se suman 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.

En realidad, hacemos este tipo de cosas todo el tiempo cuando redondeamos los números decimales a un tamaño manejable y solo damos los primeros dígitos. Porque 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 punto flotante.

Answer 3

BCD - Decimal codificado en binario - las representaciones son exactas. No son muy eficientes en el espacio, pero en este caso es un compromiso que hay que hacer para lograr la precisión.

Answer 4

Como hemos estado discutiendo, en aritmética de punto flotante, el decimal 0.1 no se puede representar perfectamente en binario.

Las representaciones de coma flotante y enteros proporcionan cuadrículas o celosías para los números representados. A medida que se realiza la aritmética, los resultados caen fuera 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 la representación decimal codificada en binario como sugirió un caballero, ¿podríamos mantener los números en la cuadrícula?

Answer 5

El número 61.0 de hecho tiene una operación de punto flotante exacta, pero eso no es cierto para todos los enteros. Si escribiera un bucle que lo agregara tanto a un número de punto flotante de doble precisión como a un entero de 64 bits, finalmente alcanzarí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 alcanzar el punto de aproximación en el lado derecho del punto decimal. Si comenzaste a escribir todos los números en un punto flotante binario, tendría más sentido.

Otra forma de pensar sobre esto es que cuando observas que 61.0 es perfectamente representable en la base 10, y cambiar el punto decimal no cambia eso, estás realizando una 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 ilustrar cómo un número perfectamente preciso puede perder su representación precisa.

Answer 6

El problema es que realmente no sabes si el número en realidad 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.

Answer 7

En la ecuacion

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 ser capaz de 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))

Answer 8

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.

Answer 9

Esta es una buena pregunta.

Todas sus preguntas se basan en "¿cómo representamos un número?"

TODOS los números se pueden representar con una representación decimal o con una 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 la 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 se pueden representar 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 se puede representar 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 base 2 o base 10 para la representación de valores de punto flotante)

Answer 10

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

Answer 11

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 ambos 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.

Answer 12

La razón de la imprecisión es la naturaleza de las bases numéricas. En la base 10, no puedes representar exactamente 1/3. Se convierte en 0.333 ... Sin embargo, en la base 3, 1/3 está representado exactamente por 0.1 y 1/2 es un decimal que se repite infinitamente (¿tresimal?). Los valores que se pueden representar de manera finita dependen del número de factores primos únicos de la base, por lo que la base 30 [2 * 3 * 5] puede representar más fracciones que la base 2 o la base 10. Aún más para la base 210 [2 * 3 * 5 * 7].

Este es un problema separado del "error de punto flotante". La inexactitud se debe a que unos pocos miles de millones de valores se distribuyen en un rango mucho mayor. Entonces, si tiene 23 bits para el significado, solo puede representar unos 8,3 millones de valores distintos. Luego, un exponente de 8 bits proporciona 256 opciones para distribuir esos valores. Este esquema permite que los decimales más precisos ocurran cerca de 0, por lo que casi puede representar 0.1.

Answer 13

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

Lo que significa que, aunque hay una cantidad infinita de ellos, podríamos "contar" todos los elementos en la secuencia, sin omitir ninguno. Eso significa que si queremos obtener el artículo en la posición 610000000000000 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 obtén una respuesta. La razón es porque, incluso entre 0 y 1 , hay un número infinito de valores, cuando se consideran valores de punto flotante. Lo mismo se aplica a cualquiera de los dos números de punto 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 acerca de 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.

Answer 14

La respuesta de alta puntuación anterior lo clavó.

Primero mezcló la base 2 y la base 10 en su pregunta, luego, cuando coloca un número en el lado derecho que no es divisible en la base, tiene 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 punto flotante que se pueden representar con precisión de más de una manera (IEEE es malo en esto, es una horrible especificación de punto flotante para comenzar, así que espere un dolor de cabeza). No es diferente aquí 1/3 no es IGUAL al número en su calculadora 0.3333333, no importa cuántos 3 hay a la derecha del punto decimal. Es o puede estar lo suficientemente cerca pero no es igual. por lo que es de esperar que algo como 2 * 1/3 no sea igual a 2/3 dependiendo del redondeo. Nunca use igual con punto flotante.

Answer 15

Los números decimales se pueden representar exactamente, si tiene suficiente espacio, pero no con números de puntos binarios flotantes. Si utiliza un tipo de punto decimal flotante (por ejemplo, System.Decimal en .NET), se pueden representar exactamente muchos valores que no pueden representarse exactamente en punto flotante binario.

Mirémoslo de otra manera: en la base 10 con la que es probable que se sienta cómodo, no puede expresar exactamente 1/3. Es 0.3333333 ... (recurrente). La razón por la que no puede representar 0.1 como un número binario de punto flotante es exactamente por la misma razón. Puede representar 3, y 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 se quiere multiplicar un número por 3: siempre se puede multiplicar por un número entero sin tener problemas. Pero cuando divides por un número que es primo y no es un factor de tu base, puedes tener problemas (y lo harás si intentas dividir 1 por ese número).

Aunque 0.1 se usa generalmente como el ejemplo más simple de un número decimal exacto que no se puede representar exactamente en punto flotante binario, podría decirse que 0.2 es un ejemplo más simple, ya que es 1/5 - y 5 es el principal que causa problemas entre decimal y binario .

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

Algunos tipos de punto decimal flotante tienen un tamaño fijo como System.Decimal otros como java.math.BigDecimal son "arbitrariamente grandes", pero alcanzarán un límite en algún punto, 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 tuvieras una gran cantidad de bits genuinamente arbitrarios para jugar, aún no podrías representar el decimal 0.1 exactamente en una representación de punto binario flotante. Compare esto con el otro modo: dado un número arbitrario de dígitos decimales, puede representar exactamente cualquier número que sea exactamente representable como un punto binario flotante.

Answer 16

Me sorprende que nadie haya declarado 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

Desde aquí, hay una variedad de formas conocidas para 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 algunos otros beneficios, como la mejor aproximación racional. Si decides terminar la secuencia de números en una fracción continua temprano, los dígitos restantes (cuando se combinan en una fracción) te darán la mejor fracción posible. Así es como se encuentran las aproximaciones a pi:

Fracción continua de pi:

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

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

355/113

Que es una excelente aproximación racional.

Answer 17

Para repetir lo que dije en mi comentario al Sr. Skeet: podemos representar 1/3, 1/9, 1/27, o cualquier racional en notación decimal. Lo hacemos añadiendo un símbolo extra. 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 es 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 cita de Hehner es una forma de hacer esto. Usa un símbolo de cita para representar la parte repetitiva 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 los racionales decimales usando la notación de comillas binarias exactamente, y viceversa.

Answer 18

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

Answer 19

Si haces un número suficientemente grande con un punto flotante (ya que puede hacer exponentes), también terminarás con inexactitud frente al punto decimal, también. Entonces, no creo que tu pregunta sea completamente válida porque la premisa es incorrecta; no es el caso que el cambio de 10 siempre creará más precisión, porque en algún punto el número de punto flotante tendrá que usar exponentes para representar la amplitud del número y también perderá cierta precisión de esa manera.

Answer 20

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 el punto 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 de punto flotante:

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