Cómo analizar manualmente un número de punto 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 valor flotante se proporciona como en un programa C o Java (excepto 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 números 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 en multiplicar la parte entera por 10^norte, dónde norte es el número de dígitos en la parte fraccionaria, y luego suma la parte fraccionaria a la parte entera y resta norte del exponente.Esto efectivamente convierte 4.2e1 en 42e0, Por ejemplo.Entonces podría usar el pow función para calcular 10^exponente y multiplica el resultado por la nueva parte entera.La pregunta es: ¿este método garantiza la máxima precisión en todo momento?

Tiene alguna idea sobre esto?

Answer 1

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

Lea el número un carácter tras otro y primero encuentre todos los dígitos.Haz eso en aritmética de números enteros.También lleve la cuenta del punto decimal y del exponente.Éste será importante más adelante.

Ahora puedes armar tu número de punto flotante.Lo primero que debe hacer es escanear la representación entera de los dígitos para buscar el primer bit establecido (de mayor a menor).

Los bits que siguen inmediatamente al primer bit son su mantisa.

Obtener el exponente tampoco es difícil.Conoces la posición del primer bit, la posición del punto decimal y el exponente opcional de la notación científica.Combínelos y agregue el sesgo del exponente de coma flotante (creo que es 127, pero consulte alguna referencia, por favor).

Este exponente debería estar en algún lugar en el rango de 0 a 255.Si es mayor o menor tienes un número infinito positivo o negativo (caso especial).

Guarde el exponente tal como está en los bits 24 a 30 de su flotante.

Lo 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, intenta descomponer un número de coma flotante y observa el exponente y la mantisa y verás lo fácil que es en realidad.

Por cierto, hacer la aritmética en punto flotante es una mala idea porque siempre forzarás que tu mantisa se trunque a 23 bits significativos.De esa manera no obtendrás una representación exacta.

Answer 2

Todas las otras respuestas han pasado por alto cómo duro es hacer esto correctamente.Puede hacer un primer enfoque en esto que es preciso hasta cierto punto, pero hasta que tenga en cuenta los modos de redondeo IEEE (et al), nunca tendrá la bien respuesta.He escrito implementaciones ingenuas antes con una cantidad bastante grande de errores.

Si no te asustan las matemáticas, te recomiendo leer el siguiente artículo de David Goldberg, Lo que todo informático debería saber sobre la aritmética de punto flotante.Obtendrá una mejor comprensión de lo que sucede bajo el capó y por qué las partes están dispuestas así.

Mi mejor consejo es comenzar con una implementación funcional de atoi y continuar desde allí.Rápidamente descubrirás que te estás perdiendo cosas, pero con unas cuantas miradas strtodla fuente y estarás en el camino correcto (que es un camino muy, muy largo).Eventualmente alabarás inserte diety aquí que existen 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 3

El algoritmo "estándar" para convertir un número decimal a la mejor aproximación de punto flotante es el de William Clinger. Cómo leer números de coma flotante con precisión, descargable desde aquí.Tenga en cuenta que hacer esto correctamente requiere números enteros de precisión múltiple, al menos un cierto porcentaje del tiempo, para poder manejar los casos extremos.

Los algoritmos para ir en sentido contrario, imprimiendo el mejor número decimal a partir de un número flotante, se encuentran en Burger y Dybvig. Impresión de números de coma flotante de forma rápida y precisa, descargable aquí.Esto también requiere aritmética de enteros de precisión múltiple.

Véase también David M Gay Conversiones binario-decimal y decimal-binario correctamente redondeadas para algoritmos que van en ambos sentidos.

Answer 4

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 número entero 1567834 seguido de e10, que luego modificaría a e6, ya que el decimal estaba a 4 dígitos del final de la parte "numeral" del flotante.

La precisión es un problema.Deberá verificar la especificación IEEE del idioma que está utilizando.Si la cantidad de bits en la Mantisa (o Fracción) 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: se convierte a 5123123123 en nuestro método, que NO cabe en un número entero, pero los bits para 5.123123123 pueden caber en la mantisa de la especificación flotante.

Por supuesto, podrías usar un método que tome cada dígito delante del decimal, multiplique el total actual (en un flotante) por 10 y luego agregue el nuevo dígito.Para los dígitos después del decimal, multiplique el dígito por una potencia creciente de 10 antes de sumarlo al 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 punto flotante sin usar las bibliotecas de análisis disponibles.

¡De todos modos, buena suerte!

Answer 5

Sí, puedes descomponer la construcción en operaciones de punto flotante mientras estas operaciones son EXACTO, y puedes permitirte un único final inexacto operación.

Desafortunadamente, las operaciones de punto flotante pronto se vuelven inexactos, cuando se excede la precisión de la mantisa, los resultados se redondean.Una vez introducido un "error" de redondeo, se acumulará en operaciones posteriores...
Entonces, generalmente, NO, no puede usar un algoritmo tan ingenuo para convertir decimales arbitrarios, esto puede conducir a un número redondeado incorrectamente, desviado en varios ulp del correcto, como otros ya le han dicho.

PERO A VER HASTA DONDE PODEMOS LLEGAR:

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 entero Mantissa si tiene muchos dígitos, como al elevar 10 a la potencia del exponente sesgado...

Afortunadamente, si las dos primeras operaciones son exactas, entonces puedes permitirte 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 un 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 número entero Mantissa y un exponente sesgado entre -10 y 10.

En doble precisión, 53 bits,

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

Por lo tanto, puede permitirse 15 dígitos decimales y un exponente sesgado entre -22 y 22.

Depende de usted ver si sus números siempre estarán en el rango correcto...(Si eres realmente complicado, puedes equilibrar la mantisa y el exponente insertando/eliminando ceros finales).

De lo contrario, tendrás que utilizar cierta precisión extendida.
Si su lenguaje proporciona números enteros de precisión arbitraria, entonces es un poco complicado hacerlo bien, pero no tanto. Hice esto en Smalltalk y escribí en un blog sobre 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 estas son implementaciones simples e ingenuas.Afortunadamente, libc está más optimizado.

Answer 6

Mi primer pensamiento es analizar la cadena en un int64 mantisa y una int exponente decimal usando solo los primeros 18 dígitos de la mantisa.Por ejemplo, 1.2345e-5 se analizaría en 12345 y -9.Luego seguiría multiplicando la mantisa por 10 y disminuyendo 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 puedan usarse para convertir el número de la forma decimal n*10^m a la forma binaria p*2^q.El factor sería otro. int64 así que multiplicaría la mantisa por ella de modo que obtuviera los 64 bits superiores del número de 128 bits resultante.Este int64 la mantisa 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 quieras 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.

Answer 7

Para eso, debe comprender el estándar IEEE 754 para poder realizar una representación binaria adecuada.Después de eso puedes usar Flotador.intBitsToFloat o Doble.longBitsToDouble.

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

Answer 8

Si desea obtener el resultado más preciso posible, debe utilizar una precisión de trabajo interna más alta y luego convertir el resultado a la precisión deseada.Si no le importan algunos ULP de error, puede multiplicar repetidamente por 10 según sea necesario con la precisión deseada.Yo evitaría la función pow(), ya que producirá resultados inexactos para exponentes grandes.

Answer 9

No es posible convertir cualquier cadena arbitraria que represente un número en doble o flotante sin perder precisión.Hay muchos números fraccionarios que se pueden representar exactamente en decimal (p. ej."0.1") que sólo se puede aproximar en un binario flotante o doble.Esto es similar a cómo la fracción 1/3 no se puede representar exactamente en decimal, solo puedes 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 biblioteca?Mencionaste Java;la mayoría de los JDK incluyen el código fuente de las bibliotecas de clases para que pueda consultar cómo funciona el método java.lang.Double.parseDouble(String).Por supuesto, algo como BigDecimal es mejor para controlar la precisión y los modos de redondeo, pero dijiste que debe ser flotante o doble.

Answer 10

Usando una máquina de estados.Es bastante fácil de hacer e incluso funciona si se interrumpe el flujo de datos (sólo hay que conservar el estado y el resultado parcial).También puedes usar un generador de analizador (si estás haciendo algo más complejo).

Answer 11

Estoy de acuerdo con el término.Una máquina de estados es la mejor manera de realizar esta tarea, ya que hay muchas formas estúpidas de dañar un analizador.Estoy trabajando en uno ahora, creo que está completo y creo que tiene 13 estados.

El problema no es baladí.

Soy un ingeniero de hardware interesado en diseñar hardware de punto flotante.Estoy en mi segunda implementación.

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

que en la página 18 ofrece algunos casos de prueba interesantes.

Sí, he leído el artículo de Clinger, pero siendo un ingeniero de hardware ingenuo, no puedo entender el código presentado.La referencia al algoritmo de Steele tal como se responde en el texto de Knuth me resultó útil.Tanto la entrada como la salida son problemáticas.

Todas las referencias antes mencionadas a varios artículos son excelentes.

Todavía tengo que registrarme aquí todavía, pero cuando lo haga, suponiendo que no se haya registrado el inicio de sesión, será hermano.(hermano-punto).

Clyde