Encontrar min/max de un flotador/doble que tiene la misma representación interna

Question

Refrescante en floating points (también PDF), IEEE-754 y tomando parte in this discussion on floating point rounding when converting to strings, me llevó a jugar: cómo puedo obtener el valor máximo y mínimo para un dado un número de punto flotante cuyas representaciones binarias son iguales.

Descargo de responsabilidad: para esta discusión, me gusta adherirme al punto flotante de 32 y 64 bits como lo describe IEEE-754. No estoy interesado en el punto flotante extendido (80 bits) o quads (IEEE-754-2008 de 128 bits) ni en ningún otro estándar (IEEE-854).

Antecedentes: Las computadoras son malas para representar 0.1 en representación binaria. En C#, un flotante representa esto como 3DCCCCCD internamente (C# usa redondeada a más cercana) y un doble como 3FB999999999999A. Los mismos patrones de bits se utilizan para 0.100000005 decimal (flotante) y 0.1000000000000000124 (doble), pero no para 0.1000000000000000144 (doble).

Por conveniencia, el siguiente código C# da estas representaciones internas:

string GetHex(float f) 
{ 
    return BitConverter.ToUInt32(BitConverter.GetBytes(f), 0).ToString("X"); 
} 

string GetHex(double d) 
{ 
    return BitConverter.ToUInt64(BitConverter.GetBytes(d), 0).ToString("X"); 
} 

// float 
Console.WriteLine(GetHex(0.1F)); 

// double 
Console.WriteLine(GetHex(0.1)); 

En el caso de 0.1, no hay menor número decimal que se representa con el mismo patrón de bits, cualquier 0.99...99 dará lugar a una diferente la representación de bit (es decir, float para 0.999999937 produce 3F7FFFFF internamente).

Mi pregunta es simple: cómo puedo encontrar el valor decimal más bajo y más alto para un flotante determinado (o doble) que se almacena internamente en la misma representación binaria.

Por qué: (Sé que preguntará) para encontrar el error al redondear en .NET cuando se convierte en una cadena y cuando se convierte a partir de una cadena, para encontrar el valor exacto interno y para entender el mío redondeando errores mejor.

Supongo que es algo como: tomar la mantisa, eliminar el resto, obtener su valor exacto, obtener uno (mantissa-bit) más alto y calcular la media: cualquier valor inferior a ese arrojará el mismo patrón de bits. Mi problema principal es: cómo obtener la parte fraccionaria como un entero (la manipulación de bits no es mi activo más fuerte). Jon Skeet's DoubleConverter clase puede ser útil.

Answer 1

Una forma de obtener a su pregunta es encontrar el tamaño de un ULP, o U nit en el L ast P encaje, de su número de coma flotante. Simplificando un poco, esta es la distancia entre un número de coma flotante dado y el siguiente número más grande. De nuevo, simplificando un poco, dado un valor de coma flotante representable x, cualquier cadena decimal cuyo valor esté entre (x - 1/2 ulp) y (x + 1/2 ulp) se redondeará a x cuando se convierta en un flotante punto de referencia

El truco es que (x +/- 1/2 ulp) no es un número de punto flotante representable, por lo que calcular su valor requiere que utilice un tipo de coma flotante más amplio (si hay uno disponible) o un ancho arbitrario grande decimal o tipo similar para hacer el cálculo.

¿Cómo se encuentra el tamaño de un ulp?Una forma relativamente fácil es más o menos lo que usted sugiere, escrito aquí es pseudocódigo C-ish, porque no sé C#:

float absX = absoluteValue(x); 
uint32_t bitPattern = getRepresentationOfFloat(absx); 
bitPattern++; 
float nextFloatNumber = getFloatFromRepresentation(bitPattern); 
float ulpOfX = (nextFloatNumber - absX); 

Esto funciona porque sumando uno al patrón de bits de x se corresponde exactamente con la adición de una ULP a el valor de x. No se produce redondeo en coma flotante en la resta porque los valores involucrados son muy cercanos (en particular, hay un teorema de la aritmética de punto flotante ieee-754 que si dos números x y y satisfacen y/2 < = x < = 2y, entonces x - y se calcula exactamente). Las únicas salvedades aquí son:

1. si x pasa a ser el mayor número de coma flotante finito, esto no va a funcionar (se devolverá inf, que es claramente erróneo).
2. si su plataforma no soporta correctamente el subdesbordamiento gradual (digamos un dispositivo incrustado que se ejecuta en el modo al ras con el cero), esto no funcionará para valores muy pequeños de x.

Parece que no es probable que esté en ninguna de esas situaciones, por lo que esto debería funcionar bien para sus propósitos.

Ahora que sabes lo que es un ulp de x, puedes encontrar el intervalo de valores que se redondea a x. Puede calcular ulp (x)/2 exactamente en coma flotante, porque la división de coma flotante en 2 es exacta (nuevamente, salvo bajo flujo). Entonces solo necesita calcular el valor de x +/- ulp (x)/2 tipo de coma flotante más grande adecuado (double funcionará si está interesado en float) o en un tipo de Decimal grande, y tiene su intervalo.

He hecho algunas suposiciones simplificadoras a través de esta explicación. Si necesita que esto realmente se deletree exactamente, deje un comentario y ampliaré las secciones que son un poco confusas cuando tengo la oportunidad.

---

Otra nota la siguiente declaración en su pregunta:

En el caso de 0,1, no hay ningún menor número decimal que se representa con el mismo patrón de bits

es incorrecto. Acabas de estar mirando los valores incorrectos (0,999999 ... en lugar de 0,099999 ... - un error fácil de hacer).

Answer 2

Python 3.1 acaba de implementar algo como esto: vea the changelog (scroll down a bit), bug report.