Warum ist eine Roundtrip-Konvertierung über eine Zeichenfolge für ein Double nicht sicher?

185

Vor kurzem musste ich ein Double in Text serialisieren und es dann zurückbekommen. Der Wert scheint nicht gleichwertig zu sein:

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

Laut MSDN: Standard Numeric Format Strings soll die Option "R" die Sicherheit beim Hin- und Rückflug gewährleisten.

Der Formatbezeichner für den Roundtrip ("R") wird verwendet, um sicherzustellen, dass ein numerischer Wert, der in eine Zeichenfolge konvertiert wird, wieder in denselben numerischen Wert analysiert wird

Warum ist das passiert?

Philip Ding
quelle
6
Ich debuggte in meinem VS und seine Rückkehr hier wahr
Neel
19
Ich habe es reproduziert und falsch zurückgegeben. Sehr interessante Frage.
Jon Skeet
40
.net 4.0 x86 - wahr, .net 4.0 x64 - falsch
Ulugbek Umirov
25
Herzlichen Glückwunsch zum Auffinden eines so beeindruckenden Fehlers in .net.
Aron
14
@ Casperah Round Trip ist speziell dazu gedacht, Gleitkomma-Inkonsistenzen zu vermeiden
Gusdor

Antworten:

178

Ich habe den Fehler gefunden.

.NET führt Folgendes aus 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);

DoubleToNumberist ziemlich einfach - es ruft nur auf _ecvt, was in der C-Laufzeit ist:

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;
    }
}

Es stellt sich heraus, dass _ecvtdie Zeichenfolge zurückgegeben wird 845512408225570.

Beachten Sie die nachfolgende Null? Es stellt sich heraus, dass das den Unterschied macht!
Wenn die Null vorhanden ist, wird das Ergebnis tatsächlich auf0.84551240822557006Ihre ursprüngliche Zahl zurückgeführt. Es wird also gleich verglichen, und daher werden nur 15 Ziffern zurückgegeben.

Wenn ich jedoch die Zeichenfolge bei dieser Null auf kürze 84551240822557, erhalte ich zurück 0.84551240822556994, was nicht Ihre ursprüngliche Nummer ist, und daher würde es 17 Ziffern zurückgeben.

Beweis: Führen Sie den folgenden 64-Bit-Code (von dem ich den größten Teil aus der Microsoft Shared Source CLI 2.0 extrahiert habe) in Ihrem Debugger aus und überprüfen Sie ihn vam Ende von 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
quelle
4
Gute Erklärung +1. Dieser Code stammt von Shared-Source-Cli-2.0, oder? Dies ist der einzige Gedanke, den ich gefunden habe.
Soner Gönül
10
Ich muss sagen, das ist ziemlich erbärmlich. Strings, die mathematisch gleich sind (wie eins mit einer nachgestellten Null oder sagen wir 2.1e-1 vs. 0.21), sollten immer identische Ergebnisse liefern, und Strings, die mathematisch geordnet sind, sollten Ergebnisse liefern, die mit der Reihenfolge übereinstimmen.
Gnasher729
4
@ MrLister: Warum sollte "2.1E-1 nicht einfach so wie 0.21 sein"?
user541686
9
@ gnasher729: Ich würde "2.1e-1" und "0.21" etwas zustimmen ... aber eine Zeichenfolge mit einer nachgestellten Null ist nicht genau gleich eins ohne - in der ersteren ist die Null eine signifikante Ziffer und fügt hinzu Präzision.
CHao
4
@cHao: Äh ... es erhöht die Präzision, aber das wirkt sich nur darauf aus, wie Sie die endgültige Antwort runden, wenn Sigfigs für Sie von Bedeutung sind, und nicht darauf, wie der Computer die endgültige Antwort überhaupt berechnen soll. Die Aufgabe des Computers besteht darin, alles mit höchster Genauigkeit zu berechnen, unabhängig von den tatsächlichen Messgenauigkeiten der Zahlen. Es ist das Problem des Programmierers, wenn er das Endergebnis abrunden möchte.
user541686
107

Es scheint mir, dass dies einfach ein Fehler ist. Ihre Erwartungen sind völlig vernünftig. Ich habe es mit .NET 4.5.1 (x64) reproduziert und die folgende Konsolen-App ausgeführt, die meine DoubleConverterKlasse verwendet. DoubleConverter.ToExactStringzeigt den genauen Wert, dargestellt durch a 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);
    }
}

Ergebnisse in .NET:

0.84551240822557
0.845512408225570055719799711368978023529052734375
0.84551240822556994469749724885332398116588592529296875
False

Ergebnisse in Mono 3.3.0:

0.84551240822557006
0.845512408225570055719799711368978023529052734375
0.845512408225570055719799711368978023529052734375
True

