Cómo analizar manualmente un número de coma flotante de una cadena

Question

Por supuesto, la mayoría de los idiomas tienen funciones de biblioteca para esto, pero supongamos que quiero hacerlo yo mismo.

Supongamos que el flotador se da como en un programa Java C o (a excepción de la 'f' o sufijo '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 se componen en un valor de tipo float o double sin perder precisión?

estoy pensando de multiplicar la parte entera con 10^n, en donde n es el número de dígitos en la parte fraccionaria, y después añadiendo la parte fraccionaria a la parte entera y restando 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?

¿Alguna idea de esto?

Answer 1

Yo ensamblaría directamente el número de punto flotante utilizando su representación binaria.

Lea el número uno después de otro y primero encuentre 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 punto 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 su 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 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.

Btw - hacer la aritmética en punto flotante en sí es una mala idea porque siempre forzarás a tu mantisa a truncarse a 23 bits significativos. No obtendrás una representación exacta de esa manera.

Answer 2

Uso de 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).

Answer 3

Para eso tienes que entender el estándar IEEE 754 para una correcta representación binaria. Después de eso, puede usar Float.intBitsToFloat o Double.longBitsToDouble.

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

Answer 4

Si desea que el resultado más preciso posible, se debe utilizar una precisión más alta de trabajo interno, y luego downconvert 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.

Answer 5

Puede ignorar el decimal al analizar (excepto su ubicación). Digamos que la entrada fue: 156.7834e10 ... Esto podría analizarse fácilmente en el entero 1567834 seguido de e10, que luego se modificará a 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 la cantidad de bits en Mantissa (o Fraction) es mayor que la cantidad de bits en su tipo 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.

De todos modos, buena suerte!

Answer 6

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 puede representarse exactamente en decimales, solo puede escribir 0.333333 ...

Si no desea usar una función de biblioteca directamente, ¿por qué no mira el código fuente para esos 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.

Answer 7

(EDIT: se ha añadido un poco en el artículo de David Goldberg)

Todas las otras respuestas han perdido la forma dura 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, What Every Computer Scientist Should Know About Floating-Point Arithmetic. 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í. Rápidamente descubrirá que le faltan cosas, pero algunas miradas a la fuente strtod y estará en el camino correcto (que es una ruta larga, larga). Finalmente, elogiará insertar diety aquí que hay bibliotecas estándar.

/* use this to start your atof implementation */ 

/* atoi - christopher.watford@gmail.com */ 
/* 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); 
} 

Answer 8

El algoritmo "estándar" para convertir un número decimal a la mejor aproximación de punto flotante es de William Clinger How to read floating point numbers accurately, descargable 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.

Algoritmos para ir por el otro lado, imprimiendo el mejor número decimal de un número flotante, se encuentran en Burger y Dybvig's Printing Floating-Point Numbers Quickly and Accurately, descargables here. Esto también requiere una aritmética de enteros de precisión múltiple

Consulte también Correctly Rounded Binary-Decimal and Decimal-Binary Conversions de David M Gay para ver los algoritmos en ambos sentidos.

Answer 9

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 punto flotante. Estoy en mi segunda implementación.

me encontré con esto hoy http://speleotrove.com/decimal/decarith.pdf

el 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 entiendo 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 anteriores a varios artículos son excelentes.

Todavía no me he registrado aquí, pero cuando lo haga, suponiendo que no se haya iniciado sesión, será broh. (broh-dot).

Clyde

Answer 10

Mi primer pensamiento es para analizar la cadena en una mantisa y un exponente int64int decimal usando solamente 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 ella de modo 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.

yo esperaría que esto sea muy preciso y muy rápido pero también se puede desear para manejar los números especiales NaN, -INFINITY, -0.0 y el infinito. No he pensado en los números desnormalizados ni en los modos de redondeo.

Answer 11

Sí, se puede descomponer la construcción en las operaciones de punto flotante , siempre que estas operaciones sonEXACTA, y puede permitirse una sola operación inexacta última.

Lamentablemente, las operaciones de punto flotante soon se vuelven inexactas, cuando se supera la precisión de mantissa, los resultados se redondean. Una vez que se introduce un "error" de redondeo, se acumulará en operaciones posteriores ...
Por lo tanto, generalmente NO, no puede usar ese ingenuo algoritmo para convertir decimales arbitrarios, esto puede conducir a un número incorrectamente redondeado , apagado por varios ulp del correcto, como otros ya te han dicho.

pero vamos a ver lo lejos que puede ir:

Si reconstruye cuidadosamente el flotador como esto:

if(biasedExponent >= 0) 
    return integerMantissa * (10^biasedExponent); 
else 
    return integerMantissa/(10^(-biasedExponent)); 

existe el riesgo de exceder la precisión tanto cuando acumulando la integerMantissa si tiene muchos dígitos, y al aumentar 10 a la potencia de BiasedExponent ...

Afortunadamente, si las dos primeras operaciones son exactas, entonces puede permitirse una operación final inexacta * o /, gracias a IEEE propert ies, el resultado se redondeará correctamente.

Vamos a aplicar esto a los flotadores de precisión simple que tienen una precisión de 24 bits.

10^8 > 2^24 > 10^7 

Observando que múltiplo de 2 sólo aumentará el exponente y dejar la mantisa sin cambios, sólo tenemos que hacer frente a las potencias de 5 para la exponenciación de 10:

5^11 > 2^24 > 5^10 

Sin embargo, puede darse el lujo 7 dígitos de precisión en el integerMantissa y una biasedExponent entre -10 y 10.

en doble precisión, 53 bits,

10^16 > 2^53 > 10^15 
5^23 > 2^53 > 5^22 

Así que puede pagar 15 dígitos decimales, y un exponente sesgado entre -22 y 22.

Todo depende de usted para ver si sus números siempre se sitúen en el rango correcto ... (Si usted es realmente complicado , puede organizar equilibrar mantisa y exponente mediante la inserción/eliminación de ceros finales).

De lo contrario, tendrá que utilizar un poco de precisión extendida.
Si su lenguaje proporciona números enteros de precisión arbitraria, entonces es un poco difícil de hacerlo bien, pero no es tan difícil, lo hice en Smalltalk y escribió en su blog acerca de ello 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 estos son implementaciones sencillas e ingenuas . Afortunadamente, libc está más optimizado.