¿Cómo se imprime el valor EXACTO de un número de punto flotante?

5 minutos de lectura

avatar de usuario
R.. GitHub DEJAR DE AYUDAR A ICE

En primer lugar, esta no es una pregunta de novato de coma flotante. Sé que los resultados de la aritmética de punto flotante (sin mencionar las funciones trascendentales) generalmente no se pueden representar exactamente, y que la mayoría de los decimales finales no se pueden representar exactamente como números binarios de punto flotante.

Dicho esto, cada posible valor de coma flotante corresponde exactamente a un racional diádico (un número racional p/q donde q es una potencia de 2), que a su vez tiene una representación decimal exacta.

Mi pregunta es: ¿Cómo encuentra esta representación decimal exacta de manera eficiente? sprintf y funciones similares generalmente solo se especifican hasta una cantidad de dígitos significativos para determinar de manera única el valor de punto flotante original; no necesariamente imprimen la representación decimal exacta. Conozco un algoritmo que he usado, pero es muy lento, O(e^2) donde e es el exponente. Aquí hay un esquema:

  1. Convierta la mantisa en un entero decimal. Puede hacer esto separando los bits para leer la mantisa directamente, o puede escribir un bucle de coma flotante desordenado que primero multiplique el valor por una potencia de dos para ponerlo en el rango 1<=x<10, luego tira un dígito a la vez lanzando a int, restando y multiplicando por 10.
  2. Aplica el exponente multiplicando o dividiendo repetidamente por 2. Esta es una operación en el cuerda de dígitos decimales que generó. Cada ~3 multiplicaciones agregará un dígito adicional a la izquierda. Cada división agregará un dígito adicional a la derecha.

¿Es esto realmente lo mejor posible? Lo dudo, pero no soy un experto en punto flotante y no puedo encontrar una manera de hacer los cálculos de base 10 en la representación de punto flotante del número sin encontrarme con la posibilidad de resultados inexactos (multiplicando o dividiendo por cualquier cosa menos una potencia de 2 es una operación con pérdidas en números de punto flotante a menos que sepa que tiene bits libres para trabajar).

  • Al final, simplemente reemplacé mi viejo código base-10 con base-1e9 y repetí la multiplicación/división por 2 con mult por 2^29 y div por 2^9 para la mayoría de las iteraciones seguido de mult/div por 2 para el cola. El código resultante imprime el código más pequeño de 80 bits. long double en un tiempo bastante insignificante, así que estoy bastante feliz.

    – R.. GitHub DEJA DE AYUDAR A ICE

    30 de julio de 2010 a las 23:59

  • Jon Skeet tiene un Clase DoubleConverter que puede imprimir las representaciones decimales exactas. Está escrito en C# pero puedes convertirlo a C stackoverflow.com/questions/4732680/…

    – phuclv

    21 de junio de 2014 a las 11:02

avatar de usuario
Greg Kuperberg

Esta pregunta tiene una parte burocrática y una parte algorítmica. Un número de punto flotante se almacena internamente como (2mi × metro), donde mi es un exponente (en sí mismo en binario) y metro es una mantisa. La parte burocrática de la pregunta es cómo acceder a estos datos, pero R. parece más interesado en la parte algorítmica de la pregunta, es decir, convertir (2mi × metro) a una fracción (a/B) en forma decimal. La respuesta a la pregunta burocrática en varios idiomas es frexp (que es un detalle interesante que no sabía antes de hoy).

Es cierto que a primera vista, se necesita O(mi2) trabajar solo para escribir 2mi en decimal, y más tiempo aún para la mantisa. Pero, gracias a la magia de la Schönhage–Strassen algoritmo de multiplicación rápida, puedes hacerlo en Õ(mi) tiempo, donde la tilde significa “hasta log factores”. Si ve Schönhage-Strassen como magia, entonces no es tan difícil pensar en qué hacer. Si mi es par, puedes calcular recursivamente 2mi/2y luego elevarlo al cuadrado usando la multiplicación rápida. Por otro lado si mi es impar, puedes calcular recursivamente 2mi−1 y luego duplicarlo. Hay que tener cuidado de comprobar que existe una versión de Schönhage–Strassen en base 10. Aunque no está muy documentado, se puede hacer en cualquier base.

