Menghasilkan bilangan bulat acak dari suatu rentang

Saya membutuhkan fungsi yang akan menghasilkan bilangan bulat acak dalam rentang yang diberikan (termasuk nilai batas). Saya tidak persyaratan kualitas / keacakan yang tidak masuk akal, saya memiliki empat persyaratan:

• Saya perlu cepat. Proyek saya perlu menghasilkan jutaan (atau kadang-kadang bahkan puluhan juta) angka acak dan fungsi generator saya saat ini telah terbukti menjadi hambatan.
• Saya membutuhkannya agar seragam (penggunaan rand () baik-baik saja).
• rentang min-max bisa apa saja dari <0, 1> hingga <-32727, 32727>.
• itu harus ditaburkan.

Saat ini saya memiliki kode C ++ berikut:

output = min + (rand() * (int)(max - min) / RAND_MAX)

Masalahnya adalah, itu tidak benar-benar seragam - maks dikembalikan hanya ketika rand () = RAND_MAX (untuk Visual C ++ itu 1/32727). Ini adalah masalah utama untuk rentang kecil seperti <-1, 1>, di mana nilai terakhir hampir tidak pernah dikembalikan.

Jadi saya mengambil pena dan kertas dan menghasilkan formula berikut (yang dibangun di atas (int) (n + 0,5) trik pembulatan bilangan bulat):

Tapi itu masih tidak memberi saya distribusi seragam. Berjalan berulang dengan 10.000 sampel memberi saya rasio 37:50:13 untuk nilai nilai -1, 0. 1.

Bisakah Anda menyarankan formula yang lebih baik? (atau bahkan seluruh fungsi generator nomor pseudo-acak)

Solusi cepat, agak lebih baik dari milik Anda, tetapi masih belum terdistribusi dengan benar

output = min + (rand() % static_cast<int>(max - min + 1))

Kecuali ketika ukuran kisaran adalah kekuatan 2, metode ini menghasilkan angka terdistribusi tidak bias yang bias terlepas dari kualitas rand(). Untuk uji komprehensif kualitas metode ini, baca ini .

Jawaban C ++ yang paling sederhana (dan karenanya terbaik) (menggunakan standar 2011) adalah

#include <random>

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

Tidak perlu menemukan kembali roda. Tidak perlu khawatir tentang bias. Tidak perlu khawatir menggunakan waktu sebagai benih acak.

Jika kompiler Anda mendukung C ++ 0x dan menggunakannya adalah opsi untuk Anda, maka <random>tajuk standar baru cenderung memenuhi kebutuhan Anda. Ini memiliki kualitas tinggi uniform_int_distributionyang akan menerima batas minimum dan maksimum (termasuk yang Anda butuhkan), dan Anda dapat memilih di antara berbagai generator angka acak untuk dihubungkan ke distribusi itu.

Berikut adalah kode yang menghasilkan sejuta acak yang intdidistribusikan secara seragam di [-57, 365]. Saya telah menggunakan <chrono>fasilitas std baru untuk mengukur waktu seperti yang Anda sebutkan kinerja adalah perhatian utama bagi Anda.

#include <iostream>
#include <random>
#include <chrono>

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    Clock::time_point t0 = Clock::now();
    const int N = 10000000;
    typedef std::minstd_rand G;
    G g;
    typedef std::uniform_int_distribution<> D;
    D d(-57, 365);
    int c = 0;
    for (int i = 0; i < N; ++i) 
        c += d(g);
    Clock::time_point t1 = Clock::now();
    std::cout << N/sec(t1-t0).count() << " random numbers per second.\n";
    return c;
}

Bagi saya (2,8 GHz Intel Core i5) ini mencetak:

2.10268e + 07 angka acak per detik.

Anda dapat menyemai generator dengan memasukkan int ke konstruktornya:

    G g(seed);

Jika nanti Anda menemukan bahwa intitu tidak mencakup rentang yang Anda butuhkan untuk distribusi Anda, ini dapat diperbaiki dengan mengubah uniform_int_distributionseperti itu (misalnya ke long long):

    typedef std::uniform_int_distribution<long long> D;

Jika nanti Anda menemukan bahwa minstd_randgenerator itu tidak berkualitas cukup tinggi, itu juga dapat dengan mudah diganti. Misalnya:

    typedef std::mt19937 G;  // Now using mersenne_twister_engine

Memiliki kontrol terpisah atas generator angka acak, dan distribusi acak bisa sangat membebaskan.

Saya juga telah menghitung (tidak ditampilkan) 4 "momen" pertama dari distribusi ini (menggunakan minstd_rand) dan membandingkannya dengan nilai-nilai teoritis dalam upaya untuk mengukur kualitas distribusi:

