GNU/Linux >> Belajar Linux >  >> Linux

Mengapa rand() mengulang angka jauh lebih sering di Linux daripada Mac?

MacOS menyediakan fungsi rand() yang tidak berdokumen di stdlib. Jika Anda membiarkannya tidak diunggulkan, maka nilai pertama yang dihasilkannya adalah 16807, 282475249, 1622650073, 984943658, dan 1144108930. Pencarian cepat akan menunjukkan bahwa urutan ini sesuai dengan generator bilangan acak LCG yang sangat mendasar yang mengiterasi rumus berikut:

x n +1 =7 · x n (mod 2 − 1)

Karena keadaan RNG ini dijelaskan seluruhnya oleh nilai bilangan bulat 32-bit tunggal, periodenya tidak terlalu lama. Tepatnya, ini berulang setiap 2 − 2 iterasi, mengeluarkan setiap nilai dari 1 hingga 2 − 2.

Saya rasa tidak ada standar implementasi rand() untuk semua versi Linux, namun ada fungsi glibc rand() yang sering digunakan. Alih-alih satu variabel status 32-bit, ini menggunakan kumpulan lebih dari 1000 bit, yang untuk semua maksud dan tujuan tidak akan pernah menghasilkan urutan yang berulang sepenuhnya. Sekali lagi, Anda mungkin dapat mengetahui versi apa yang Anda miliki dengan mencetak beberapa keluaran pertama dari RNG ini tanpa menyemainya terlebih dahulu. (Fungsi glibc rand() menghasilkan angka 1804289383, 846930886, 1681692777, 1714636915, dan 1957747793.)

Jadi alasan Anda mendapatkan lebih banyak tabrakan di Linux (dan hampir tidak ada di MacOS) adalah karena versi Linux dari rand() pada dasarnya lebih acak.


Meskipun pada awalnya mungkin terdengar seperti macOS rand() entah bagaimana lebih baik untuk tidak mengulangi angka apa pun, perlu dicatat bahwa dengan jumlah angka yang dihasilkan ini diharapkan akan melihat banyak duplikat (sebenarnya, sekitar 790 juta, atau (2-1)/e ). Demikian pula iterasi melalui angka secara berurutan juga tidak akan menghasilkan duplikat, tetapi tidak akan dianggap sangat acak. Jadi rand() Linux penerapannya dalam pengujian ini tidak dapat dibedakan dari sumber acak sebenarnya, sedangkan macOS rand() tidak.

Hal lain yang tampak mengejutkan pada pandangan pertama adalah bagaimana macOS rand() dapat mengelola untuk menghindari duplikat dengan baik. Melihat kode sumbernya, kami menemukan penerapannya sebagai berikut:

/*
 * Compute x = (7^5 * x) mod (2^31 - 1)
 * without overflowing 31 bits:
 *      (2^31 - 1) = 127773 * (7^5) + 2836
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
    long hi, lo, x;

    /* Can't be initialized with 0, so use another value. */
    if (*ctx == 0)
        *ctx = 123459876;
    hi = *ctx / 127773;
    lo = *ctx % 127773;
    x = 16807 * lo - 2836 * hi;
    if (x < 0)
        x += 0x7fffffff;
    return ((*ctx = x) % ((unsigned long) RAND_MAX + 1));

Ini memang menghasilkan semua angka antara 1 dan RAND_MAX , inklusif, tepat satu kali, sebelum urutan berulang lagi. Karena keadaan berikutnya didasarkan pada perkalian, keadaan tidak akan pernah menjadi nol (atau semua keadaan di masa depan juga akan menjadi nol). Jadi angka berulang yang Anda lihat adalah yang pertama, dan nol adalah angka yang tidak pernah dikembalikan.

Apple telah mempromosikan penggunaan generator angka acak yang lebih baik dalam dokumentasi dan contoh mereka setidaknya selama macOS (atau OS X) ada, sehingga kualitas rand() mungkin tidak dianggap penting, dan mereka hanya terjebak dengan salah satu generator pseudorandom paling sederhana yang tersedia. (Seperti yang Anda catat, rand() mereka bahkan dikomentari dengan rekomendasi untuk menggunakan arc4random() sebagai gantinya.)