Wenn Sie die Zeichenfolge von Mono (die am Ende "006" enthält) manuell angeben, analysiert .NET diese Zeichenfolge auf den ursprünglichen Wert zurück. Es sieht so aus, als ob das Problem eher in der ToString("R")Handhabung als in der Analyse liegt.

Wie in anderen Kommentaren erwähnt, scheint dies spezifisch für die Ausführung unter der x64-CLR zu sein. Wenn Sie den obigen Code für x86 kompilieren und ausführen, ist dies in Ordnung:

csc /platform:x86 Test.cs DoubleConverter.cs

... Sie erhalten die gleichen Ergebnisse wie mit Mono. Es wäre interessant zu wissen, ob der Fehler unter RyuJIT auftritt - das habe ich momentan selbst nicht installiert. Insbesondere kann ich mir vorstellen, dass dies möglicherweise ein JIT-Fehler ist, oder es ist durchaus möglich, dass es ganz unterschiedliche Implementierungen der double.ToStringauf Architektur basierenden Interna gibt .

Ich schlage vor, Sie melden einen Fehler unter http://connect.microsoft.com

Jon Skeet
quelle
1
Also Jon? Ist dies ein Fehler im JITer, der das bestätigt ToString()? Als ich versuchte, den fest codierten Wert durch zu ersetzen, rand.NextDouble()gab es kein Problem.
Aron
1
Ja, es ist definitiv in der ToString("R")Konvertierung. Versuchen Sie zu ToString("G32")bemerken, dass der richtige Wert gedruckt wird.
user541686
1
@Aron: Ich kann nicht sagen, ob es sich um einen Fehler im JITter oder in einer x64-spezifischen Implementierung der BCL handelt. Ich bezweifle sehr, dass es so einfach ist wie Inlining. Testen mit zufälligen Werten hilft nicht viel, IMO ... Ich bin mir nicht sicher, was Sie davon erwarten.
Jon Skeet
2
Was passiert, denke ich, ist, dass das "Round Trip" -Format einen Wert ausgibt, der 0,498 ulp größer ist als er sein sollte, und die Parsing-Logik rundet ihn manchmal fälschlicherweise auf den letzten winzigen Bruchteil eines ulp. Ich bin mir nicht sicher, welchen Code ich mehr beschuldige, da ich denke, dass ein "Round-Trip" -Format einen numerischen Wert ausgeben sollte, der innerhalb eines Viertel-ULP liegt, um numerisch korrekt zu sein. Das Parsen von Logik, die einen Wert innerhalb von 0,75 μl von dem, was angegeben wurde, ergibt, ist viel einfacher als Logik, die ein Ergebnis innerhalb von 0,502 μl von dem, was angegeben wird, liefern muss.
Supercat
1
Jon Skeets Website ist ausgefallen? Ich finde das so unwahrscheinlich , dass ich ... hier jeglichen Glauben verliere.
Patrick M
2

Vor kurzem versuche ich, dieses Problem zu beheben . Wie im Code hervorgehoben , hat der double.ToString ("R") folgende Logik:

  1. Versuchen Sie, das Double mit einer Genauigkeit von 15 in einen String umzuwandeln.
  2. Konvertieren Sie die Zeichenfolge zurück in double und vergleichen Sie sie mit dem ursprünglichen double. Wenn sie gleich sind, geben wir die konvertierte Zeichenfolge mit einer Genauigkeit von 15 zurück.
  3. Andernfalls konvertieren Sie das Double in einen String mit einer Genauigkeit von 17.

In diesem Fall hat double.ToString ("R") das Ergebnis fälschlicherweise mit einer Genauigkeit von 15 ausgewählt, damit der Fehler auftritt. Es gibt eine offizielle Problemumgehung im MSDN-Dokument:

In einigen Fällen werden Doppelwerte, die mit der numerischen Standardzeichenfolge "R" formatiert sind, nicht erfolgreich umgeleitet, wenn sie mit den Switches / platform: x64 oder / platform: anycpu kompiliert und auf 64-Bit-Systemen ausgeführt werden. Um dieses Problem zu umgehen, können Sie Double-Werte mithilfe der numerischen Standardformatzeichenfolge "G17" formatieren. Im folgenden Beispiel wird die Zeichenfolge im Format "R" mit einem Double-Wert verwendet, der nicht erfolgreich umgeleitet wird, und die Zeichenfolge im Format "G17" wird verwendet, um den ursprünglichen Wert erfolgreich umzurunden.

Wenn dieses Problem nicht behoben ist, müssen Sie double.ToString ("G17") für Roundtrips verwenden.

Update : Jetzt gibt es ein spezielles Problem , um diesen Fehler zu verfolgen.

Jim Ma
quelle