Mengapa C ++ rand () tampaknya hanya menghasilkan angka dari urutan besarnya yang sama?

146

Dalam aplikasi kecil yang ditulis dalam C / C ++, saya menghadapi masalah dengan randfungsi dan mungkin seed:

Saya ingin menghasilkan urutan angka acak yang memiliki urutan berbeda, yaitu dengan nilai logaritma yang berbeda (basis 2). Tetapi tampaknya semua angka yang dihasilkan memiliki urutan yang sama, berfluktuasi hanya antara 2 ^ 25 dan 2 ^ 30.

Apakah karena rand()diunggulkan dengan waktu Unix yang saat ini jumlahnya relatif besar? Apa yang saya lupakan? Saya rand()hanya menyemai sekali di awal main().

c++ c math random Tallaron Mathias
sumber
7
FWIW begitu, apakah itu C atau C ++? Jika dengan C / C ++ berarti Anda benar-benar dapat menggunakan C ++, dan penyebutan C hanya acak, mungkin ini en.cppreference.com/w/cpp/numeric/random/binomial_distribution dapat membantu.
R. Martinho Fernandes
9
Sayangnya Anda bertaruh pada kuda yang salah. Benih seharusnya tidak menjadi masalah Anda. Masalah Anda salah distribusi yang diharapkan. Karena programmer yang tidak memihak akan mengharapkan rand()untuk mengembalikan angka-angka yang terdistribusi secara seragam (dokumentasi dengan peringkat Google tinggi secara eksplisit mengatakan demikian) Saya tidak berpikir pertanyaan ini berguna untuk pembaca masa depan. Itu sebabnya pilihlah, tapi jangan biarkan itu mencegah Anda menggunakan SO.
Kaisar Orionii
12
@ doug65536 "... di mana tidak ada nomor yang pernah diulang" - itu tidak acak! Saya dapat mendanai masa pensiun saya di meja dadu jika dadu rand () saya tidak pernah mengembalikan angka yang sama dua kali hingga setiap angka yang mungkin dikembalikan.
Chris Gregg
6
@ GalacticCowboy Jangan salah mengartikan periodisitas dengan pengulangan angka individual. Dari artikel Wikipedia yang Anda kutip: "hasil berulang tidak menyiratkan bahwa akhir periode telah tercapai, karena keadaan internalnya mungkin lebih besar dari outputnya." Akan sangat, sangat buruk jika PRNG menghasilkan nilai dan kemudian dijamin tidak akan menghasilkan nilai itu lagi sampai semua nilai dikembalikan.
Chris Gregg
12
Doug65536, tidak ada yang berkelahi. Mereka hanya menyatakan dengan benar bahwa Anda salah. PRNG dapat dengan senang hati mengeluarkan hal-hal berikut jika saya menginginkan RAND antara 1 dan 10: 2 4 7 2 8 1 5 9 7 3 Itu akan sepenuhnya valid, meskipun ada banyak 2s dan 7s. Saya pikir Anda membuat PRNG bingung dengan fasilitas shuffle di iPhone Anda.
Bersantai Di Siprus

Jawaban:

479

Hanya ada 3% dari angka antara 1 dan 2 30 yang TIDAK antara 2 25 dan 2 30 . Jadi, ini kedengarannya normal :)

Karena 2 25 /2 30 = 2 -5 = 1/32 = 0,03125 = 3,125%

C4stor
sumber
36
Aye, poin bagus! Ada angka 31 kali lebih banyak antara 2 ^ 25 dan 2 ^ 30 dari antara 1 dan 2 ^ 25 :) terima kasih atas jawaban cepatnya. Saya perlu memikirkan kembali program itu. Pertanyaan dijawab
Tallaron Mathias
1
@ TalaronMathias Pertimbangkan untuk memotong angka melalui >>bitshifting - ini akan memberi Anda angka yang lebih kecil. (Atau mengambil modulus dengan %.)
Sean Allred
13
Saya berharap ini menjadi jelas bagi sebagian besar programmer: Setiap integer unsigned kurang dari 2 ^ 25 harus memiliki 7 bit pertama yang sama dengan 0- dan jika setiap bit acak ...
BlueRaja - Danny Pflughoeft
118
@ BlueRaja-DannyPflughoeft - jika probabilitas jelas, kasino akan gulung tikar.
Brett Hale
26
@ BrettHale - Saya tidak berpikir programmer adalah target demografis kasino.
EkoostikMartin
272