min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001

( x_Awalan mengacu pada "yang diharapkan")

Mari kita bagi masalah menjadi dua bagian:

• Hasilkan nomor acak n dalam rentang 0 hingga (maks-mnt).
• Tambahkan min ke nomor itu

Bagian pertama jelas yang paling sulit. Mari kita asumsikan bahwa nilai pengembalian rand () sangat seragam. Menggunakan modulo akan menambah bias ke (RAND_MAX + 1) % (max-min+1)angka pertama . Jadi jika kita secara ajaib bisa berubah RAND_MAXmenjadiRAND_MAX - (RAND_MAX + 1) % (max-min+1) , tidak ada lagi akan bias.

Ternyata kita dapat menggunakan intuisi ini jika kita bersedia mengizinkan pseudo-nondeterminisme ke dalam waktu berjalan dari algoritma kita. Setiap kali rand () mengembalikan nomor yang terlalu besar, kami cukup meminta nomor acak lain sampai kami mendapatkan nomor yang cukup kecil.

Waktu berjalan sekarang didistribusikan secara geometris , dengan nilai yang diharapkan di 1/pmana pprobabilitas mendapatkan angka yang cukup kecil pada percobaan pertama. Karena RAND_MAX - (RAND_MAX + 1) % (max-min+1)selalu kurang dari (RAND_MAX + 1) / 2, kita tahu itu p > 1/2, sehingga jumlah iterasi yang diharapkan akan selalu kurang dari dua untuk rentang apa pun. Seharusnya dimungkinkan untuk menghasilkan puluhan juta angka acak dalam waktu kurang dari satu detik pada CPU standar dengan teknik ini.

EDIT:

Meskipun hal di atas secara teknis benar, jawaban DSimon mungkin lebih berguna dalam praktiknya. Anda seharusnya tidak menerapkan hal ini sendiri. Saya telah melihat banyak implementasi dari sampel penolakan dan seringkali sangat sulit untuk melihat apakah itu benar atau tidak.

Bagaimana dengan Twister Mersenne ? Implementasi boost agak mudah digunakan dan diuji dengan baik di banyak aplikasi dunia nyata. Saya telah menggunakannya sendiri di beberapa proyek akademik seperti kecerdasan buatan dan algoritma evolusi.

Inilah contoh mereka di mana mereka membuat fungsi sederhana untuk menggulung dadu enam sisi:

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

boost::mt19937 gen;

int roll_die() {
    boost::uniform_int<> dist(1, 6);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
    return die();
}

Oh, dan inilah beberapa mucikari dari generator ini kalau-kalau Anda tidak yakin Anda harus menggunakannya pada yang jauh lebih rendah rand():

The Mersenne Twister adalah generator "angka acak" yang ditemukan oleh Makoto Matsumoto dan Takuji Nishimura; situs web mereka mencakup banyak implementasi algoritma.

Pada dasarnya, Mersenne Twister adalah register geser linier-umpan balik yang sangat besar. Algoritma ini beroperasi pada seed 19.937 bit, disimpan dalam array 624 elemen dari integer 32-bit unsigned. Nilai 2 ^ 19937-1 adalah prime Mersenne; teknik untuk memanipulasi benih didasarkan pada algoritma "memutar" yang lebih tua - maka nama "Mersenne Twister".

Aspek menarik dari Mersenne Twister adalah penggunaan operasi biner - yang bertentangan dengan penggandaan yang memakan waktu - untuk menghasilkan angka. Algoritma juga memiliki periode yang sangat panjang, dan granularity yang baik. Ini cepat dan efektif untuk aplikasi non-kriptografi.

int RandU(int nMin, int nMax)
{
    return nMin + (int)((double)rand() / (RAND_MAX+1) * (nMax-nMin+1));
}

Ini adalah pemetaan 32768 integer ke (nMax-nMin + 1) integer. Pemetaan akan cukup baik jika (nMax-nMin + 1) kecil (seperti dalam kebutuhan Anda). Perhatikan bahwa jika (nMax-nMin + 1) besar, pemetaan tidak akan berfungsi (Misalnya - Anda tidak dapat memetakan 32768 nilai ke nilai 30000 dengan probabilitas sama). Jika rentang tersebut diperlukan - Anda harus menggunakan sumber acak 32-bit atau 64-bit, alih-alih hasil rand 15-bit (), atau abaikan rand () yang berada di luar jangkauan.

Ini adalah versi yang tidak bias yang menghasilkan angka di [low, high]:

int r;
do {
  r = rand();
} while (r < ((unsigned int)(RAND_MAX) + 1) % (high + 1 - low));
return r % (high + 1 - low) + low;

