Cara menghasilkan bilangan bulat acak dari dalam suatu rentang

Ini adalah tindak lanjut dari pertanyaan yang diposting sebelumnya:

Bagaimana cara menghasilkan nomor acak di C?

Saya ingin dapat menghasilkan nomor acak dari dalam kisaran tertentu, seperti 1 hingga 6 untuk meniru sisi dadu.

Bagaimana saya akan melakukan ini?

Semua jawaban sejauh ini salah secara matematis. Kembali rand() % Ntidak secara seragam memberikan angka dalam kisaran [0, N)kecuali Nmembagi panjang interval ke mana rand()kembali (yaitu pangkat 2). Selain itu, orang tidak tahu apakah modulusnya rand()independen: mungkin saja mereka pergi 0, 1, 2, ..., yang seragam tetapi tidak terlalu acak. Satu-satunya asumsi yang tampaknya masuk akal untuk dibuat adalah yang rand()mengeluarkan distribusi Poisson: dua subinterval yang tidak tumpang tindih dengan ukuran yang sama kemungkinannya sama dan independen. Untuk sekumpulan nilai yang terbatas, ini menyiratkan distribusi seragam dan juga memastikan bahwa nilairand() tersebar dengan baik.

Ini berarti bahwa satu-satunya cara yang benar untuk mengubah kisaran rand()adalah dengan membaginya ke dalam kotak; misalnya, jika RAND_MAX == 11dan Anda menginginkan rentang 1..6, Anda harus menetapkan {0,1}ke 1,{2,3} ke 2, dan seterusnya. Ini adalah interval yang terputus-putus, berukuran sama dan dengan demikian didistribusikan secara seragam dan independen.

Saran untuk menggunakan pembagian floating-point secara matematis masuk akal tetapi pada prinsipnya menderita masalah pembulatan. Mungkindouble presisi cukup tinggi untuk membuatnya bekerja; mungkin tidak. Saya tidak tahu dan saya tidak ingin memikirkannya; bagaimanapun, jawabannya tergantung pada sistem.

Cara yang benar adalah dengan menggunakan aritmatika integer. Artinya, Anda menginginkan sesuatu seperti berikut:

#include <stdlib.h> // For random(), RAND_MAX

// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
  unsigned long
    // max <= RAND_MAX < ULONG_MAX, so this is okay.
    num_bins = (unsigned long) max + 1,
    num_rand = (unsigned long) RAND_MAX + 1,
    bin_size = num_rand / num_bins,
    defect   = num_rand % num_bins;

  long x;
  do {
   x = random();
  }
  // This is carefully written not to overflow
  while (num_rand - defect <= (unsigned long)x);

  // Truncated division is intentional
  return x/bin_size;
}

Loop diperlukan untuk mendapatkan distribusi seragam yang sempurna. Misalnya, jika Anda diberi nomor acak dari 0 sampai 2 dan Anda hanya menginginkan satu dari 0 sampai 1, Anda terus menarik sampai tidak mendapatkan 2; tidak sulit untuk memastikan bahwa ini memberikan 0 atau 1 dengan probabilitas yang sama. Metode ini juga dijelaskan dalam tautan yang diberikan no pada jawaban mereka, meskipun kode berbeda. Saya menggunakan random()daripada rand()karena memiliki distribusi yang lebih baik (seperti dicatat oleh halaman manual untuk rand()).

Jika Anda ingin mendapatkan nilai acak di luar rentang default [0, RAND_MAX], Anda harus melakukan sesuatu yang rumit. Mungkin yang paling bijaksana adalah untuk mendefinisikan sebuah fungsi random_extended()yang menarik nbit (menggunakan random_at_most()) dan kembali di [0, 2**n), dan kemudian menerapkan random_at_most()dengan random_extended()di tempat random()(dan 2**n - 1di tempat RAND_MAX) untuk menarik nilai acak kurang dari 2**n, dengan asumsi Anda memiliki tipe numerik yang dapat menahan seperti sebuah nilai. Akhirnya, tentu saja, Anda bisa mendapatkan nilai dalam [min, max]menggunakan min + random_at_most(max - min), termasuk nilai negatif.

Mengikuti jawaban @Ryan Reich, saya pikir saya akan menawarkan versi bersih saya. Pemeriksaan batas pertama tidak diperlukan untuk pemeriksaan batas kedua, dan saya telah membuatnya berulang daripada rekursif. Ini mengembalikan nilai dalam rentang [min, max], di mana max >= mindan 1+max-min < RAND_MAX.

