floating point - puro - Número de ceros consecutivos en la representación decimal de un doble

numeros decimales

Question

¿Cuál es la cantidad máxima de ceros consecutivos no consecutivos (sin par) en la representación decimal exacta de un número de precisión doble IEEE 754?

Contexto

Considere el problema de convertir un double en decimal, redondeando hacia arriba (o hacia abajo), cuando la única primitiva que puede usar es una función existente que se convierte en la más cercana (redondeada correctamente a cualquier número de dígitos deseado).

Puede obtener algunos dígitos adicionales y eliminarlos usted mismo. Por ejemplo, para redondear 1.875 hasta un dígito después del punto, puede convertirlo a la representación decimal más cercana con dos o tres dígitos después del punto ( 1.87 o 1.875 ) y luego borrar los dígitos usted mismo para obtener la respuesta esperada, 1.8 .

Para algunos números y opciones de un número adicional de dígitos para imprimir, este método produce un resultado incorrecto. Por ejemplo, para el double más cercano a 0.799999996 , convirtiendo a decimal, redondeando al más cercano, a 2, 3 o 4 dígitos después del punto produce 0.80 , 0.800 y 0.8000 . Al borrar los dígitos adicionales después de la conversión, se obtiene el resultado 0.8 , cuando el resultado deseado fue 0.7 .

Como hay un número finito de double , existe una cantidad de dígitos adicionales que es suficiente imprimir en la conversión inicial para calcular siempre el resultado correcto después del truncamiento de la representación decimal obtenida. Este número está relacionado con el número máximo de nueves o ceros que pueden aparecer en la representación decimal exacta de un double .

Relacionado

Esta pregunta está relacionada con esta pregunta acerca del redondeo hacia abajo en la conversión de un double a decimal , y es dual de esta pregunta sobre la conversión redondeada correctamente de representaciones decimales a dobles .

Answer 1

La solución pragmática es:

• llame a su función existente para devolver una cadena que contenga solo el número de decimales que necesita;
• convertir el resultado a un valor de doble precisión;
• si este valor es mayor que el original, disminuya el dígito final.

Answer 2

Obviamente, es al menos 15, como se ilustra en este código de Smalltalk / Squeak:

1.0 successor asTrueFraction printShowingMaxDecimalPlaces: 100.
-> ''1.0000000000000002220446049250313080847263336181640625''

1.0 predecessor asTrueFraction printShowingMaxDecimalPlaces: 100.
-> ''0.99999999999999988897769753748434595763683319091796875''

Ahora, es un poco más complicado demostrar que no puede haber más de 15 ceros consecutivos. Busca un número de coma flotante f=(A*10^n+B)*10^p donde

• n> 15
• A es un número entero
• 0 <B <1

Pero el flotante también debe expresarse como entero y exponente sesgado f=s*2^e donde

• s es un número entero
• 0 <s <2 ^ 53 <5 ^ 23

Tenemos así: s=(A*2^n*5^n+B)*2^(pe)*5^p con s < 2^53 .

Mi primera respuesta fue falsa, esto debe ser terminado ...

En general, s puede escribirse, s = 2 ^ a * 5 ^ b + c, c no divisible por 2 ni 5.

A * 2 ^ (n + pe) * 5 ^ (n + p) + B * 2 ^ (pe) * 5 ^ p = 2 ^ a * 5 ^ b + c

Podemos buscar una construcción con A = 1, B = c * 2 ^ (ep) / 5 ^ p <1, n + pe = a, n + p = b, ep = na.

B = c * 2 ^ (na) / 5 ^ (bn)

Intenté todos los pares a, b, tales que 2 ^ 52 <2 ^ a * 5 ^ b <2 ^ 53, pero no pude encontrar n> 15 que satisficieran B <1 ... Probar con A> 1 solo hará que las cosas peor (implica reducir a y b).

Por lo tanto, no creo que haya ningún doble con 16 ceros consecutivos, pero no es una hermosa demostración ...

Answer 3

No tengo una solución para esto, pero este es un enfoque que podría seguir:

• Mantenga un registro de la cadena de ceros más larga encontrada hasta el momento. Llame la longitud L Es al menos 15 de largo, gracias a la respuesta de aka.nice.
• Para cada posible exponente y cada ubicación 10^k donde L+1 ceros consecutivos podrían ocurrir, se obtiene un pequeño problema desordenado de mochila.
• Calcule las 53 potencias correspondientes de dos módulos 10^{k+L}, y redúzcalos para que tengan alrededor de L+1 cifras significativas.
• Encuentre todas las combinaciones de las primeras 26 potencias de dos módulos 10^{k+L} usando matemáticas de números enteros nativos.
• Encuentre todas las combinaciones de las últimas 26 potencias de dos módulos 10^{k+L} manera similar.
• Clasifique ambas mitades y busque pares que le den algo muy cercano al negativo del bit implícito utilizando un escaneo lineal. Probablemente solo obtengas unos partidos haciendo esto.
• Verifica cada partida usando sprintf o algo así.

