¿Qué causa los errores de redondeo de punto flotante?

Esto se debe a que algunas fracciones necesitan una cantidad muy grande (o incluso infinita) de lugares para expresarse sin redondeo. Esto es válido tanto para la notación decimal como para la binaria o cualquier otra. Si limitara la cantidad de lugares decimales para usar en sus cálculos (y evitara hacer cálculos en notación fraccionaria), tendría que redondear incluso una expresión simple como 1/3 + 1/3. En lugar de escribir 2/3 como resultado, tendría que escribir 0.33333 + 0.33333 = 0.66666 que no es idéntico a 2/3.

En el caso de una computadora, el número de dígitos está limitado por la naturaleza técnica de su memoria y registros de CPU. La notación binaria utilizada internamente agrega algunas dificultades más. Las computadoras normalmente no pueden expresar números en notación fraccionaria, aunque algunos lenguajes de programación agregan esta habilidad, lo que permite evitar esos problemas hasta cierto punto.

Lo que todo informático debe saber sobre la aritmética de coma flotante

Comentarios

• Acertar. Pero también quiero señalar que algunos números que terminar en decimal don ‘ t terminar en binario. En particular, 0.1 es un número recurrente en binario, por lo que ningún número binario de coma flotante puede representar exactamente 0.1.
• Flotante los puntos no son ‘ t solo útiles para muchos lugares decimales. Los enteros de 32 bits solo pueden contar hasta aproximadamente 4 mil millones, pero un flotante de 32 bits puede ser casi infinitamente grande.
• En particular, las fracciones que podemos expresar como decimales finitos son aquellas cuyos denominadores ‘ la factorización prima contiene solo 2 y 5 (por ejemplo, podemos expresar 3/10 y 7/25 , pero no 18/11). Cuando pasamos a binario, perdemos el factor de 5, por lo que solo los racionales diádicos (por ejemplo, 1/4, 3/128) se pueden expresar exactamente.

Principalmente, los errores de redondeo provienen del hecho de que el infinito de todos los números reales no puede ser representado por la memoria finita de una computadora , y mucho menos por una pequeña porción de memoria como una sola variable de punto flotante , así que muchos números almacenados son solo aproximaciones del número que deben representar.

Dado que solo hay un número limitado de valores que son no una aproximación, y cualquier operación entre una aproximación y otro número da como resultado una aproximación, los errores de redondeo son casi inevitables .

Lo importante Lo importante es darse cuenta de cuándo es probable que causen un problema y tomar medidas para mitigar los riesgos .

Además de David Goldberg «s essential Lo que todos los científicos informáticos t debe saber acerca de la aritmética de coma flotante (reeditado por Sun / Oracle como un apéndice de su numérico Computation Guide ), que fue mencionado por thorsten , el ACCU diario Sobrecarga publicó una excelente serie de artículos de Richard Harris sobre Floating Point Blues .

La serie comenzó con

• ¡Vas a tener que pensar! en Sobrecarga n. ° 99 ( pdf , p5-10):

Co numérico mputing tiene muchas trampas. Richard Harris comienza a buscar una bala de plata.

El dragón del error numérico no suele despertar de su letargo, pero si se le acerca de manera imprudente, ocasionalmente infligirá un daño catastrófico a los cálculos del programador desprevenido.

Tanto es así que algunos programadores, habiéndolo encontrado por casualidad en los bosques de la aritmética de punto flotante IEEE 754, aconsejan a sus compañeros que no viajen por esa tierra justa.

En esta serie de artículos exploraremos el mundo de la computación numérica, contrastando la aritmética de coma flotante con algunas de las técnicas que se han propuesto como reemplazos más seguros para ella. Aprenderemos que el territorio del dragón es de hecho muy amplio y que en general debemos andar con cuidado si tememos a su atención devastadora.

Richard comienza explicando la taxonomía de los números reales, racionales, irracionales, algebraicos y trascendentales. Luego continúa explicando la representación IEEE754, antes de continuar con el error de cancelación y los problemas de orden de ejecución.

Si no lee más que esto, tendrá una excelente base en los problemas asociados con los números de punto flotante. .

Sin embargo, si desea saber más, continúa con

• ¿Por qué el punto fijo no» curará la tristeza del punto flotante? en Sobrecarga # 100 ( pdf , p15-22)
• Por qué los racionales no Cura la tristeza del punto flotante en sobrecarga # 101 ( pdf , pág. 9-13)
• ¿Por qué el álgebra informática no curará su tristeza del punto flotante? en Sobrecarga # 102 ( pdf , p9- 14).
• Por qué la aritmética de intervalos no curará su blues de coma flotante en Sobrecarga 103 ( pdf , p19-24)