Convertir una mantisa muy larga de binario a base 10 no es exactamente la misma pregunta, pero tiene una respuesta similar. Puedes dividir la mantisa en dos mitades, metro = a × 2k + B. Luego convierte recursivamente a y B a base 10, convierte 2k a la base 10, y haz otra multiplicación rápida para calcular metro en base 10

El resultado abstracto detrás de todo esto es que puedes convertir números enteros de una base a otra en Õ(norte) hora.

Si la pregunta es sobre números de coma flotante estándar de 64 bits, entonces es demasiado pequeño para el sofisticado algoritmo de Schönhage-Strassen. En este rango, en cambio, puede ahorrar trabajo con varios trucos. Un enfoque es almacenar todos los 2048 valores de 2mi en una tabla de búsqueda, y luego trabaje en la mantisa con multiplicación asimétrica (entre la multiplicación larga y la multiplicación corta). Otro truco es trabajar en base 10000 (o una potencia mayor de 10, según la arquitectura) en lugar de base 10. Pero, como señala R. en los comentarios, los números de punto flotante de 128 bits ya permiten exponentes lo suficientemente grandes para llamar a Cuestiona tanto las tablas de búsqueda como la multiplicación larga estándar. En la práctica, la multiplicación larga es la más rápida hasta un puñado de dígitos, luego en un rango medio significativo se puede usar Multiplicación Karatsuba o Multiplicación de Toom-Cooky luego, una variación de Schönhage-Strassen es mejor no solo en teoría sino también en la práctica.

En realidad, el paquete entero grande BPF ya tiene Õ(norte)-conversión de raíz de tiempo, así como buenas heurísticas para elegir el algoritmo de multiplicación. La única diferencia entre su solución y la mía es que, en lugar de hacer grandes operaciones aritméticas en base 10, calculan grandes potencias de 10 en base 2. En esta solución, también necesitan una división rápida, pero eso se puede obtener a partir de una multiplicación rápida en cualquier de varias maneras.

  • ¡Gracias por el enlace y la primera respuesta con cualquier contenido teórico! Parece que Toom-cocinero en realidad podría ser el algoritmo preferible para exponentes no astronómicos.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 de julio de 2010 a las 19:03

  • Muy interesante. ¿Podría explicar cómo el uso de la base 10000 acelera las cosas?

    – Steven Sudit

    9 de julio de 2010 a las 19:04

  • Steven: Usar la base 10000 acelera las cosas porque es 4 veces más rápido que la base 10 debido a que ambos encajan en una palabra de máquina.

    – Gabo

    9 de julio de 2010 a las 19:08

  • @Gabe, ¿estás seguro? Un flotante de “64 bits” implica una aritmética de ~1076 dígitos (decimales). Un flotador de “80 bits” implica una aritmética de ~16448 dígitos.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 de julio de 2010 a las 19:28

  • Estás pensando en casos en los que el exponente es positivo. Si es negativo, cada vez que disminuya más el exponente, obtendrá un lugar decimal adicional a la derecha (manteniendo un ‘5’), pero se necesitan varios decrementos de exponente para borrar un lugar decimal a la izquierda (por ejemplo, 5->2->1 ->0). Sobreestimé, pero parece que necesita aproximadamente binary_exp * 2/3 dígitos decimales, por lo que ~ 700 dígitos para IEEE 754.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 de julio de 2010 a las 19:54

avatar de usuario
rick regan