Parece que tienes que ejecutar este ciclo unos millones de veces, pero debería ser factible en unas pocas docenas de computadoras modernas en unas pocas docenas de horas.

También agregaría que hay un entero exactamente representable en coma flotante que tiene un montón de ceros finales: 87960930222080000000000000000000000 tiene 22 ceros finales y es 10F0CF064DD5920000000000000000 en hexadecimal. (De hecho, 10 ^ 22 es exactamente representable como un doble y obviamente tiene 22 ceros finales. No se puede hacer nada mejor ya que 5 ^ 23 necesitarían dividir tal significado y eso es imposible. Oh bien).

Answer 4

[Versión corta: la respuesta es 20. Reformule el problema en términos de encontrar buenas aproximaciones racionales a números de la forma 2^e / 10^d ; luego use fracciones continuas para encontrar la mejor aproximación para cada d adecuada.]

La respuesta parece ser 20 : es decir, hay ejemplos de flotantes IEEE 754 binary64 cuya expansión decimal tiene 20 ceros consecutivos, pero no hay ninguno con 21 ceros consecutivos en su expansión decimal (excluyendo los ceros al principio y al final). Lo mismo es cierto para cadenas de nueves.

Para la primera parte, todo lo que tengo que hacer es exhibir tal flotador. El valor 0x1.9527560bfbed8p-1000 es representable exactamente como un float binary64, y su expansión decimal contiene una cadena de 20 ceros:

1.-301

Para la parte de la pregunta sobre nueves, la expansión decimal de 0x1.c23142c9da581p-405 contiene una cadena de 20 nueves:

2.12818792307269553358078502102171540639252016258831784842556110831434197718043638405555406495645619729155240037555858106390933161420388023706431461384056688295540725831155392678607931808851292893574214797681879999999999999999999941026584542575391157788777223962620780080784703190447744595561259568772261019375946489162743091583251953125E-122

Para explicar cómo encontré los números anteriores y para mostrar que no hay ejemplos con 21 ceros consecutivos, necesitaremos trabajar un poco más. Un número real con una cadena larga de 9s o 0s en su expansión decimal tiene la forma (a + eps)*10^d para algunos enteros d y el número real eps , con a distinto de cero (podríamos suponer también positivo) y eps distintos de cero y pequeños. Por ejemplo, si 0 < abs(eps) < 10^-10 entonces a + eps tiene al menos 10 ceros después del punto decimal (si eps es positivo), o 10 nueves después del punto decimal (si eps es negativo); multiplicar por 10^d permite cambiar la ubicación de la cadena de ceros o nueves.

Pero nos interesan los números del formulario anterior que se pueden representar simultáneamente como un flotador IEEE 754 binary64; en otras palabras, números que también son de la forma b*2^e para los enteros b y e satisfacen 2^52 <= b <= 2^53 , con e limitado en el rango (y con algunas restricciones adicionales en b una vez que obtenemos en el rango subnormal, pero podemos preocuparnos más tarde).

Así que combinando esto, estamos buscando soluciones a (a + eps) * 10^d = b * 2^e en los enteros a , b , d y e tales que eps es pequeño, a es positivo y 2^52 <= b <= 2^53 (y nos preocuparemos por los rangos para d e más adelante). Reorganizando, obtenemos eps / b = 2^e / 10^d - a / b . En otras palabras, estamos buscando buenas aproximaciones racionales a 2^e / 10^d , con un denominador limitado. Esa es una aplicación clásica de fracciones continuas: dados d e , uno puede encontrar eficientemente la mejor aproximación racional con un denominador limitado por 2^53 .

Entonces, la estrategia de solución en general es:

for each appropriate d and e:
    find the best rational approximation a / b to 2^e / 10^d with denominator <= 2^53
    if (the error in this rational approximation is small enough):
        # we''ve got a candidate
        examine the decimal expansion of b*2^e

Tenemos solo alrededor de 2 mil valores para comprobar e, y en el peor unos cientos de d para cada uno de ellos, por lo que todo es computacionalmente muy factible.

Ahora a los detalles: ¿qué significa "lo suficientemente pequeño"? ¿Qué d y e son "apropiados"?

En cuanto a "lo suficientemente pequeño": digamos que estamos buscando cadenas de al menos 19 ceros o nueves, por lo que estamos buscando soluciones con 0 < abs(eps) <= 10^-19 . De modo que es suficiente encontrar, para cada d y e , todas las a y b tales que abs(2^e / 10^d - a / b) <= 10^-19 * 2^-52 . Tenga en cuenta que debido al límite en b , puede haber solo una de esas fracciones a / b ; si hubiera otro tal a'' / b'' entonces tenemos 1 / 2^106 <= 1 / (b *b'') <= abs(a / b - a'' / b'') <= 2 * 10^-19 * 2^-52 , una contradicción. Entonces, si tal fracción existe, necesariamente es la mejor aproximación racional con el denominador dado encuadernado.

