Por que uma conversão de ida e volta através de uma string não é segura para uma dupla?

185

Recentemente, tive que serializar um duplo no texto e depois recuperá-lo. O valor parece não ser equivalente:

double d1 = 0.84551240822557006;
string s = d1.ToString("R");
double d2 = double.Parse(s);
bool s1 = d1 == d2;
// -> s1 is False

Mas, de acordo com o MSDN: Strings de formato numérico padrão , a opção "R" deve garantir segurança de ida e volta.

O especificador de formato de ida e volta ("R") é usado para garantir que um valor numérico convertido em uma seqüência de caracteres seja analisado novamente no mesmo valor numérico

Por quê isso aconteceu?

Philip Ding
fonte
6
Eu depurado na minha VS e seu retorno verdade aqui
Neel
19
Eu o reproduzi retornando falso. Pergunta muito interessante.
Jon Skeet
40
.net 4.0 x86 - true, .net 4.0 x64 - false
Ulugbek Umirov
25
Parabéns por encontrar um bug tão impressionante no .net.
Aron19:
14
Viagem @Casperah redondo é especificamente destinado a evitar inconsistências ponto flutuante
Gusdor

Respostas:

178

Eu encontrei o bug.

O .NET faz o seguinte em clr\src\vm\comnumber.cpp:

DoubleToNumber(value, DOUBLE_PRECISION, &number);

if (number.scale == (int) SCALE_NAN) {
    gc.refRetVal = gc.numfmt->sNaN;
    goto lExit;
}

if (number.scale == SCALE_INF) {
    gc.refRetVal = (number.sign? gc.numfmt->sNegativeInfinity: gc.numfmt->sPositiveInfinity);
    goto lExit;
}

NumberToDouble(&number, &dTest);

if (dTest == value) {
    gc.refRetVal = NumberToString(&number, 'G', DOUBLE_PRECISION, gc.numfmt);
    goto lExit;
}

DoubleToNumber(value, 17, &number);

DoubleToNumberé bem simples - basta chamar _ecvt, que está no tempo de execução C:

void DoubleToNumber(double value, int precision, NUMBER* number)
{
    WRAPPER_CONTRACT
    _ASSERTE(number != NULL);

    number->precision = precision;
    if (((FPDOUBLE*)&value)->exp == 0x7FF) {
        number->scale = (((FPDOUBLE*)&value)->mantLo || ((FPDOUBLE*)&value)->mantHi) ? SCALE_NAN: SCALE_INF;
        number->sign = ((FPDOUBLE*)&value)->sign;
        number->digits[0] = 0;
    }
    else {
        char* src = _ecvt(value, precision, &number->scale, &number->sign);
        wchar* dst = number->digits;
        if (*src != '0') {
            while (*src) *dst++ = *src++;
        }
        *dst = 0;
    }
}

Acontece que _ecvtretorna a string 845512408225570.

Observe o zero à direita? Acontece que faz toda a diferença!
Quando o zero está presente, o resultado é analisado novamente0.84551240822557006, que é o seunúmero original - portanto, ele é igual e, portanto, somente 15 dígitos são retornados.

No entanto, se eu truncar a string nesse zero para 84551240822557, então eu volto 0.84551240822556994, que não é o seu número original e, portanto, retornaria 17 dígitos.

Prova: execute o seguinte código de 64 bits (a maioria dos quais extraí do Microsoft Shared Source CLI 2.0) no seu depurador e examine vno final de main:

#include <stdlib.h>
#include <string.h>
#include <math.h>

#define min(a, b) (((a) < (b)) ? (a) : (b))

struct NUMBER {
    int precision;
    int scale;
    int sign;
    wchar_t digits[20 + 1];
    NUMBER() : precision(0), scale(0), sign(0) {}
};