Jika rentang Anda cukup kecil, tidak ada alasan untuk menembolok sisi kanan perbandingan di doloop.

Saya merekomendasikan perpustakaan Boost.Random , sangat rinci dan terdokumentasi dengan baik, memungkinkan Anda menentukan secara spesifik distribusi apa yang Anda inginkan, dan dalam skenario non-kriptografi sebenarnya dapat mengungguli implementasi rand C library yang khas.

anggap min dan maks adalah nilai int, [dan] berarti sertakan nilai ini, (dan) berarti tidak termasuk nilai ini, gunakan di atas untuk mendapatkan nilai yang tepat menggunakan c ++ rand ()

referensi: untuk () mendefinisikan], kunjungi:

https://en.wikipedia.org/wiki/Interval_(mathematics)

untuk fungsi rand dan srand atau yang ditentukan RAND_MAX, kunjungi:

http://en.cppreference.com/w/cpp/numeric/random/rand

[min, maks]

int randNum = rand() % (max - min + 1) + min

(minimum, maks)

int randNum = rand() % (max - min) + min + 1

[min, maks)

int randNum = rand() % (max - min) + min

(minimum, maks)

int randNum = rand() % (max - min - 1) + min + 1

Dalam thread penolakan sampel ini sudah dibahas, tetapi saya ingin menyarankan satu optimasi berdasarkan fakta yang rand() % 2^somethingtidak menimbulkan bias seperti yang telah disebutkan di atas.

Algoritma ini sangat sederhana:

• menghitung kekuatan terkecil 2 lebih besar dari panjang interval
• acak satu nomor dalam interval "baru" itu
• mengembalikan nomor itu jika kurang dari panjang interval asli
  • tolak sebaliknya

Ini kode contoh saya:

int randInInterval(int min, int max) {
    int intervalLen = max - min + 1;
    //now calculate the smallest power of 2 that is >= than `intervalLen`
    int ceilingPowerOf2 = pow(2, ceil(log2(intervalLen)));

    int randomNumber = rand() % ceilingPowerOf2; //this is "as uniform as rand()"

    if (randomNumber < intervalLen)
        return min + randomNumber;      //ok!
    return randInInterval(min, max);    //reject sample and try again
} 

Ini bekerja dengan baik terutama untuk interval kecil, karena kekuatan 2 akan "lebih dekat" dengan panjang interval nyata, sehingga jumlah kesalahan akan lebih kecil.

PS
Jelas menghindari rekursi akan lebih efisien (tidak perlu menghitung berulang-ulang log plafon ..) tapi saya pikir itu lebih mudah dibaca untuk contoh ini.

Perhatikan bahwa dalam sebagian besar saran, nilai acak awal yang Anda dapatkan dari fungsi rand (), yang biasanya dari 0 hingga RAND_MAX, terbuang sia-sia. Anda hanya membuat satu angka acak, sementara ada prosedur suara yang bisa memberi Anda lebih banyak.

Asumsikan bahwa Anda menginginkan wilayah [min, maks] angka bilangan bulat acak. Kita mulai dari [0, maks-mnt]

Ambil basis b = maks-min + 1

Mulai dari mewakili angka yang Anda dapatkan dari rand () di pangkalan b.

Dengan cara itu Anda mendapatkan lantai (log (b, RAND_MAX)) karena setiap digit dalam basis b, kecuali mungkin yang terakhir, mewakili angka acak dalam kisaran [0, maks-mnt].

Tentu saja perubahan terakhir ke [min, maks] sederhana untuk setiap angka acak r + min.

int n = NUM_DIGIT-1;
while(n >= 0)
{
    r[n] = res % b;
    res -= r[n];
    res /= b;
    n--;
}

Jika NUM_DIGIT adalah jumlah digit dalam basis b yang dapat Anda ekstrak dan itu

NUM_DIGIT = floor(log(b,RAND_MAX))

maka yang di atas adalah sebagai implementasi sederhana mengekstraksi NUM_DIGIT angka acak dari 0 ke b-1 dari satu RAND_MAX nomor acak yang menyediakan b <RAND_MAX.

Rumus untuk ini sangat sederhana, jadi coba ungkapan ini,

 int num = (int) rand() % (max - min) + min;  
 //Where rand() returns a random number between 0.0 and 1.0

Ungkapan berikut harus tidak bias jika saya tidak salah:

std::floor( ( max - min + 1.0 ) * rand() ) + min;

Saya berasumsi di sini bahwa rand () memberi Anda nilai acak dalam kisaran antara 0,0 dan 1,0 TIDAK termasuk 1,0 dan bahwa max dan min adalah bilangan bulat dengan kondisi bahwa min <max.