Angka acak pada C ++

12

Baru-baru ini saya terbiasa dengan bahasa modern yang mencakup generator acak yang bagus, yang biasanya adalah Twister Mersenne; sekarang saya kembali ke C ++ saya harus memutuskan apa yang akan digunakan.

Saya mencari implementasi Mersenne Twister dan saya perhatikan ada begitu banyak: apakah ada yang lebih banyak digunakan dan tersebar luas, atau apakah saya harus memilih satu dengan asumsi semuanya sama-sama bagus?

o0 '.
sumber
1
Saya suka pemisahan bahasa C ++ dan modern.
jcora
2
Mungkin mengatakan "level yang lebih tinggi" lebih tepat.
o0 '.
Saya pikir pertanyaan ini milik stackoverflow
TravisG
5
Pada SO saya akan memberikan jawaban yang berbeda karena saya tidak akan tahu itu untuk mesin permainan sebagai lawan dari, katakanlah, simulasi Monte Carlo untuk terapi medis, di mana kasus tidak memiliki 624 dimensi keacakan dapat mematikan.

Jawaban:

19

C ++ 11 menyertakan generator Mersenne Twister secara default sebagai bagian dari <random>antarmuka barunya . Misalnya, untuk menghasilkan bilangan bulat secara seragam antara [-10, 10] menggunakan MT:

std::mt19937 eng; // This is the Mersenne Twister
std:::uniform_int_distribution<int> dist(-10, 10)
for (int i = 0; i < 10; ++i)
    std::cout << dist(eng) << std::endl;

Sebagian besar ini juga tersedia di setiap kompiler yang menawarkan TR1 meskipun namanya sedikit berbeda; std::tr1::mt19937dan std::tr1::uniform_int<int>.

Saya biasanya memperingatkan orang-orang agar tidak menggunakan Mersenne Twister. Ini algoritma yang oke tapi banyak popularitasnya hanya pemasaran. 624 dimensi keacakan lebih dari yang dibutuhkan kebanyakan orang, dan MT membawa persyaratan negara yang relatif berat dan ketika melakukan recalc tabel penuh, ia dapat meniup cache. Saya pribadi menyukai xorshift yang memberikan periode yang sangat baik dan distribusi yang masuk akal untuk apa pun yang dibutuhkan game, dengan memori kecil dan persyaratan CPU.

Saya telah menulis sebuah generator xorshift yang memenuhi standar C ++ 11-compliant - xorshift.hpp , xorshift.cpp - dan meletakkannya di domain publik. Anda dapat menyambungkan ini ke fungsi pengacakan C ++ 11 apa pun, seperti di atas:

xorshift eng;
std:::uniform_int_distribution<int> dist(-10, 10)
for (int i = 0; i < 10; ++i)
    std::cout << dist(eng) << std::endl;

sumber
5
Ya, itulah jawaban yang saya cari, itu sebabnya saya diposting di sini di gamedev :)
o0 '.
1
Hanya ingin mencatat bahwa tidak ada dalam file yang Anda tautkan menunjukkan bahwa mereka ada dalam domain publik. Cara kerja undang-undang hak cipta, benar-benar perlu ada catatan yang jelas tentang hal itu, karena undang-undang menganggap "semua cadangan hak" secara default. Sebenarnya lebih aman untuk hanya menggunakan sesuatu seperti lisensi MIT atau BSD 2-klausa, karena beberapa yurisdiksi pada dasarnya tidak mengakui "ini dalam domain publik" sebagai mengikat secara hukum. Jika Anda tertarik melihat orang menggunakan kode Anda, mungkin ada baiknya Anda mengurusnya.
Sean Middleditch
1
@ seanmiddleditch: Saya jelas tentang hal itu di sini. Jika Anda menginginkannya di bawah lisensi gaya MIT, saya akan mengikuti petunjuk SQLite dan memberikannya kepada Anda hanya dengan $ 1000.
Kurangnya jika header dalam kode menyatakan sesuatu (yang SQLite tidak, iirc) adalah masalah utama. Jika Anda tidak peduli, itu keren. Hanya memberi Anda saran yang ramah.
Sean Middleditch
1

RNG lain yang pernah saya gunakan sebelumnya untuk tujuan gamedev adalah RNG "kecil" Bob Jenkins, yang dijelaskan di sini .

(Ia juga memiliki RNG kekuatan-kriptografi yang disebut ISAAC, tetapi lebih besar dan lebih lambat, dan game tidak membutuhkan tingkat kekuatan seperti itu.)

Nathan Reed
sumber
1
Itu terlihat lebih mahal daripada xorshift (4 xors dan 3 shift vs 4 add, 6 shift, 2 ors, dan xor), memiliki periode yang lebih buruk, dan menjalankan risiko siklus yang sangat singkat dengan inisialisasi tertentu. Itu terlihat cepat tetapi tidak tercepat; periode oke tapi jauh dari optimal; kualitas distribusi dasar yang sama dengan xorshift; Saya tidak melihat alasan untuk menggunakannya.
Cukup adil. Saya tidak cukup tahu tentang analisis RNG untuk menggali sifat distribusi dan siklus.
Nathan Reed