#define I64(x) x##LL
static const unsigned long long rgval64Power10[] = {
    // powers of 10
    /*1*/ I64(0xa000000000000000),
    /*2*/ I64(0xc800000000000000),
    /*3*/ I64(0xfa00000000000000),
    /*4*/ I64(0x9c40000000000000),
    /*5*/ I64(0xc350000000000000),
    /*6*/ I64(0xf424000000000000),
    /*7*/ I64(0x9896800000000000),
    /*8*/ I64(0xbebc200000000000),
    /*9*/ I64(0xee6b280000000000),
    /*10*/ I64(0x9502f90000000000),
    /*11*/ I64(0xba43b74000000000),
    /*12*/ I64(0xe8d4a51000000000),
    /*13*/ I64(0x9184e72a00000000),
    /*14*/ I64(0xb5e620f480000000),
    /*15*/ I64(0xe35fa931a0000000),

    // powers of 0.1
    /*1*/ I64(0xcccccccccccccccd),
    /*2*/ I64(0xa3d70a3d70a3d70b),
    /*3*/ I64(0x83126e978d4fdf3c),
    /*4*/ I64(0xd1b71758e219652e),
    /*5*/ I64(0xa7c5ac471b478425),
    /*6*/ I64(0x8637bd05af6c69b7),
    /*7*/ I64(0xd6bf94d5e57a42be),
    /*8*/ I64(0xabcc77118461ceff),
    /*9*/ I64(0x89705f4136b4a599),
    /*10*/ I64(0xdbe6fecebdedd5c2),
    /*11*/ I64(0xafebff0bcb24ab02),
    /*12*/ I64(0x8cbccc096f5088cf),
    /*13*/ I64(0xe12e13424bb40e18),
    /*14*/ I64(0xb424dc35095cd813),
    /*15*/ I64(0x901d7cf73ab0acdc),
};

static const signed char rgexp64Power10[] = {
    // exponents for both powers of 10 and 0.1
    /*1*/ 4,
    /*2*/ 7,
    /*3*/ 10,
    /*4*/ 14,
    /*5*/ 17,
    /*6*/ 20,
    /*7*/ 24,
    /*8*/ 27,
    /*9*/ 30,
    /*10*/ 34,
    /*11*/ 37,
    /*12*/ 40,
    /*13*/ 44,
    /*14*/ 47,
    /*15*/ 50,
};

static const unsigned long long rgval64Power10By16[] = {
    // powers of 10^16
    /*1*/ I64(0x8e1bc9bf04000000),
    /*2*/ I64(0x9dc5ada82b70b59e),
    /*3*/ I64(0xaf298d050e4395d6),
    /*4*/ I64(0xc2781f49ffcfa6d4),
    /*5*/ I64(0xd7e77a8f87daf7fa),
    /*6*/ I64(0xefb3ab16c59b14a0),
    /*7*/ I64(0x850fadc09923329c),
    /*8*/ I64(0x93ba47c980e98cde),
    /*9*/ I64(0xa402b9c5a8d3a6e6),
    /*10*/ I64(0xb616a12b7fe617a8),
    /*11*/ I64(0xca28a291859bbf90),
    /*12*/ I64(0xe070f78d39275566),
    /*13*/ I64(0xf92e0c3537826140),
    /*14*/ I64(0x8a5296ffe33cc92c),
    /*15*/ I64(0x9991a6f3d6bf1762),
    /*16*/ I64(0xaa7eebfb9df9de8a),
    /*17*/ I64(0xbd49d14aa79dbc7e),
    /*18*/ I64(0xd226fc195c6a2f88),
    /*19*/ I64(0xe950df20247c83f8),
    /*20*/ I64(0x81842f29f2cce373),
    /*21*/ I64(0x8fcac257558ee4e2),

    // powers of 0.1^16
    /*1*/ I64(0xe69594bec44de160),
    /*2*/ I64(0xcfb11ead453994c3),
    /*3*/ I64(0xbb127c53b17ec165),
    /*4*/ I64(0xa87fea27a539e9b3),
    /*5*/ I64(0x97c560ba6b0919b5),
    /*6*/ I64(0x88b402f7fd7553ab),
    /*7*/ I64(0xf64335bcf065d3a0),
    /*8*/ I64(0xddd0467c64bce4c4),
    /*9*/ I64(0xc7caba6e7c5382ed),
    /*10*/ I64(0xb3f4e093db73a0b7),
    /*11*/ I64(0xa21727db38cb0053),
    /*12*/ I64(0x91ff83775423cc29),
    /*13*/ I64(0x8380dea93da4bc82),
    /*14*/ I64(0xece53cec4a314f00),
    /*15*/ I64(0xd5605fcdcf32e217),
    /*16*/ I64(0xc0314325637a1978),
    /*17*/ I64(0xad1c8eab5ee43ba2),
    /*18*/ I64(0x9becce62836ac5b0),
    /*19*/ I64(0x8c71dcd9ba0b495c),
    /*20*/ I64(0xfd00b89747823938),
    /*21*/ I64(0xe3e27a444d8d991a),
};