Para d y e : para cubrir el rango binario64 incluyendo los subnormales, queremos que e -1126 de -1126 a 971 inclusive. Si d es demasiado grande, entonces 2^e / 10^d será mucho más pequeño que 2^-53 y no hay esperanza de una solución; d <= 16 + floor(e*log10(2)) es un límite práctico. Si d es demasiado pequeño (o demasiado negativo), entonces 2^e / 10^d será un número entero y no hay solución; para evitar eso, queremos d > min(e, 0) .

Con todo lo que cubre, vamos a escribir un código. La solución de Python es bastante sencilla, gracias en parte a la existencia del método Fraction.limit_deminator , que hace exactamente el trabajo de encontrar la mejor aproximación racional dentro de los límites.

from fractions import Fraction
from itertools import groupby
from math import floor, log10

def longest_run(s, c):
    """Length of the longest run of a given character c in the string s."""
    runs = [list(g) for v, g in groupby(s, lambda k: k == c) if v]
    return max(len(run) for run in runs) if runs else 0

def closest_fraction(d, e):
    """Closest rational to 2**e/10**d with denominator at most 2**53."""
    f = Fraction(2**max(e-d, 0) * 5**max(-d, 0), 2**max(0, d-e) * 5**max(0, d))
    approx = f.limit_denominator(2**53)
    return approx.numerator, approx.denominator

seen = set()
emin = -1126
emax = 971
for e in range(emin, emax+1):
    dmin = min(e, 0) + 1
    dmax = int(floor(e*log10(2))) + 16
    for d in range(dmin, dmax+1):
        num, den = closest_fraction(d, e)
        x = float.fromhex(''0x{:x}p{}''.format(den, e))
        # Avoid duplicates.
        if x in seen:
            continue
        seen.add(x)
        digits = ''{:.1000e}''.format(x).split(''e'')[0].replace(''.'','''').strip(''0'')
        zero_run = longest_run(digits, ''0'')
        if zero_run >= 20:
            print "{} has {} zeros in its expansion".format(x.hex(), zero_run)
        nine_run = longest_run(digits, ''9'')
        if nine_run >= 20:
            print "{} has {} nines in its expansion".format(x.hex(), nine_run)

Hay muchas posibilidades de mejorar el rendimiento allí ( no usar el módulo de fractions de Python sería un buen comienzo :-); tal como está, tarda unos minutos en completarse. Y aquí están los resultados:

0x1.9527560bfbed8p-1000 has 20 zeros in its expansion
0x1.fa712b8efae8ep-997 has 20 zeros in its expansion
0x1.515476ae79b24p-931 has 20 nines in its expansion
0x1.a5a9945a181edp-928 has 20 nines in its expansion
0x1.86049d3311305p-909 has 20 zeros in its expansion
0x1.69c08f3dd8742p-883 has 20 zeros in its expansion
0x1.1b41d80091820p-861 has 20 zeros in its expansion
0x1.62124e00b5e28p-858 has 20 zeros in its expansion
0x1.ba96e180e35b2p-855 has 20 zeros in its expansion
0x1.31c5be6377c48p-786 has 20 zeros in its expansion
0x1.7e372dfc55b5ap-783 has 20 zeros in its expansion
0x1.7e89dc1c3860ap-555 has 20 nines in its expansion
0x1.7e89dc1c3860ap-554 has 20 nines in its expansion
0x1.7e89dc1c3860ap-553 has 20 nines in its expansion
0x1.7e89dc1c3860ap-552 has 20 nines in its expansion
0x1.30bd91ea994cbp-548 has 20 zeros in its expansion
0x1.4a5f9de9ee064p-468 has 20 nines in its expansion
0x1.9cf785646987dp-465 has 20 nines in its expansion
0x1.c23142c9da581p-408 has 20 nines in its expansion
0x1.c23142c9da581p-407 has 20 nines in its expansion
0x1.c23142c9da581p-406 has 20 nines in its expansion
0x1.c23142c9da581p-405 has 20 nines in its expansion
0x1.ba431f4e34be9p+738 has 20 nines in its expansion

Answer 5

Este código eliminará 0 al final del decimal.

 private void button1_Click(object sender, EventArgs e)
        {
            String Str = textBox1.Text;
            String lstVal = GetDecimalString(Str);
           textBox2.Text = lstVal;
        }

    private static string GetDecimalString(String Str)
    {
        String lstVal = "";
        if (Str.IndexOf(".") > -1)
        {
            String[] Last = Str.Split(''.'');
            if (Last.Length == 1)
            {
                lstVal = Last[0];
            }
            else
            {
                lstVal = Last[1];
            }
            String TrimedData = lstVal;
            for (int i = lstVal.Length - 1; i >= 0; i--)
            {
                if (TrimedData.EndsWith("0") && TrimedData.Length > 3)
                {
                    TrimedData = TrimedData.Substring(0, i - 1);
                }
            }
            lstVal = TrimedData;

            if (lstVal.Length < 3)
                lstVal = lstVal.PadRight(3, ''0'');

            lstVal = String.Join(".", Last[0], lstVal);
        }
        else
        {
            lstVal = Str;
        }
        return lstVal;
    }