¿Cómo convertir cuerdas a flotadores con una precisión perfecta?

Estoy tratando de escribir una función en el lenguaje de programación D para reemplazar las llamadas al strtold de C. (Justificación: Para usar strtold desde D, debe convertir cadenas D en cadenas C, lo cual es ineficiente. Además, strtold no se puede ejecutar en tiempo de compilación). He encontrado una implementación que funciona principalmente, pero parece perder cierta precisión en los bits menos significativos.¿Cómo convertir cuerdas a flotadores con una precisión perfecta?

El código de la parte interesante del algoritmo está debajo y puedo ver de dónde proviene la pérdida de precisión, pero no sé cómo deshacerme de ella. (He omitido muchas partes del código que no eran relevantes para el algoritmo central para salvar a las personas que leen). ¿Qué algoritmo de cadena a flotación garantizará que el resultado sea lo más parecido posible al número IEEE? línea al valor representado por la cadena.

real currentPlace = 10.0L ^^ (pointPos - ePos + 1 + expon); 

real ans = 0; 
for(int index = ePos - 1; index > -1; index--) { 
    if(str[index] == '.') { 
     continue; 
    } 

    if(str[index] < '0' || str[index] > '9') { 
     err(); 
    } 

    auto digit = cast(int) str[index] - cast(int) '0'; 
    ans += digit * currentPlace; 
    currentPlace *= 10; 
} 

return ans * sign;

Además, estoy usando las pruebas de unidad para la versión antigua, que hizo cosas como:

assert(to!(real)("0.456") == 0.456L);

¿Es posible que las respuestas que se producen por mis funciones son en realidad más precisa que la representación que produce el compilador al analizar un literal en coma flotante, pero el compilador (que está escrito en C++) siempre concuerda exactamente con strtold porque usa strtold internamente para analizar literales en coma flotante.

Fuente

2010-02-01 dsimcha

indique de dónde proviene la pérdida de precisión. –

@John: la pérdida de precisión proviene de dos lugares: 1. Rondamos cada vez que ejecutamos la línea 'ans + = digit * currentPlace', y 10^i no se puede representar exactamente en IEEE 754 para la mayoría de los enteros i. – dsimcha

Como referencia, revise las implementaciones de strtod: http://www.google.com/codesearch?hl=es&lr=&q=double+strtod+const+char+str%2C+char+endptr&sbtn=Search – outis

No puede almacenar más flotadores con perfecta precisión en una computadora digital

Fuente

2010-02-01 00:54:47

Derecha. Esta es la razón por la que defino precisión "perfecta" como el número de coma flotante más cercano (32/64/80) al número representado por la cadena de entrada. – dsimcha

Clinger y Steele & White desarrollado algoritmos finas para leer y escribir en coma flotante.

Hay una retrospectiva here junto con algunas referencias a las implementaciones.

David Gay's paper mejorando el trabajo de Clinger, y implementation in C de Gay son geniales. Los he usado en sistemas embebidos, y creo que Gay's dtoa hizo su camino en muchos libc.

Fuente

2010-02-01 00:57:43

El código fuente de Gay contiene su propia implementación de BigInt que usa en algunos de sus cálculos temporales, es bastante código. Creo que el documento es mucho más fácil de leer. –

La dtoa de Gay se usa en todas partes: Firefox, Opera, Safari, Thunderbird, KDE, Chrome, Python, MySQL, Mac OS X, J y D, por ejemplo. –

¡Desde que escribió esta respuesta, se ha descubierto que un algoritmo mucho más eficiente que el de Gay's imprime valores canónicos más cortos para números flotantes! Tal vez actualice su respuesta para reflejar esto? Consulte "Imprimir números de punto flotante de forma rápida y precisa con enteros " aquí: http://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf –

Comience acumulando los dígitos como un valor entero, ignorando el punto decimal y el exponente. Todavía utilizaría un acumulador de punto flotante, pero no tendría una parte fraccionaria, esto evita la pérdida de precisión debido a la incapacidad de expresar exactamente los números de coma flotante. (También podría ignorar los dígitos fraccionarios que están más allá de la precisión de los flotadores para representar: 8 dígitos para los flotadores IEEE de 32 bits).

Puede usar un número entero de 64 bits para acumular dígitos si lo prefiere, pero debe tener cuidado de ignorar dígitos extra que podrían causar desbordamiento si lo hace. (aún debe tener estos dígitos en cuenta al determinar el exponente)

Luego escale este valor por el exponente, teniendo en cuenta la ubicación del punto decimal que ignoró al acumular dígitos.

Fuente

2010-02-01 01:05:15

Crea un número de coma flotante para cada dígito y luego suma estos números. Dado que los números de punto flotante no son exactos, sino que se redondean a un cierto número de dígitos binarios, esto implica pequeñas imprecisiones al almacenar los números individuales y sumarlos. Por lo tanto, agregar los números de punto flotante para los dígitos individuales juntos podría dar un resultado con un pequeño error de redondeo.

Un ejemplo sería 0.1 + 0.02, que es no igual a 0.12 si representado como un número de coma flotante.(Para verificar esto simplemente intente compararlos en su lenguaje de programación favorito)

Fuente

2010-02-01 01:05:56 sth

Honestamente, esta es una de esas cosas que realmente no debería estar haciendo si aún no sabe cómo hacerlo. Está lleno de trampas, e incluso si logras hacerlo bien, es probable que sea tremendamente lento si no tienes experiencia en el análisis del rendimiento numérico de bajo nivel.

Dicho esto, si está realmente decidido a escribir su propia implementación, la mejor referencia para la corrección es "Conversiones binarias-decimales y binarias-decimal correctamente redondeadas" de David Gay (postscript version). También debe estudiar sus implementaciones de referencia (en C), que están disponibles en Netlib.

Fuente

2010-02-01 01:21:57

¿Cómo convertir cuerdas a flotadores con una precisión perfecta?

Respuesta

Cuestiones relacionadas