static const signed short rgexp64Power10By16[] = {
    // exponents for both powers of 10^16 and 0.1^16
    /*1*/ 54,
    /*2*/ 107,
    /*3*/ 160,
    /*4*/ 213,
    /*5*/ 266,
    /*6*/ 319,
    /*7*/ 373,
    /*8*/ 426,
    /*9*/ 479,
    /*10*/ 532,
    /*11*/ 585,
    /*12*/ 638,
    /*13*/ 691,
    /*14*/ 745,
    /*15*/ 798,
    /*16*/ 851,
    /*17*/ 904,
    /*18*/ 957,
    /*19*/ 1010,
    /*20*/ 1064,
    /*21*/ 1117,
};

static unsigned DigitsToInt(wchar_t* p, int count)
{
    wchar_t* end = p + count;
    unsigned res = *p - '0';
    for ( p = p + 1; p < end; p++) {
        res = 10 * res + *p - '0';
    }
    return res;
}
#define Mul32x32To64(a, b) ((unsigned long long)((unsigned long)(a)) * (unsigned long long)((unsigned long)(b)))

static unsigned long long Mul64Lossy(unsigned long long a, unsigned long long b, int* pexp)
{
    // it's ok to losse some precision here - Mul64 will be called
    // at most twice during the conversion, so the error won't propagate
    // to any of the 53 significant bits of the result
    unsigned long long val = Mul32x32To64(a >> 32, b >> 32) +
        (Mul32x32To64(a >> 32, b) >> 32) +
        (Mul32x32To64(a, b >> 32) >> 32);

    // normalize
    if ((val & I64(0x8000000000000000)) == 0) { val <<= 1; *pexp -= 1; }

    return val;
}