Luego pasa a tratar de ayudarlo a curar su Calculus Blues

• Por qué [Insertar algoritmo aquí] no curará la tristeza del cálculo en Sobrecarga 104 ( pdf , p22-24).
• Por qué las diferencias finitas no curarán la tristeza del cálculo en Sobrecarga 105 ( pdf , p5-12).
• Por qué la aproximación polinomial no «curará la tristeza del cálculo en Sobrecarga 106 ( pdf , p16-25).
• Por qué el álgebra informática no curará su tristeza por el cálculo in Sobrecarga 107 ( pdf , p15-20).

y por último, pero no menos importante,

• Por qué la diferenciación automática no curará la tristeza del cálculo en Sobrecarga 108 ( pdf , p4-11).

Toda la serie de artículos está vale la pena examinarlas, y con 66 páginas en total, siguen siendo más pequeñas que las 77 páginas del artículo de Goldberg .

Si bien este La serie cubre gran parte del mismo terreno, lo encontré bastante más accesible que el artículo de Goldberg. También encontré más fácil entender las partes más complejas del artículo después de leer el artículo anterior de Richards y después de esos primeros artículos, Richard se ramifica en muchas áreas interesantes que el artículo de Goldberg no aborda.

Como así hablo ak mencionado en los comentarios:

Como autor de esos artículos Me gustaría mencionar que he creado versiones interactivas de ellos en mi blog www.thusspakeak.com comenzando con thusspakeak.com/ak/2013/06 .

Comentarios

• Como autor de esos artículos, ‘ me gustaría mencionar que he creado versiones interactivas de ellos en mi blog www.thusspakeak.com comenzando con thusspakeak.com/ak/2013/06 .
• Gracias @ thusspakea.k. ‘ he añadido una nota a mi respuesta, y aunque Estos elementos interactivos funcionan muy bien.

Bueno, thorsten tiene el enlace definitivo. Yo agregaría:

Cualquier forma de representación tendrá algún error de redondeo para algún número. Intente expresar 1/3 en coma flotante IEEE o en decimal. Ninguno de los dos puede hacerlo con precisión. Esto va más allá de responder a su pregunta, pero he usado esta regla empírica con éxito:

• Almacene los valores ingresados por el usuario en decimal (porque es casi seguro que lo ingresaron en una representación decimal – muy pocos usuarios usará binario o hexadecimal). De esa manera, siempre tendrá la representación exacta ingresada por el usuario.
• Si tiene que almacenar fracciones ingresadas por el usuario, almacene el numerador y el denominador (también en decimal)
• Si tiene un sistema con varias unidades de medida para la misma cantidad (como Celsius / Fahrenheit), y el usuario puede ingresar ambos, almacenar el valor que ingresaron y las unidades en las que los ingresaron. No intente convertir y guardar como una sola representación, a menos que pueda hacerlo sin pérdida de precisión o exactitud. Utilice el valor almacenado y unidades en todos los cálculos.
• Almacene los valores generados por la máquina en punto flotante IEEE (pueden ser números generados por un dispositivo de medición electrónico, como un sensor analógico con un convertidor A / D, o el resultado no redondeado de un cálculo). Tenga en cuenta que esto no se aplica si está leyendo un sensor a través de una conexión en serie y ya está dando usted el valor en formato decimal (p. ej., 18,2 C).
• Almacene los totales visibles para el usuario, etc., en formato decimal (como una cuenta bancaria equilibrio). Redondea apropiadamente, pero usa ese valor como el valor definitivo para todos los cálculos futuros.

Comentarios

• Yo agregaría: Considera usar un paquete matemático de precisión arbitraria como ARPREC o decNumber.
• No ‘ t decimal (a diferencia de binario) tiene mucho beneficio para valores enteros, como el numerador y denominador de una fracción. Cualquiera puede almacenar valores enteros exactos y el binario es más eficiente. Hay ‘ cierto costo en la conversión de ida y vuelta para entrada y salida, pero es probable que ‘ se vea abrumado por el costo de realizar la E / S.

Lo que parece no haber sido mencionado hasta ahora son los conceptos de un algoritmo inestable y un problema mal condicionado . Primero abordaré el primero, ya que parece ser un error más frecuente para los numericistas novatos.

Considere el cálculo de las potencias de la proporción áurea (recíproca) φ=0.61803…; una forma posible de hacerlo es usar la fórmula de recursividad φ^n=φ^(n-2)-φ^(n-1), comenzando con φ^0=1 y φ^1=φ. Si ejecuta esta recursividad en su entorno informático favorito y compara los resultados con potencias evaluadas con precisión, encontrará una erosión lenta de cifras significativas. Esto es lo que sucede, por ejemplo, en Mathematica :