unsigned int rand_interval(unsigned int min, unsigned int max)
{
    int r;
    const unsigned int range = 1 + max - min;
    const unsigned int buckets = RAND_MAX / range;
    const unsigned int limit = buckets * range;

    /* Create equal size buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    do
    {
        r = rand();
    } while (r >= limit);

    return min + (r / buckets);
}

Berikut adalah rumus jika Anda mengetahui nilai maks dan min dari suatu rentang, dan Anda ingin menghasilkan angka yang disertakan di antara rentang tersebut:

r = (rand() % (max + 1 - min)) + min

unsigned int
randr(unsigned int min, unsigned int max)
{
       double scaled = (double)rand()/RAND_MAX;

       return (max - min +1)*scaled + min;
}

Lihat di sini untuk opsi lain.

Tidakkah Anda hanya melakukan:

srand(time(NULL));
int r = ( rand() % 6 ) + 1;

%adalah operator modulus. Pada dasarnya itu hanya akan membagi dengan 6 dan mengembalikan sisanya ... dari 0 - 5

Bagi mereka yang memahami masalah bias tetapi tidak tahan dengan waktu proses yang tidak terduga dari metode berbasis penolakan, rangkaian ini menghasilkan bilangan bulat acak yang semakin tidak bias dalam [0, n-1]interval:

r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...

Ia melakukannya dengan mensintesis i * log_2(RAND_MAX + 1)bit acak titik tetap presisi tinggi (di mana ijumlah iterasi) dan melakukan perkalian panjang dengann .

Ketika jumlah bit cukup besar dibandingkan n , biasnya menjadi sangat kecil.

Tidak masalah jika RAND_MAX + 1kurang dari n(seperti dalam pertanyaan ini ), atau jika itu bukan pangkat dua, tetapi kehati-hatian harus dilakukan untuk menghindari luapan bilangan bulat jika RAND_MAX * nbesar.

Untuk menghindari bias modulo (disarankan dalam jawaban lain) Anda selalu dapat menggunakan:

arc4random_uniform(MAX-MIN)+MIN

Dimana "MAX" adalah batas atas dan "MIN" adalah batas bawah. Misalnya, untuk angka antara 10 dan 20:

arc4random_uniform(20-10)+10

arc4random_uniform(10)+10

Solusi sederhana dan lebih baik daripada menggunakan "rand ()% N".

Berikut adalah algoritma yang sedikit lebih sederhana daripada solusi Ryan Reich:

/// Begin and end are *inclusive*; => [begin, end]
uint32_t getRandInterval(uint32_t begin, uint32_t end) {
    uint32_t range = (end - begin) + 1;
    uint32_t limit = ((uint64_t)RAND_MAX + 1) - (((uint64_t)RAND_MAX + 1) % range);

    /* Imagine range-sized buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    uint32_t randVal = rand();
    while (randVal >= limit) randVal = rand();

    /// Return the position you hit in the bucket + begin as random number
    return (randVal % range) + begin;
}

Example (RAND_MAX := 16, begin := 2, end := 7)
    => range := 6  (1 + end - begin)
    => limit := 12 (RAND_MAX + 1) - ((RAND_MAX + 1) % range)

The limit is always a multiple of the range,
so we can split it into range-sized buckets:
    Possible-rand-output: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
    Buckets:             [0, 1, 2, 3, 4, 5][0, 1, 2, 3, 4, 5][X, X, X, X, X]
    Buckets + begin:     [2, 3, 4, 5, 6, 7][2, 3, 4, 5, 6, 7][X, X, X, X, X]

1st call to rand() => 13
    → 13 is not in the bucket-range anymore (>= limit), while-condition is true
        → retry...
2nd call to rand() => 7
    → 7 is in the bucket-range (< limit), while-condition is false
        → Get the corresponding bucket-value 1 (randVal % range) and add begin
    => 3

Meski Ryan benar, solusinya bisa lebih sederhana berdasarkan apa yang diketahui tentang sumber keacakan. Untuk menyatakan kembali masalahnya:

• Ada sumber keacakan, mengeluarkan bilangan bulat dalam kisaran [0, MAX)dengan distribusi seragam.
• Tujuannya adalah untuk menghasilkan bilangan bulat acak yang terdistribusi seragam dalam kisaran [rmin, rmax]mana 0 <= rmin < rmax < MAX.

Menurut pengalaman saya, jika jumlah tempat sampah (atau "kotak") secara signifikan lebih kecil dari kisaran nomor aslinya, dan sumber aslinya kuat secara kriptografis - tidak perlu melalui semua rigamarole itu, dan pembagian modulo sederhana akan cukup (seperti output = rnd.next() % (rmax+1), jika rmin == 0), dan menghasilkan bilangan acak yang didistribusikan secara seragam "cukup", dan tanpa kehilangan kecepatan. Faktor kuncinya adalah sumber keacakan (yaitu, anak-anak, jangan mencobanya di rumah dengan rand()).

Berikut contoh / bukti cara kerjanya dalam praktik. Saya ingin menghasilkan angka acak dari 1 hingga 22, memiliki sumber yang kuat secara kriptografis yang menghasilkan byte acak (berdasarkan Intel RDRAND). Hasilnya adalah:

Rnd distribution test (22 boxes, numbers of entries in each box):     
 1: 409443    4.55%
 2: 408736    4.54%
 3: 408557    4.54%
 4: 409125    4.55%
 5: 408812    4.54%
 6: 409418    4.55%
 7: 408365    4.54%
 8: 407992    4.53%
 9: 409262    4.55%
10: 408112    4.53%
11: 409995    4.56%
12: 409810    4.55%
13: 409638    4.55%
14: 408905    4.54%
15: 408484    4.54%
16: 408211    4.54%
17: 409773    4.55%
18: 409597    4.55%
19: 409727    4.55%
20: 409062    4.55%
21: 409634    4.55%
22: 409342    4.55%   
total: 100.00%

Ini hampir sama dengan seragam yang saya butuhkan untuk tujuan saya (lemparan dadu yang adil, menghasilkan buku kode yang kuat secara kriptografis untuk mesin sandi PD II seperti http://users.telenet.be/d.rijmenants/en/kl-7sim.htm , dll. ). Outputnya tidak menunjukkan bias yang berarti.

Berikut adalah sumber penghasil bilangan acak yang kuat secara kriptografik (benar): Pembangkit Nomor Acak Digital Intel dan kode sampel yang menghasilkan bilangan acak 64-bit (tidak bertanda).

int rdrand64_step(unsigned long long int *therand)
{
  unsigned long long int foo;
  int cf_error_status;

  asm("rdrand %%rax; \
        mov $1,%%edx; \
        cmovae %%rax,%%rdx; \
        mov %%edx,%1; \
        mov %%rax, %0;":"=r"(foo),"=r"(cf_error_status)::"%rax","%rdx");
        *therand = foo;
  return cf_error_status;
}

Saya mengompilasinya di Mac OS X dengan clang-6.0.1 (lurus), dan dengan gcc-4.8.3 menggunakan tanda "-Wa, q" (karena GAS tidak mendukung instruksi baru ini).

Seperti dikatakan sebelumnya, modulo tidak cukup karena mengganggu distribusi. Inilah kode saya yang menutupi bit dan menggunakannya untuk memastikan distribusi tidak miring.

static uint32_t randomInRange(uint32_t a,uint32_t b) {
    uint32_t v;
    uint32_t range;
    uint32_t upper;
    uint32_t lower;
    uint32_t mask;

    if(a == b) {
        return a;
    }

    if(a > b) {
        upper = a;
        lower = b;
    } else {
        upper = b;
        lower = a; 
    }

    range = upper - lower;

    mask = 0;
    //XXX calculate range with log and mask? nah, too lazy :).
    while(1) {
        if(mask >= range) {
            break;
        }
        mask = (mask << 1) | 1;
    }


    while(1) {
        v = rand() & mask;
        if(v <= range) {
            return lower + v;
        }
    }

}

Kode sederhana berikut memungkinkan Anda melihat distribusi:

int main() {

    unsigned long long int i;


    unsigned int n = 10;
    unsigned int numbers[n];


    for (i = 0; i < n; i++) {
        numbers[i] = 0;
    }

    for (i = 0 ; i < 10000000 ; i++){
        uint32_t rand = random_in_range(0,n - 1);
        if(rand >= n){
            printf("bug: rand out of range %u\n",(unsigned int)rand);
            return 1;
        }
        numbers[rand] += 1;
    }

    for(i = 0; i < n; i++) {
        printf("%u: %u\n",i,numbers[i]);
    }

}

Akan mengembalikan angka floating point dalam kisaran [0,1]:

#define rand01() (((double)random())/((double)(RAND_MAX)))