void NumberToDouble(NUMBER* number, double* value)
{
    unsigned long long val;
    int exp;
    wchar_t* src = number->digits;
    int remaining;
    int total;
    int count;
    int scale;
    int absscale;
    int index;

    total = (int)wcslen(src);
    remaining = total;

    // skip the leading zeros
    while (*src == '0') {
        remaining--;
        src++;
    }

    if (remaining == 0) {
        *value = 0;
        goto done;
    }

    count = min(remaining, 9);
    remaining -= count;
    val = DigitsToInt(src, count);

    if (remaining > 0) {
        count = min(remaining, 9);
        remaining -= count;

        // get the denormalized power of 10
        unsigned long mult = (unsigned long)(rgval64Power10[count-1] >> (64 - rgexp64Power10[count-1]));
        val = Mul32x32To64(val, mult) + DigitsToInt(src+9, count);
    }

    scale = number->scale - (total - remaining);
    absscale = abs(scale);
    if (absscale >= 22 * 16) {
        // overflow / underflow
        *(unsigned long long*)value = (scale > 0) ? I64(0x7FF0000000000000) : 0;
        goto done;
    }

    exp = 64;

    // normalize the mantisa
    if ((val & I64(0xFFFFFFFF00000000)) == 0) { val <<= 32; exp -= 32; }
    if ((val & I64(0xFFFF000000000000)) == 0) { val <<= 16; exp -= 16; }
    if ((val & I64(0xFF00000000000000)) == 0) { val <<= 8; exp -= 8; }
    if ((val & I64(0xF000000000000000)) == 0) { val <<= 4; exp -= 4; }
    if ((val & I64(0xC000000000000000)) == 0) { val <<= 2; exp -= 2; }
    if ((val & I64(0x8000000000000000)) == 0) { val <<= 1; exp -= 1; }

    index = absscale & 15;
    if (index) {
        int multexp = rgexp64Power10[index-1];
        // the exponents are shared between the inverted and regular table
        exp += (scale < 0) ? (-multexp + 1) : multexp;

        unsigned long long multval = rgval64Power10[index + ((scale < 0) ? 15 : 0) - 1];
        val = Mul64Lossy(val, multval, &exp);
    }

    index = absscale >> 4;
    if (index) {
        int multexp = rgexp64Power10By16[index-1];
        // the exponents are shared between the inverted and regular table
        exp += (scale < 0) ? (-multexp + 1) : multexp;

        unsigned long long multval = rgval64Power10By16[index + ((scale < 0) ? 21 : 0) - 1];
        val = Mul64Lossy(val, multval, &exp);
    }

    // round & scale down
    if ((unsigned long)val & (1 << 10))
    {
        // IEEE round to even
        unsigned long long tmp = val + ((1 << 10) - 1) + (((unsigned long)val >> 11) & 1);
        if (tmp < val) {
            // overflow
            tmp = (tmp >> 1) | I64(0x8000000000000000);
            exp += 1;
        }
        val = tmp;
    }
    val >>= 11;

    exp += 0x3FE;

    if (exp <= 0) {
        if (exp <= -52) {
            // underflow
            val = 0;
        }
        else {
            // denormalized
            val >>= (-exp+1);
        }
    }
    else
        if (exp >= 0x7FF) {
            // overflow
            val = I64(0x7FF0000000000000);
        }
        else {
            val = ((unsigned long long)exp << 52) + (val & I64(0x000FFFFFFFFFFFFF));
        }

        *(unsigned long long*)value = val;

done:
        if (number->sign) *(unsigned long long*)value |= I64(0x8000000000000000);
}

int main()
{
    NUMBER number;
    number.precision = 15;
    double v = 0.84551240822557006;
    char *src = _ecvt(v, number.precision, &number.scale, &number.sign);
    int truncate = 0;  // change to 1 if you want to truncate
    if (truncate)
    {
        while (*src && src[strlen(src) - 1] == '0')
        {
            src[strlen(src) - 1] = 0;
        }
    }
    wchar_t* dst = number.digits;
    if (*src != '0') {
        while (*src) *dst++ = *src++;
    }
    *dst++ = 0;
    NumberToDouble(&number, &v);
    return 0;
}
user541686
fonte
4
Boa explicação +1. Este código é de shared-source-cli-2.0, certo? Este é o único pensamento que encontrei.
Soner Gönül
10
Devo dizer que é bastante patético. Seqüências de caracteres matematicamente iguais (como uma com zero à direita, ou seja, 2,1e-1 vs. 0,21) devem sempre fornecer resultados idênticos, e seqüências de caracteres matematicamente ordenadas devem fornecer resultados consistentes com a ordem.
gnasher729
4
@ MrLister: Por que "2.1E-1 não deveria ser igual a 0.21 assim"?
user541686
9
@ gnasher729: Concordo um pouco com "2.1e-1" e "0.21" ... mas uma string com zero à direita não é exatamente igual a uma sem - no primeiro, o zero é um dígito significativo e acrescenta precisão.
Chao
4
@cHao: Er ... acrescenta precisão, mas isso afeta apenas como você decide arredondar a resposta final se os sigfigs forem importantes para você, não como o computador deve calcular a resposta final em primeiro lugar. O trabalho do computador é calcular tudo com a maior precisão, independentemente das precisões reais de medição dos números; é problema do programador se ele deseja arredondar o resultado final.
user541686
107

Parece-me que isso é simplesmente um bug. Suas expectativas são inteiramente razoáveis. Eu o reproduzi usando o .NET 4.5.1 (x64), executando o seguinte aplicativo de console que usa minha DoubleConverterclasse. DoubleConverter.ToExactStringmostra o valor exato representado por um double:

using System;