ph = N[1/GoldenRatio]; Nest[Append[#1, #1[[-2]] - #1[[-1]]] & , {1, ph}, 50] - ph^Range[0, 51] {0., 0., 1.1102230246251565*^-16, -5.551115123125783*^-17, 2.220446049250313*^-16, -2.3592239273284576*^-16, 4.85722573273506*^-16, -7.147060721024445*^-16, 1.2073675392798577*^-15, -1.916869440954372*^-15, 3.1259717037102064*^-15, -5.0411064211886014*^-15, 8.16837916750579*^-15, -1.3209051907825398*^-14, 2.1377864756200182*^-14, -3.458669982359108*^-14, 5.596472721011714*^-14, -9.055131861349097*^-14, 1.465160458236081*^-13, -2.370673237795176*^-13, 3.835834102607072*^-13, -6.206507137114341*^-13, 1.004234127360273*^-12, -1.6248848342954435*^-12, 2.6291189633497825*^-12, -4.254003796798193*^-12, 6.883122762265558*^-12, -1.1137126558640235*^-11, 1.8020249321541067*^-11, -2.9157375879969544*^-11, 4.717762520172237*^-11, -7.633500108148015*^-11, 1.23512626283229*^-10, -1.9984762736468268*^-10, 3.233602536479646*^-10, -5.232078810126407*^-10, 8.465681346606119*^-10, -1.3697760156732426*^-9, 2.216344150333856*^-9, -3.5861201660070964*^-9, 5.802464316340953*^-9, -9.388584482348049*^-9, 1.5191048798689004*^-8, -2.457963328103705*^-8, 3.9770682079726053*^-8, -6.43503153607631*^-8, 1.0412099744048916*^-7, -1.6847131280125227*^-7, 2.725923102417414*^-7, -4.4106362304299367*^-7, 7.136559332847351*^-7, -1.1547195563277288*^-6} 

El supuesto resultado para φ^41 tiene el signo incorrecto, e incluso antes, los valores calculados y reales para φ^39 no comparten dígitos en común (3.484899258054952 * ^ – 9 for the computed version against the true value 7.071019424062048 *^-9). Por lo tanto, el algoritmo es inestable y no se debe utilizar esta fórmula de recursión en aritmética inexacta. Esto se debe la naturaleza inherente de la fórmula de recursividad: hay una solución «decadente» y «creciente» para esta recursividad, y tratar de calcular la solución «decadente» por solución directa cuando hay una solución alternativa «creciente» es suplicar un dolor numérico. Por lo tanto, uno debe asegurarse de que sus algoritmos numéricos sean estables.

Ahora, pasemos al concepto de un problema mal condicionado : aunque puede haber una forma estable de hacerlo algo numéricamente, es muy posible que el problema que tiene simplemente no puede ser resuelto por su algoritmo. Esto es culpa del problema en sí, y no del método de solución. El ejemplo canónico en numérica es la solución de ecuaciones lineales que involucran la llamada «matriz de Hilbert»:

La matrix es el ejemplo canónico de una matriz mal acondicionada : tratar de resolver un sistema con una matriz de Hilbert grande podría devolver una solución inexacta.

Aquí «sa Mathematica demostración: compare los resultados de la aritmética exacta

Table[LinearSolve[HilbertMatrix[n], HilbertMatrix[n].ConstantArray[1, n]], {n, 2, 12}] {{1, 1}, {1, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}} 

y la aritmética inexacta

Table[LinearSolve[N[HilbertMatrix[n]], N[HilbertMatrix[n].ConstantArray[1, n]]], {n, 2, 12}] {{1., 1.}, {1., 1., 1.}, {1., 1., 1., 1.}, {1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 1., 1., 1., 1., 1., 1.}, {1., 1., 1., 0.99997, 1.00014, 0.999618, 1.00062, 0.9994, 1.00031, 0.999931}, {1., 1., 0.999995, 1.00006, 0.999658, 1.00122, 0.997327, 1.00367, 0.996932, 1.00143, 0.999717}, {1., 1., 0.999986, 1.00022, 0.998241, 1.00831, 0.975462, 1.0466, 0.94311, 1.04312, 0.981529, 1.00342}} 

(Si lo probó en Mathematica , notará algunos mensajes de error advirtiendo sobre la aparición del mal condicionamiento).

En ambos casos, simplemente aumentando el la precisión no cura; solo retrasará la inevitable erosión de las cifras.

Esto es a lo que podría enfrentarse. Las soluciones pueden ser difíciles: para el primero, o vuelves a la mesa de dibujo o revisas revistas / libros / lo que sea para encontrar si alguien más ha encontrado una solución mejor que tú; para el segundo, o te rindes o reformulas tu problema a algo más manejable.

Te dejo con una cita de Dianne O «Leary:

La vida puede arrojarnos algunos problemas mal condicionados, pero no hay una buena razón para conformarse con un algoritmo inestable.

porque los números decimales de base 10 no se pueden expresar en base 2

o, en otras palabras, 1/10 no se puede transformado en una fracción con una potencia de 2 en el denominador (que es lo que son esencialmente los números de coma flotante)

Comentarios

• No es exactamente cierto: 0.5 y 0.25 se puede expresar en base 2. Creo que te refieres a » no todos los números decimales de base 10 «.
• Más exactamente. No todos los números fraccionarios se pueden representar exactamente usando una notación de punto flotante (es decir, con. Tanto la base 2 como la base 10 tienen este problema exacto). Intente hacer 9*3.3333333 en decimal y compárelo con 9*3 1/3
• Esta es la fuente más común de coma flotante Confusión. .1 + .1 != .2 porque se usa codificación binaria de punto flotante, no decimal.
• @SeanMcMillan: Y 1.0/3.0*3.0 != 1.0, porque flota -se usa codificación binaria de puntos, no trinaria.

En matemáticas, hay infinitos números racionales . Una variable de 32 bits solo puede tener 2 ³² valores diferentes y una variable de 64 bits solo 2 valores ⁶⁴ . Por lo tanto, hay infinitos números racionales que no tienen una representación precisa.

Podríamos idear esquemas que nos permitieran representar 1/3 perfectamente, o 1/100. Resulta que para muchos propósitos prácticos esto no es muy útil. Existe una gran excepción: en las finanzas, las fracciones decimales suelen aparecer. Eso se debe principalmente a que las finanzas son esencialmente una actividad humana, no física.

Por lo tanto, generalmente elegimos usar un punto flotante binario y redondear cualquier valor que no se pueda representar en binario. Pero en finanzas, a veces elegimos el punto flotante decimal y redondear los valores al valor decimal más cercano .

Comentarios

• Peor aún, mientras que una cantidad infinita (numerablemente infinita) de memoria le permitiría a uno representar todos los racionales, no es suficiente para representar los reales. Peor aún, casi todos los números reales no son números computables. Lo mejor que podemos hacer con una cantidad finita de memoria es aproximar un subconjunto de rango finito de los reales.
• @Kevin: Estás ‘ hablando de los números computables, que es un pequeño subconjunto (un subconjunto con medida cero) de los reales.
• +1 para el explicación más básica: ‘ estás tratando de representar una cantidad infinita de números con un número finito de bits.
• @DavidHammen: Los números computables son un subconjunto diminuto ( de medida cero) de los reales, pero cada número con el que ‘ trabajará en un programa es, por definición, computable.
• @Giorgio: Si elige la representación correcta, la raíz cuadrada de 2 es representable, por ejemplo, como la cadena "√2". (Mi vieja calculadora HP-48 podía hacer exactamente eso, y cuadrar ese valor resultó en exactamente 2.0.) Solo hay una infinidad contable de números reales representables para cualquier representación finita, pero ningún cálculo puede producir un número que, en principio, no es representable. En la práctica, el punto flotante binario limita drásticamente el conjunto de números representables, con el beneficio de una velocidad increíble y un almacenamiento pequeño en relación con las representaciones simbólicas.

el único «problema de redondeo» realmente obvio con los números de punto flotante en el que pienso es con los filtros de promedio móvil:

$$ \ begin {align} y [n] & = \ frac {1} {N} \ sum \ limits_ {i = 0} ^ {N-1} x [ni] \ & = y [n-1] + \ frac {1} {N} (x [n] – x [nN]) \ \ end {align} $$

para que esto funcione sin la acumulación de ruido, desea asegurarse de que el $ x [n] $ que agrega en las muestras actuales sea exactamente el mismo que el $ x [nN] $ que restará $ N $ muestras en el futuro. si no es así, entonces lo que es diferente es un poco de mierda que se atasca en su línea de retardo y nunca saldrá. esto se debe a que este filtro de promedio móvil está construido con un IIR que tiene un polo marginalmente estable en $ z = 1 $ y un cero que lo cancela por dentro. pero, es un integrador y cualquier basura que se integre y no se elimine por completo existirá en la suma del integrador para siempre. Aquí es donde el punto fijo no tiene el mismo problema que los números de punto flotante.

Comentarios

• hey, ¿no ‘ t el marcado matemático de $ LaTeX $ funciona en el foro prog.SE ??? div id = «0934d2d03f»>