Ist 1.0 eine gültige Ausgabe von std :: generate_canonical?

Ich habe immer gedacht, Zufallszahlen würden zwischen null und eins liegen, ohne1 , dh es handelt sich um Zahlen aus dem halboffenen Intervall [0,1]. Die Dokumentation auf cppreference.com von std::generate_canonicalbestätigt dies.

Wenn ich jedoch das folgende Programm ausführe:

#include <iostream>
#include <limits>
#include <random>

int main()
{
    std::mt19937 rng;

    std::seed_seq sequence{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    rng.seed(sequence);
    rng.discard(12 * 629143 + 6);

    float random = std::generate_canonical<float,
                   std::numeric_limits<float>::digits>(rng);

    if (random == 1.0f)
    {
        std::cout << "Bug!\n";
    }

    return 0;
}

Es gibt mir die folgende Ausgabe:

Bug!

dh es erzeugt mir ein perfektes 1, was Probleme bei meiner MC-Integration verursacht. Ist das ein gültiges Verhalten oder liegt ein Fehler auf meiner Seite vor? Dies ergibt die gleiche Ausgabe mit G ++ 4.7.3

g++ -std=c++11 test.c && ./a.out

und klirren 3.3

clang++ -stdlib=libc++ -std=c++11 test.c && ./a.out

Wie kann ich vermeiden, wenn dies korrekt ist 1?

Edit 1 : G ++ von git scheint unter dem gleichen Problem zu leiden. ich bin on

commit baf369d7a57fb4d0d5897b02549c3517bb8800fd
Date:   Mon Sep 1 08:26:51 2014 +0000

und Kompilieren mit ~/temp/prefix/bin/c++ -std=c++11 -Wl,-rpath,/home/cschwan/temp/prefix/lib64 test.c && ./a.outergibt die gleiche Ausgabe, lddergibt

linux-vdso.so.1 (0x00007fff39d0d000)
libstdc++.so.6 => /home/cschwan/temp/prefix/lib64/libstdc++.so.6 (0x00007f123d785000)
libm.so.6 => /lib64/libm.so.6 (0x000000317ea00000)
libgcc_s.so.1 => /home/cschwan/temp/prefix/lib64/libgcc_s.so.1 (0x00007f123d54e000)
libc.so.6 => /lib64/libc.so.6 (0x000000317e600000)
/lib64/ld-linux-x86-64.so.2 (0x000000317e200000)

Bearbeiten 2 : Ich habe das Verhalten hier gemeldet: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63176

Bearbeiten 3 : Das Clang-Team scheint sich des Problems bewusst zu sein: http://llvm.org/bugs/show_bug.cgi?id=18767

Das Problem liegt in der Zuordnung von der Codomäne von std::mt19937( std::uint_fast32_t) zu float; Der vom Standard beschriebene Algorithmus liefert falsche Ergebnisse (die nicht mit der Beschreibung der Ausgabe des Algorithmus übereinstimmen), wenn ein Genauigkeitsverlust auftritt, wenn der aktuelle IEEE754-Rundungsmodus nicht rund auf negativ bis unendlich ist (beachten Sie, dass der Standardwert rund ist zum nächsten).

Die 7549723-Ausgabe von mt19937 mit Ihrem Startwert ist 4294967257 ( 0xffffffd9u), was, wenn auf 32-Bit-Float gerundet, ergibt 0x1p+32, was dem Maximalwert von mt19937, 4294967295 ( 0xffffffffu) entspricht, wenn dies ebenfalls auf 32-Bit-Float gerundet wird.

Der Standard könnte ein korrektes Verhalten sicherstellen, wenn er spezifiziert, dass beim Konvertieren von der Ausgabe des URNG in die RealTypevon eine generate_canonicalRundung in Richtung einer negativen Unendlichkeit durchgeführt werden soll; Dies würde in diesem Fall zu einem korrekten Ergebnis führen. Als QOI wäre es gut für libstdc ++, diese Änderung vorzunehmen.

Mit dieser Änderung 1.0wird nicht mehr generiert; Stattdessen werden die Grenzwerte 0x1.fffffep-Nfür 0 < N <= 8häufiger generiert (ungefähr 2^(8 - N - 32)pro N, abhängig von der tatsächlichen Verteilung von MT19937).

Ich würde empfehlen , nicht zu verwenden , floatmit std::generate_canonicaldirekt; generiere lieber die Zahl in doubleund runde dann in Richtung negative Unendlichkeit:

    double rd = std::generate_canonical<double,
        std::numeric_limits<float>::digits>(rng);
    float rf = rd;
    if (rf > rd) {
      rf = std::nextafter(rf, -std::numeric_limits<float>::infinity());
    }

Dieses Problem kann auch auftreten bei std::uniform_real_distribution<float>; Die Lösung ist dieselbe, um die Verteilung auf doubledas Ergebnis zu spezialisieren und es auf eine negative Unendlichkeit in zu runden float.

Nach dem Standard 1.0ist nicht gültig.

C ++ 11 §26.5.7.2 Funktionsvorlage generate_canonical

Jede aus der in diesem Abschnitt 26.5.7.2 beschriebenen Vorlage instanziierte Funktion ordnet das Ergebnis eines oder mehrerer Aufrufe eines bereitgestellten Generators gfür einheitliche Zufallszahlen einem Mitglied des angegebenen RealType zu, sodass, wenn die von g _i erzeugten Werte ggleichmäßig verteilt sind, die Die Ergebnisse der Instanziierung t _j , 0 ≤ t _j <1 , sind so gleichmäßig wie möglich verteilt, wie unten angegeben.

Ich bin gerade auf eine ähnliche Frage gestoßen uniform_real_distribution, und hier ist, wie ich den sparsamen Wortlaut des Standards zu diesem Thema interpretiere:

Der Standard definiert mathematische Funktionen immer in Bezug auf Mathematik , niemals in Bezug auf IEEE-Gleitkomma (da der Standard immer noch vorgibt, dass Gleitkomma möglicherweise nicht IEEE-Gleitkomma bedeutet). Jedes Mal, wenn Sie mathematische Formulierungen im Standard sehen, handelt es sich um echte Mathematik , nicht um IEEE.

Der Standard sagt, dass beide uniform_real_distribution<T>(0,1)(g)und generate_canonical<T,1000>(g)Werte im halboffenen Bereich zurückgeben sollten [0,1]. Dies sind jedoch mathematische Werte. Wenn Sie eine reelle Zahl im halboffenen Bereich [0,1] nehmen und sie als IEEE-Gleitkomma darstellen, ist dies ein erheblicher Bruchteil der Zeit, auf die sie aufgerundet wird T(1.0).

Wann Tist float(24 Mantissenbits), erwarten wir uniform_real_distribution<float>(0,1)(g) == 1.0fungefähr 1 in 2 ^ 25 mal. Mein Brute-Force-Experiment mit libc ++ bestätigt diese Erwartung.

template<class F>
void test(long long N, const F& get_a_float) {
    int count = 0;
    for (long long i = 0; i < N; ++i) {
        float f = get_a_float();
        if (f == 1.0f) {
            ++count;
        }
    }
    printf("Expected %d '1.0' results; got %d in practice\n", (int)(N >> 25), count);
}

int main() {
    std::mt19937 g(std::random_device{}());
    auto N = (1uLL << 29);
    test(N, [&g]() { return std::uniform_real_distribution<float>(0,1)(g); });
    test(N, [&g]() { return std::generate_canonical<float, 32>(g); });
}

Beispielausgabe:

Expected 16 '1.0' results; got 19 in practice
Expected 16 '1.0' results; got 11 in practice

Wann Tist double(53 Mantissenbits), erwarten wir uniform_real_distribution<double>(0,1)(g) == 1.0ungefähr 1 in 2 ^ 54 mal. Ich habe nicht die Geduld, diese Erwartung zu testen. :) :)

Mein Verständnis ist, dass dieses Verhalten in Ordnung ist. Es kann unser Gefühl der "halboffenen Fremdheit" verletzen, dass eine Verteilung, die behauptet, Zahlen "kleiner als 1,0" zurückzugeben, tatsächlich Zahlen zurückgeben kann, die gleich sind 1.0; aber das sind zwei verschiedene Bedeutungen von "1.0", sehen Sie? Der erste ist der mathematische 1.0; Die zweite ist die IEEE-Gleitkommazahl mit einfacher Genauigkeit 1.0. Und wir haben jahrzehntelang gelernt, Gleitkommazahlen nicht auf exakte Gleichheit zu vergleichen.

Welchen Algorithmus Sie auch immer in die Zufallszahlen einspeisen, ist egal, ob er manchmal genau wird 1.0. Mit einer Gleitkommazahl können Sie nichts anderes tun als mathematische Operationen. Sobald Sie eine mathematische Operation ausführen, muss sich Ihr Code mit Rundungen befassen. Auch wenn Sie könnten berechtigterweise davon ausgehen , dass generate_canonical<float,1000>(g) != 1.0fSie nach wie vor nicht in der Lage sein , das zu übernehmen generate_canonical<float,1000>(g) + 1.0f != 2.0f- wegen der Rundung. Sie können einfach nicht davon wegkommen; Warum sollten wir in dieser einzigen Instanz so tun, als ob Sie es könnten?