Veo que ya ha aceptado una respuesta, pero aquí hay un par de implementaciones de código abierto de esta conversión que quizás desee ver:

  1. david gays dtoa() función en dtoa.c: https://www.netlib.org/fp/dtoa.c.

  2. La función ___printf_fp() en el /stdio-common/printf_fp.c archivo en Glibc (https://ftp.gnu.org/gnu/glibc/glibc-2.11.2.tar.gzpor ejemplo).

Ambos imprimirán tantos dígitos como pidas en un %f-escribe printfcomo he escrito sobre en:

  • ¡Gran respuesta! Este es el tipo de cosa que estaba buscando. Buscaré esas fuentes.

    – R.. GitHub DEJA DE AYUDAR A ICE

    10 de julio de 2010 a las 18:26

  • Tu blog es fantástico. Había visto algunas publicaciones al respecto antes, pero no sabía que el autor también existe aquí 🙂

    – devnull

    27 de junio de 2014 a las 13:13

  • ISTM que la implementación de David M. gay es una implementación estándar de facto (pero no oficial). Varios idiomas también lo han adoptado según sus necesidades. De hecho, estoy tratando de hacer que la gente de Delphi y C++Builder en Embarcadero también lo adopte. — Oh, espera, ¿tú eres el chico de Exploring Binary? ¡Buen trabajo! Me encanta tu sitio.

    – Rudy Velthuis

    18 oct 2018 a las 22:19

Se ha trabajado mucho en la impresión de números de punto flotante. El estándar de oro es imprimir un equivalente decimal de longitud mínima, de modo que cuando se vuelve a leer el equivalente decimal, se obtiene el mismo número de punto flotante con el que comenzó, sin importar cuál sea el modo de redondeo durante la lectura. Puede leer sobre el algoritmo en el excelente artículo de Burger y Dybvig.

  • Ese es un problema bien investigado que en cierto modo es más simple y en cierto modo más difícil, pero a pesar de todo es un problema diferente. Gracias por el enlace.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 de julio de 2010 a las 20:40

  • @R: Ups. No entendí la pregunta. Tal vez un ejemplo hubiera ayudado.

    —Norman Ramsey

    9 de julio de 2010 a las 22:51

avatar de usuario
Gabe

Aunque es C# y su pregunta está etiquetada con C, Jon Skeet tiene un código para convertir un double a su representación exacta como una cadena: http://www.yoda.arachsys.com/csharp/DoubleConverter.cs

De un vistazo rápido, no parece ser demasiado difícil de migrar a C, y aún más fácil de escribir en C++.

Tras una mayor reflexión, parece que el algoritmo de Jon también es O (e ^ 2), ya que también realiza un bucle sobre el exponente. Sin embargo, eso significa que el algoritmo es O (log (n) ^ 2) (donde n es el número de coma flotante), y no estoy seguro de que pueda convertir de base 2 a base 10 en mejor tiempo que log-squared.

Bueno, como no soy un experto en punto flotante, preferiría usar una biblioteca de código abierto bien probada.

los MPFR de GNU es bueno

La biblioteca MPFR es una biblioteca C para cálculos de punto flotante de precisión múltiple con redondeo correcto. El objetivo principal de MPFR es proporcionar una biblioteca para el cálculo de punto flotante de precisión múltiple que sea eficiente y tenga una semántica bien definida.

  • Y admite la conversión de doble a decimal arbitrario.

    – Steven Sudit

    9 de julio de 2010 a las 18:15

avatar de usuario
dan04

sprintf y funciones similares generalmente solo se especifican hasta una cantidad de dígitos significativos para determinar de manera única el valor de coma flotante original; no necesariamente imprimen la representación decimal exacta.

Puede solicitar más dígitos significativos que los predeterminados:

printf("%.100g\n", 0.1);

huellas dactilares 0.1000000000000000055511151231257827021181583404541015625.

  • Y admite la conversión de doble a decimal arbitrario.

    – Steven Sudit

    9 de julio de 2010 a las 18:15

avatar de usuario
miguel dorgan

Si desea obtener resultados más exactos, ¿por qué no utilizar las matemáticas de punto fijo? Las conversiones son rápidas. El error es conocido y se puede solucionar. No es una respuesta exacta a su pregunta, sino una idea diferente para usted.

  • No sería una mala idea si estuviera usando esto en una aplicación específica, pero el dominio del problema está resolviendo específicamente este punto flotante (bastante doloroso) para la conversión decimal exacta.

    – R.. GitHub DEJA DE AYUDAR A ICE

    9 de julio de 2010 a las 18:03

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad