Apakah 1.0 merupakan keluaran yang valid dari std :: generate_canonical?

Saya selalu berpikir bilangan acak akan berada di antara nol dan satu, tanpa1 , yaitu nomor dari interval setengah terbuka [0,1). The dokumentasi pada cppreference.com dari std::generate_canonicalmenegaskan ini.

Namun, ketika saya menjalankan program berikut:

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

Ini memberi saya output berikut:

Bug!

yaitu menghasilkan saya yang sempurna 1, yang menyebabkan masalah dalam integrasi MC saya. Apakah itu perilaku yang valid atau adakah kesalahan di pihak saya? Ini memberikan keluaran yang sama dengan G ++ 4.7.3

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

dan dentang 3.3

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

Jika ini adalah perilaku yang benar, bagaimana saya bisa menghindarinya 1?

Sunting 1 : G ++ dari git tampaknya mengalami masalah yang sama. aku berada

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

dan kompilasi dengan ~/temp/prefix/bin/c++ -std=c++11 -Wl,-rpath,/home/cschwan/temp/prefix/lib64 test.c && ./a.outmemberikan hasil yang sama, lddhasil

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)

Sunting 2 : Saya melaporkan perilaku di sini: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63176

Sunting 3 : Tim dentang tampaknya menyadari masalah ini: http://llvm.org/bugs/show_bug.cgi?id=18767

Masalahnya adalah dalam pemetaan dari codomain dari std::mt19937( std::uint_fast32_t) ke float; algoritma yang dijelaskan oleh standar memberikan hasil yang salah (tidak konsisten dengan deskripsi output dari algoritma) ketika kehilangan presisi terjadi jika mode pembulatan IEEE754 saat ini adalah selain round-to-negative-infinity (perhatikan bahwa defaultnya adalah round -ke-terdekat).

Output 7549723 dari mt19937 dengan seed Anda adalah 4294967257 (0xffffffd9u ), yang jika dibulatkan ke float 32-bit menghasilkan 0x1p+32, yang sama dengan nilai maksimal mt19937, 4294967295 ( 0xffffffffu) ketika itu juga dibulatkan ke float 32-bit.

Standar tersebut dapat memastikan perilaku yang benar jika itu untuk menentukan hal itu ketika mengkonversi dari output URNG ke RealType dari generate_canonical, pembulatan harus dilakukan menuju tak terhingga negatif; ini akan memberikan hasil yang benar dalam kasus ini. Sebagai QOI, sebaiknya libstdc ++ melakukan perubahan ini.

Dengan perubahan ini, 1.0tidak akan dibuat lagi; sebagai gantinya nilai batas 0x1.fffffep-Nuntuk 0 < N <= 8akan dibuat lebih sering (kira-kira2^(8 - N - 32) per N, tergantung pada distribusi aktual MT19937).

Saya akan merekomendasikan untuk tidak menggunakan floatdengan std::generate_canonicallangsung; lebih baik buat angka dalam doubledan kemudian bulatkan menuju tak terhingga negatif:

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

Masalah ini juga bisa terjadi dengan std::uniform_real_distribution<float>; solusinya sama, untuk mengkhususkan distribusi terus doubledan membulatkan hasil menuju negatif tak terhingga dalam float.

Menurut standar, 1.0tidak valid.

C ++ 11 §26.5.7.2 Template fungsi generate_canonical

Setiap fungsi yang dibuat dari template yang dijelaskan dalam bagian ini 26.5.7.2 memetakan hasil dari satu atau lebih pemanggilan generator nomor acak seragam yang disediakan gke salah satu anggota RealType tertentu sehingga, jika nilai g _{i yang} dihasilkan gdidistribusikan secara seragam, Hasil instansiasi t _j , 0 ≤ t _j <1 , didistribusikan seseragam mungkin seperti yang ditentukan di bawah ini.

Saya baru saja menemukan pertanyaan serupa dengan uniform_real_distribution, dan inilah cara saya menafsirkan kata-kata pelit Standar tentang masalah ini:

Standar selalu mendefinisikan fungsi matematika dalam istilah matematika , tidak pernah dalam istilah titik mengambang IEEE (karena Standar masih menganggap bahwa titik mengambang mungkin tidak berarti titik mengambang IEEE). Jadi, setiap kali Anda melihat susunan kata matematika dalam Standar, itu berbicara tentang matematika nyata , bukan IEEE.

Standar mengatakan bahwa keduanya uniform_real_distribution<T>(0,1)(g)dan generate_canonical<T,1000>(g)harus mengembalikan nilai dalam rentang setengah terbuka [0,1). Tapi ini adalah nilai matematis . Saat Anda mengambil bilangan real dalam rentang setengah terbuka [0,1) dan merepresentasikannya sebagai titik mengambang IEEE, yah, sebagian besar waktu bilangan tersebut akan dibulatkan ke atas T(1.0).

When Tis float(24 mantissa bits), kami berharap untuk melihat uniform_real_distribution<float>(0,1)(g) == 1.0fsekitar 1 dalam 2 ^ 25 kali. Eksperimen brute-force saya dengan libc ++ menegaskan harapan ini.

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

Contoh keluaran:

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

When Tis double(53 mantissa bits), kami berharap untuk melihat uniform_real_distribution<double>(0,1)(g) == 1.0sekitar 1 dalam 2 ^ 54 kali. Saya tidak memiliki kesabaran untuk menguji harapan ini. :)

Pemahaman saya adalah bahwa perilaku ini baik-baik saja. Mungkin menyinggung perasaan kita tentang "setengah-rentang-terbuka" bahwa distribusi yang mengklaim mengembalikan angka "kurang dari 1.0" sebenarnya dapat mengembalikan angka yang sama dengan 1.0; tapi itu adalah dua arti yang berbeda dari "1.0", paham? Yang pertama adalah matematika 1.0; yang kedua adalah angka floating-point presisi tunggal IEEE1.0 . Dan kami telah diajarkan selama beberapa dekade untuk tidak membandingkan angka floating-point untuk persamaan yang tepat.

Apa pun algoritme yang Anda masukkan ke dalam angka acak tidak akan peduli jika terkadang benar 1.0. Tidak ada yang bisa Anda lakukan lakukan dengan bilangan floating-point kecuali operasi matematika, dan segera setelah Anda melakukan beberapa operasi matematika, kode Anda harus berurusan dengan pembulatan. Bahkan jika Anda dapat secara sah berasumsi demikian generate_canonical<float,1000>(g) != 1.0f, Anda tetap tidak dapat berasumsi demikian generate_canonical<float,1000>(g) + 1.0f != 2.0f- karena pembulatan. Anda tidak bisa lepas darinya; jadi mengapa kita berpura-pura dalam contoh tunggal ini bahwa Anda bisa?