Pada catatan terkait, generator nomor pseudorandom paling sederhana yang dapat saya temukan yang menghasilkan hasil yang layak dalam tes ini (dan banyak lainnya) untuk keacakan adalah xorshift*:

uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;

Implementasi ini menghasilkan hampir persis 790 juta duplikat dalam pengujian Anda.


rand() didefinisikan oleh standar C, dan standar C tidak menentukan algoritma mana yang akan digunakan. Jelas, Apple menggunakan algoritme yang lebih rendah daripada implementasi GNU/Linux Anda:Linux tidak dapat dibedakan dari sumber acak sebenarnya dalam pengujian Anda, sedangkan implementasi Apple hanya mengacak-acak angkanya.

Jika Anda menginginkan angka acak dengan kualitas apa pun, gunakan PRNG yang lebih baik yang memberikan setidaknya beberapa jaminan pada kualitas angka yang dikembalikan, atau cukup baca dari /dev/urandom atau serupa. Yang terakhir memberi Anda angka kualitas kriptografi, tetapi lambat. Bahkan jika terlalu lambat dengan sendirinya, /dev/urandom dapat memberikan beberapa benih unggul ke PRNG lain yang lebih cepat.


Secara umum, pasangan rand/srand telah dianggap agak usang untuk waktu yang lama karena bit orde rendah menampilkan lebih sedikit keacakan daripada bit orde tinggi dalam hasil. Ini mungkin atau mungkin tidak ada hubungannya dengan hasil Anda, tetapi saya pikir ini masih merupakan kesempatan yang baik untuk mengingat bahwa meskipun beberapa implementasi rand/srand sekarang lebih mutakhir, implementasi yang lebih lama tetap ada dan lebih baik menggunakan acak (3 ). Di kotak Arch Linux saya, catatan berikut masih ada di halaman manual untuk rand(3):

  The versions of rand() and srand() in the Linux C Library use the  same
   random number generator as random(3) and srandom(3), so the lower-order
   bits should be as random as the higher-order bits.  However,  on  older
   rand()  implementations,  and  on  current implementations on different
   systems, the lower-order bits are much less random than the  higher-or-
   der bits.  Do not use this function in applications intended to be por-
   table when good randomness is needed.  (Use random(3) instead.)

Tepat di bawah itu, halaman manual sebenarnya memberikan contoh implementasi rand dan srand yang sangat singkat dan sangat sederhana tentang LC RNG paling sederhana yang pernah Anda lihat dan memiliki RAND_MAX kecil. Saya tidak berpikir mereka cocok dengan apa yang ada di pustaka standar C, jika pernah. Atau setidaknya saya harap tidak.

Secara umum, jika Anda akan menggunakan sesuatu dari pustaka standar, gunakan acak jika Anda bisa (halaman manual mencantumkannya sebagai standar POSIX kembali ke POSIX.1-2001, tetapi rand adalah cara standar sebelum C bahkan dibakukan) . Atau lebih baik lagi, buka Numerical Recipes (atau cari online) atau Knuth dan implementasikan. Mereka sangat mudah dan Anda hanya perlu melakukannya sekali untuk memiliki RNG tujuan umum dengan atribut yang paling sering Anda butuhkan dan yang kualitasnya diketahui.


Linux
  1. Mengapa saya beralih dari Mac ke Linux

  2. Mengapa saya beralih dari Mac ke Linux

  3. Kisah Linux Saya:Mengapa orang mengenalkan Raspberry Pi

  1. Apa itu POSIX? Mengapa Penting bagi Pengguna Linux/UNIX?

  2. Linux – Mengapa Linux Menampilkan Memori Lebih Banyak Dan Lebih Sedikit Daripada Yang Saya Instal Secara Fisik?

  3. Df Mengatakan Saya Memiliki 20g Lebih Banyak Ruang Disk yang Digunakan Daripada Du. Mengapa??

  1. Linux – Mengapa Setuid Tidak Bekerja??

  2. Linux – Mengapa Es_mx Lokal Bekerja Tapi Tidak Es?

  3. Mengapa Linux menggunakan partisi swap daripada file?