parsing - programacion - Cómo analizar manualmente un número de punto flotante de una cadena
punto flotante informatica (11)
Por supuesto, la mayoría de los idiomas tienen funciones de biblioteca para esto, pero supongamos que quiero hacerlo yo mismo.
Supongamos que el float se da como en un programa C o Java (excepto por el sufijo ''f'' o ''d''), por ejemplo " 4.2e1 ", " .42e2 " o simplemente " 42 ". En general, tenemos la "parte entera" antes del punto decimal, la "parte fraccionaria" después del punto decimal y el "exponente". Los tres son enteros.
Es fácil encontrar y procesar los dígitos individuales, pero ¿cómo los componen en un valor de tipo float o double sin perder precisión?
Estoy pensando en multiplicar la parte entera por 10 ^ n , donde n es el número de dígitos en la parte fraccional, y luego sumar la parte fraccionaria a la parte entera y restar n del exponente. Esto efectivamente convierte 4.2e1 en 42e0 , por ejemplo. Entonces podría usar la función pow para calcular 10 ^ exponente y multiplicar el resultado con la nueva parte entera. La pregunta es, ¿este método garantiza la máxima precisión en todo?
Tiene alguna idea sobre esto?
El algoritmo "estándar" para convertir un número decimal en la mejor aproximación de coma flotante es cómo leer los números flotantes de William Clinger, descargables desde here . Tenga en cuenta que hacer esto correctamente requiere enteros de precisión múltiple, al menos un cierto porcentaje del tiempo, para manejar casos de esquina.
Los algoritmos para ir por el otro lado, imprimiendo el mejor número decimal de un número flotante, se encuentran en Burger y en Dybvig''s Printing Floating-Point Numbers de forma rápida y precisa , que se pueden descargar here . Esto también requiere una aritmética de enteros de precisión múltiple
Vea también las conversiones binarias-decimales y decimales-binarias correctas de David M Gay para algoritmos en ambos sentidos.
Estoy de acuerdo con el término. Una máquina de estado es la mejor manera de realizar esta tarea, ya que hay muchas formas estúpidas de romper un analizador. Estoy trabajando en uno ahora, creo que está completo y creo que tiene 13 estados.
El problema no es trivial.
Soy un ingeniero de hardware interesado en el diseño de hardware de coma flotante. Estoy en mi segunda implementación.
Encontré esto hoy http://speleotrove.com/decimal/decarith.pdf
que en la página 18 da algunos casos de prueba interesantes.
Sí, he leído el artículo de Clinger, pero como soy un ingeniero de hardware simple, no puedo entender el código presentado. La referencia al algoritmo de Steele como se menciona en el texto de Knuth fue útil para mí. Tanto la entrada como la salida son problemáticas.
Todas las referencias antes mencionadas a varios artículos son excelentes.
Aún no me he registrado aquí, pero cuando lo haga, suponiendo que no se haya iniciado sesión, será broh. (broh-dot).
Clyde
Mi primer pensamiento es analizar la cadena en una mantisa int64 y un exponente decimal con los primeros 18 dígitos de la mantisa. Por ejemplo, 1.2345e-5 sería analizado en 12345 y -9. Luego, seguiría multiplicando la mantisa por 10 y decrementando el exponente hasta que la mantisa tuviera 18 dígitos (> 56 bits de precisión). Luego buscaría el exponente decimal en una tabla para encontrar un factor y un exponente binario que se pueden usar para convertir el número de decimal n * 10 ^ m a binario p * 2 ^ q forma. El factor sería otro int64 así que multiplicaría la mantisa por él de tal manera que obtuve los primeros 64 bits del número resultante de 128 bits. Esta mantisa int64 se puede convertir en un flotador perdiendo solo la precisión necesaria y el exponente 2 ^ q se puede aplicar mediante la multiplicación sin pérdida de precisión.
Espero que esto sea muy preciso y muy rápido, pero es posible que también desee manejar los números especiales NaN, -infinity, -0.0 e infinito. No he pensado en los números desnormalizados ni en los modos de redondeo.
No es posible convertir cualquier cadena arbitraria que represente un número en un doble o flotante sin perder precisión. Hay muchos números fraccionarios que se pueden representar exactamente en decimales (por ejemplo, "0.1") que solo se pueden aproximar en un flotante binario o en doble. Esto es similar a cómo la fracción 1/3 no se puede representar exactamente en decimal, solo se puede escribir 0.333333 ...
Si no desea utilizar una función de biblioteca directamente, ¿por qué no mira el código fuente de esas funciones de la biblioteca? Mencionaste Java; la mayoría de los JDK se envían con el código fuente de las bibliotecas de clases para que pueda buscar cómo funciona el método java.lang.Double.parseDouble (String). Por supuesto, algo como BigDecimal es mejor para controlar los modos de precisión y redondeo, pero dijiste que debe ser flotante o doble.
Para eso, debe comprender el estándar IEEE 754 para obtener una representación binaria adecuada. Después de eso, puede usar Float.intBitsToFloat o Double.longBitsToDouble .
Puede ignorar el decimal cuando se analiza (excepto por su ubicación). Digamos que la entrada fue: 156.7834e10 ... Esto podría analizarse fácilmente en el número entero 1567834 seguido de e10, que luego modificarías en e6, ya que el decimal tenía 4 dígitos desde el final de la parte "numeral" del flotador .
La precisión es un problema. Deberá verificar las especificaciones IEEE del idioma que está utilizando. Si el número de bits en el Mantissa (o fracción) es mayor que el número de bits en su tipo de entero, entonces posiblemente perderá precisión cuando alguien escriba un número como:
5123.123123e0 - convierte a 5123123123 en nuestro método, que NO cabe en un Entero, pero los bits para 5.123123123 pueden caber en la mantisa de la especificación de flotación.
Por supuesto, puede usar un método que tome cada dígito en frente del decimal, multiplica el total actual (en un flotante) por 10, luego agrega el nuevo dígito. Para los dígitos después del decimal, multiplica el dígito por una potencia creciente de 10 antes de sumar el total actual. Sin embargo, este método parece plantear la pregunta de por qué está haciendo esto, ya que requiere el uso de la primitiva de coma flotante sin utilizar las bibliotecas de análisis disponibles.
¡En fin, buena suerte!
Si desea el resultado más preciso posible, debe usar una precisión de trabajo interna más alta y luego convertir el resultado a la precisión deseada. Si no te importan unos pocos ULP de error, entonces puedes multiplicar repetidamente por 10 según sea necesario con la precisión deseada. Evitaría la función pow (), ya que producirá resultados inexactos para grandes exponentes.
Usando una máquina de estado. Es bastante fácil de hacer, e incluso funciona si la secuencia de datos se interrumpe (solo tiene que mantener el estado y el resultado parcial). También puede usar un generador de analizadores (si está haciendo algo más complejo).
Yo ensamblaría directamente el número de coma flotante usando su representación binaria.
Lee el personaje número uno después de otro y primero encuentra todos los dígitos. Haz eso en aritmética de enteros. También haga un seguimiento del punto decimal y el exponente. Este será importante más tarde.
Ahora puede armar su número de coma flotante. Lo primero que debe hacer es escanear la representación entera de los dígitos para el primer conjunto de un bit (de mayor a menor).
Los bits que siguen inmediatamente al primer bit son tu mantisa.
Obtener el exponente tampoco es difícil. Conoces la primera posición de un bit, la posición del punto decimal y el exponente opcional de la notación científica. Combínelos y agregue el sesgo de exponente de punto flotante (creo que es 127, pero consulte alguna referencia, por favor).
Este exponente debe estar en algún lugar en el rango de 0 a 255. Si es más grande o más pequeño, tiene un número infinito positivo o negativo (caso especial).
Almacene el exponente en los bits 24 a 30 de su flotador.
El bit más significativo es simplemente el signo. Uno significa negativo, cero significa positivo.
Es más difícil de describir de lo que realmente es, intente descomponer un número de coma flotante y observe el exponente y la mantisa, y verá lo fácil que es en realidad.
Por cierto, hacer la aritmética en punto flotante en sí es una mala idea porque siempre obligarás a que tu mantisa se trunque a 23 bits significativos. No obtendrás una representación exacta de esa manera.
(EDIT: agregó un poco sobre el artículo de David Goldberg)
Todas las otras respuestas se han perdido lo difícil que es hacer esto correctamente. Puede hacer una aproximación de primer corte que sea precisa hasta cierto punto, pero hasta que tenga en cuenta los modos de redondeo IEEE (et al), nunca tendrá la respuesta correcta . He escrito implementaciones ingenuas antes con una cantidad bastante grande de error.
Si no le temen a las matemáticas, le recomiendo leer el siguiente artículo de David Goldberg, Lo que todo científico informático debería saber sobre la aritmética de coma flotante . Obtendrá una mejor comprensión de lo que está sucediendo bajo el capó, y por qué los bits se presentan como tales.
Mi mejor consejo es comenzar con una implementación de atoi que funcione, y mudarme desde allí. Descubrirás rápidamente que te faltan cosas, pero algunas miran la fuente de strtod y estarás en el camino correcto (que es un camino largo y largo). Eventualmente, elogiaremos que haya diety aquí que hay bibliotecas estándar.
/* use this to start your atof implementation */
/* atoi - [email protected] */
/* PUBLIC DOMAIN */
long atoi(const char *value) {
unsigned long ival = 0, c, n = 1, i = 0, oval;
for( ; c = value[i]; ++i) /* chomp leading spaces */
if(!isspace(c)) break;
if(c == ''-'' || c == ''+'') { /* chomp sign */
n = (c != ''-'' ? n : -1);
i++;
}
while(c = value[i++]) { /* parse number */
if(!isdigit(c)) return 0;
ival = (ival * 10) + (c - ''0''); /* mult/accum */
if((n > 0 && ival > LONG_MAX)
|| (n < 0 && ival > (LONG_MAX + 1UL))) {
/* report overflow/underflow */
errno = ERANGE;
return (n > 0 ? LONG_MAX : LONG_MIN);
}
}
return (n>0 ? (long)ival : -(long)ival);
}
Sí , puede descomponer la construcción en operaciones de coma flotante , siempre que estas operaciones sean EXACTAS , y puede permitirse una única operación final inexacta .
Desafortunadamente, las operaciones de coma flotante pronto se vuelven inexactas, cuando se supera la precisión de la mantisa, los resultados se redondean. Una vez que se introduce un "error" de redondeo, se acumulará en otras operaciones ...
Entonces, en general, NO , no puedes usar ese ingenuo algoritmo para convertir decimales arbitrarios, esto puede llevar a un número incorrectamente redondeado, apagado por varios ulp del correcto, como otros ya te han dicho.
PERO VAMOS HASTA LO QUE PODEMOS IR:
Si reconstruyes cuidadosamente el flotador así:
if(biasedExponent >= 0)
return integerMantissa * (10^biasedExponent);
else
return integerMantissa / (10^(-biasedExponent));
existe el riesgo de exceder la precisión tanto al acumular el enteroMantissa si tiene muchos dígitos, y al aumentar 10 a la potencia de BiasedExponent ...
Afortunadamente, si las dos primeras operaciones son exactas, puede permitirse una operación final inexacta * o /, gracias a las propiedades IEEE, el resultado se redondeará correctamente.
Apliquemos esto a flotadores de precisión simple que tienen una precisión de 24 bits.
10^8 > 2^24 > 10^7
Teniendo en cuenta que el múltiplo de 2 solo aumentará el exponente y dejará la mantisa sin cambios, solo tenemos que lidiar con potencias de 5 para la exponenciación de 10:
5^11 > 2^24 > 5^10
Sin embargo, puede permitirse 7 dígitos de precisión en el enteroMantissa y un BiasedExponent entre -10 y 10.
En doble precisión, 53 bits,
10^16 > 2^53 > 10^15
5^23 > 2^53 > 5^22
Entonces puede permitirse 15 dígitos decimales y un exponente sesgado entre -22 y 22.
Depende de usted ver si sus números siempre caerán en el rango correcto ... (Si es realmente complicado, podría organizar equilibrar mantisa y exponente insertando / eliminando ceros finales).
De lo contrario, tendrás que usar algo de precisión extendida.
Si su lenguaje proporciona números enteros de precisión arbitrarios, entonces es un poco complicado hacerlo bien, pero no tan difícil, lo hice en Smalltalk y escribí sobre él en http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html y http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html
Tenga en cuenta que estas son implementaciones simples e ingenuas. Afortunadamente, libc está más optimizado.