Hijau terang adalah wilayah antara 0 dan 2 25 ; hijau gelap adalah wilayah antara 2 25 dan 2 30 . Kutu adalah kekuatan 2.

distribusi

Casey Chu
sumber
42

Anda harus lebih tepat: Anda menginginkan nilai logaritma basis 2 yang berbeda tetapi distribusi apa yang Anda inginkan untuk ini? Fungsi standar rand () menghasilkan distribusi yang seragam, Anda harus mengubah output ini menggunakan fungsi kuantil yang terkait dengan distribusi yang Anda inginkan.

Jika Anda memberi tahu kami distribusinya maka kami dapat memberi tahu Anda quantilefungsi yang Anda butuhkan.

Batsyeba
sumber
13
+1, distribusi adalah istilah yang sangat penting. Tidaklah masuk akal untuk berbicara tentang angka acak ketika tidak ada yang diketahui tentang distribusinya. Seragam hanyalah kasus khusus, meskipun yang penting. Mungkin menjadi tempat yang baik untuk menunjukkan berbagai distribusi dari perpustakaan standar C ++ 11.
leftaroundtentang
18

Jika Anda ingin berbagai urutan besarnya, mengapa tidak coba saja pow(2, rand())? Atau mungkin memilih pesanan langsung sebagai rand (), seperti yang disarankan Harold?

aspiring_sarge
sumber
3
ide bagus, tetapi Anda harus memperbaiki jawaban Anda menggunakan pow bukan ^ (yang merupakan operator xor logis, bukan kekuatan, dalam bahasa C).
Kriss
6
Karena rand()bisa naik RAND_MAX, Anda benar-benar perlu mengukur nomor acak Anda agar hasilnya tidak melimpah ...
Floris
@ Floris: tetapi jika Anda skala rentang kecil yang dapat dihitung pada rentang yang sangat besar, Anda akan memiliki BANYAK lubang, yang mungkin bukan yang diharapkan OP.
André Caron
13

@ C4stor membuat poin bagus. Tetapi, untuk kasus yang lebih umum dan lebih mudah dipahami untuk manusia (basis 10): untuk rentang dari 1 hingga 10 ^ n, ~ 90% dari angka adalah dari 10 ^ (n-1) hingga 10 ^ n, oleh karena itu, ~ 99% dari angka berubah dari 10 ^ (n-2) menjadi 10 ^ n. Terus tambahkan desimal sebanyak yang Anda inginkan.

Matematika lucu, jika Anda terus melakukan ini untuk n, Anda dapat melihat bahwa dari 1 hingga 10 ^ n, 99,9999 ...% = 100% dari angka berasal dari 10 ^ 0 hingga 10 ^ n dengan metode ini.

Sekarang tentang kode, jika Anda ingin nomor acak dengan urutan acak besarnya, dari 0 hingga 10 ^ n, Anda bisa melakukannya:

  1. Hasilkan angka acak kecil dari 0 hingga n

  2. Jika Anda mengetahui rentang yang dimiliki n, hasilkan sejumlah besar pesanan acak 10 ^ k dengan k> max {n}.

  3. Potong angka acak yang lebih panjang untuk mendapatkan n digit angka acak besar ini.

Francisco Presencia
sumber
46
Anda sepenuhnya benar, tetapi untuk jawaban yang BENAR-BENAR mudah dimengerti, OP harus bertanya pada dirinya sendiri mengapa 90% dari angka acak antara 1 dan 100 adalah dua digit.
Tanyakan Tentang Monica
13

Jawaban dasar (dan benar) sudah diberikan dan diterima di atas: ada 10 angka antara 0 dan 9, 90 angka antara 10 dan 99, 900 antara 100 dan 999, dll.

Untuk cara yang efisien secara komputasi untuk mendapatkan distribusi dengan kira - kira distribusi logaritmik, Anda ingin menggeser-kanan nomor acak Anda dengan nomor acak:

s = rand() & 31; // a random number between 0 and 31 inclusive, assuming RAND_MAX = 2^32-1
r = rand() >> s; // right shift

Ini tidak sempurna, tetapi jauh lebih cepat daripada komputasi pow(2, rand()*scalefactor). Ini akan menjadi "kental" dalam arti bahwa distribusi akan seragam untuk angka dalam faktor 2 (seragam untuk 128 hingga 255, setengah kepadatan untuk 256 hingga 1023, dll).

Berikut adalah histogram dari frekuensi angka 0 hingga 31 (dalam sampel 1M):

masukkan deskripsi gambar di sini

Floris
sumber
nitpick: ini mendorong jumlah yang sangat kecil lebih dari yang mungkin diharapkan.
Peluang
Yah - intinya adalah untuk mendorong jumlah kecil, jadi saya senang itu berhasil! Saya menjalankan simulasi Monte Carlo, dan ini memberi saya faktor 2 penurunan probabilitas sebagai angka ganda - tidak seperti distribusi log. Jawaban diperbarui dengan gambar.
Floris
tidak, maksud saya, dengan rand()>>(rand()&31);, orang akan secara intuitif mengharapkan 1/32 dari angka-angka itu memiliki 32 bit, dan 1/32 dari angka-angka itu memiliki 31 bit, dan 1/32 dari angka-angka itu memiliki 30 bit, dll. Tapi itu bukan hasil yang Anda dapatkan, hanya sekitar 1/64 dari angka akan menghasilkan 32 bit, sementara hampir setengahnya harus 0. Karena matematika mental saya tidak setuju dengan pengukuran Anda, saya harus melakukan pengukuran sendiri untuk mencari ini keluar.
Mooing Duck
2
Saya tidak bermaksud mengatakan bahwa kode Anda salah. Mungkin itu yang akan saya lakukan. Itu hanya layak peringatan bahwa hasilnya tidak cukup didistribusikan seperti yang diharapkan.
Mooing Duck
1
Saya pikir masalahnya berasal dari memikirkan 0 sebagai angka 1 bit ... itulah jenis teka-teki yang Anda hadapi ketika Anda mencampur bilangan bulat dan logaritma. Ini merupakan latihan yang bagus dan Anda memberi saya sesuatu untuk dipikirkan. "Uji batas algoritme Anda" - tidak pernah menjadi tua.
Floris
5

Ada jumlah angka yang sama persis antara 0 dan 2 ^ 29 dan 2 ^ 29 dan 2 ^ 30.

Cara lain untuk melihat masalah: pertimbangkan representasi biner dari angka acak yang Anda hasilkan, probabilitas bahwa bit tertinggi adalah 1 sama dengan 1/2, dan, karena itu, Anda mendapatkan pesanan 29 dalam setengah kasus. Yang Anda inginkan adalah melihat angka yang di bawah 2 ^ 25, tetapi itu berarti 5 bit tertinggi semuanya nol, yang terjadi dengan probabilitas rendah 1/32. Kemungkinannya adalah bahwa bahkan jika Anda menjalankannya untuk waktu yang lama Anda tidak akan pernah melihat urutan di bawah 15 sama sekali (kemungkinannya adalah seperti menggulung 6 6 kali berturut-turut).

Sekarang, bagian dari pertanyaan Anda tentang benih. Tidak, seed tidak dapat menentukan rentang angka yang dihasilkan, hanya menentukan elemen awal pertama. Pikirkan rand () sebagai urutan semua angka yang mungkin ada dalam kisaran (permutasi yang telah ditentukan). Benih menentukan di mana Anda mulai menggambar angka dari urutan. Inilah mengapa jika Anda ingin keacakan (semu), Anda menggunakan waktu saat ini untuk menginisialisasi urutan: Anda tidak peduli bahwa posisi yang Anda mulai tidak terdistribusi secara seragam, yang penting adalah Anda tidak pernah memulai dari posisi yang sama.

Vadim
sumber
2

menggunakannya pow(2,rand()) akan memberikan jawaban dalam urutan besarnya yang diinginkan !!

Shivendra
sumber
2

Jika Anda ingin menggunakan nomor acak dari layanan online yang dapat Anda gunakan wget untuk itu, Anda mungkin ingin melihat Anda juga dapat menggunakan layanan seperti random.org untuk pembuatan nomor acak Anda, Anda dapat menangkapnya menggunakan wget dan kemudian membaca angka dari file yang diunduh 

wget -q https://www.random.org/integers/?num=100&min=1&max=100&col=5&base=10&format=html&rnd=new -O new.txt

http://programmingconsole.blogspot.in/2013/11/a-better-and-different-way-to-generate.html

Namit Sinha
sumber
Selamat datang di SO. tolong jangan memposting tautan sebagai jawaban. Anda dapat memberikan sketsa terperinci dari jawaban yang meninggalkan detail untuk dibaca melalui tautan.
Shai