class Test
{
    static void Main()
    {
        double d1 = 0.84551240822557006;
        string s = d1.ToString("r");
        double d2 = double.Parse(s);
        Console.WriteLine(s);
        Console.WriteLine(DoubleConverter.ToExactString(d1));
        Console.WriteLine(DoubleConverter.ToExactString(d2));
        Console.WriteLine(d1 == d2);
    }
}

Resultados no .NET:

0.84551240822557
0.845512408225570055719799711368978023529052734375
0.84551240822556994469749724885332398116588592529296875
False

Resultados no Mono 3.3.0:

0.84551240822557006
0.845512408225570055719799711368978023529052734375
0.845512408225570055719799711368978023529052734375
True

Se você especificar manualmente a seqüência de caracteres de Mono (que contém o "006" no final), o .NET analisará isso de volta ao valor original. Para isso, parece que o problema está no ToString("R")manuseio e não na análise.

Conforme observado em outros comentários, parece que isso é específico para execução no CLR x64. Se você compilar e executar o código acima, segmentando x86, tudo bem:

csc /platform:x86 Test.cs DoubleConverter.cs

... você obtém os mesmos resultados que com o Mono. Seria interessante saber se o bug aparece no RyuJIT - eu não o tenho instalado no momento. Em particular, eu posso imaginar isso possivelmente ser um bug JIT, ou é bem possível que existem inteiros implementações diferentes das partes internas dodouble.ToString baseados na arquitetura.

Sugiro que você registre um bug em http://connect.microsoft.com

Jon Skeet
fonte
1
Então Jon? Para confirmar, isso é um bug no JITer, destacando o ToString()? Como eu tentei substituir o valor codificado com rand.NextDouble()e não houve problema.
Aron19:
1
Sim, definitivamente está na ToString("R")conversão. Experimente ToString("G32")e observe que ele imprime o valor correto.
user541686
1
@ Aron: Não sei dizer se é um bug no JITter ou em uma implementação específica do x64 da BCL. Duvido muito que seja tão simples quanto inlining. Testar com valores aleatórios não ajuda muito, IMO ... Não sei o que você espera que isso demonstre.
Jon Skeet
2
O que está acontecendo, penso, é que o formato "ida e volta" está emitindo um valor 0,498ulp maior do que deveria e a lógica de análise às vezes erroneamente o arredonda a última fração minúscula de uma ulp. Não tenho certeza de qual código culpo mais, pois acho que um formato de "ida e volta" deve gerar um valor numérico que está dentro de um quarto de ULP por ser numericamente correto; analisar a lógica que gera um valor dentro de 0,75ulp do especificado é muito mais fácil do que a lógica que deve produzir um resultado dentro de 0,502ulp do especificado.
Supercat
1
O site de Jon Skeet está fora do ar? Acho tão improvável que estou perdendo toda a fé aqui.
Patrick M
2

Recentemente, estou tentando resolver esse problema . Conforme indicado no código , o double.ToString ("R") tem a seguinte lógica:

  1. Tente converter o dobro em string com precisão de 15.
  2. Converta a string novamente em dobro e compare com o dobro original. Se forem iguais, retornamos a sequência convertida cuja precisão é 15.
  3. Caso contrário, converta o dobro em sequência com precisão de 17.

Nesse caso, double.ToString ("R") escolheu incorretamente o resultado na precisão de 15 para que o erro ocorra. Há uma solução oficial no documento do MSDN:

Em alguns casos, valores duplos formatados com a cadeia de formato numérico padrão "R" não são de ida e volta com êxito se compilados usando as opções / platform: x64 ou / platform: anycpu e executam em sistemas de 64 bits. Para contornar esse problema, você pode formatar valores Double usando a seqüência de formato numérico padrão "G17". O exemplo a seguir usa a string de formato "R" com um valor Double que não faz ida e volta com sucesso e também usa a string de formato "G17" para fazer uma ida e volta com sucesso no valor original.

Portanto, a menos que esse problema seja resolvido, você deve usar double.ToString ("G17") para fazer a ronda.

Atualização : agora há um problema específico para rastrear esse bug.

Jim Ma
fonte