Dapatkah generator bilangan acak pernah menghasilkan output yang berbeda dengan biji yang identik?

10

Judul itu merangkumnya. Saya tertarik untuk mengetahui apakah ada algoritma yang mampu menghasilkan output variabel yang diberi input identik tanpa bergantung pada sumber lain untuk keacakan seperti DateTime. Sekarang atau angka yang dihasilkan dari sensor cahaya dll. Selain itu, algoritma tidak dapat dijalankan secara berurutan, hanya dua run yang berbeda dan tidak terkait yang menghasilkan output yang berbeda.

random ConditionRacer
sumber
Apa yang Anda bicarakan adalah generator pseud-random-number, lebih spesifik.
Marcel
Sebagian besar bahasa memungkinkan kemungkinan instantiating generator angka acak tanpa harus menentukan benih sehingga benih juga "acak". Ada alasan mengapa biji digunakan.
Neil
1
@Neil: dalam kasus-kasus itu, masih ada seed, hanya implisit, biasanya waktu sistem.
Michael Borgwardt
@MichaelBorgwardt, saya hanya mengatakan bahwa benihnya akan acak juga. Tentu saja tidak ada yang benar-benar acak, tetapi biasanya waktu sistem menyediakan benih yang layak, asalkan Anda tidak sering membuat generator angka acak tanpa melewati benih, dalam hal ini Anda mungkin mendapatkan benih "acak" yang sama dua kali.
Neil
Ada bidang penelitian yang menarik ke dalam perangkat keras yang tidak eksak, yang secara statistik tidak akurat. Manfaat potensial adalah penggunaan daya yang lebih rendah. Hanya menghitung 2.0 + 2.0pada sistem seperti itu tidak akan memberikan hasil yang identik. Tidak perlu sumber keacakan lain.
MSalters

Jawaban:

15

Saya tertarik untuk mengetahui apakah ada algoritma yang mampu menghasilkan output variabel yang diberi input identik tanpa bergantung pada sumber lain untuk keacakan seperti DateTime. Sekarang atau angka yang dihasilkan dari sensor cahaya dll.

Tidak, itu pada dasarnya tidak mungkin, karena definisi utama dari suatu algoritma adalah bahwa itu didefinisikan dengan baik dan deterministik, yaitu diberi input yang sama akan selalu menghasilkan output yang sama. Ada algoritma acak, tetapi mereka membutuhkan keacakan sebagai input.

Selain itu, determinisme adalah yang tujuan desain yang paling penting dari perangkat keras komputer. CPU yang tidak menghasilkan output yang sama dengan input yang sama akan sama sekali tidak berguna untuk sebagian besar tujuan.

Michael Borgwardt
sumber
14

Tidak, algoritma pembuatan angka pseudo-acak akan selalu menghasilkan output yang sama dengan seed yang sama (maka pseudo -random).

Saya merasa menarik bahwa Anda menggunakan istilah, "algoritma" daripada "program." Ini tidak termasuk kelas tertentu dari jawaban ya (kesalahan lunak dalam RAM, interleaving utas yang berbeda dalam RNG multi-ulir, dll.). Jika Anda menerima begitu saja bahwa setiap proses algoritma Anda mengambil input yang sama pada setiap iterasi ditentukan dengan baik tanpa keacakan, maka itu akan menghasilkan output yang sama pada setiap proses.

Yang sedang berkata, bahkan hal-hal dasar seperti suhu CPU tidak dapat diprediksi cukup untuk bertindak sebagai sumber entropi jika mereka dinormalisasi dengan tepat. Jadi, jangan berpikir ini menyiratkan bahwa generator nomor acak "aman secara kriptografis" dapat diprediksi jika Anda tahu jam berapa ia dijalankan; banyak dari mereka menggunakan umpan entropi yang dihasilkan sistem.

Brian
sumber
Algoritma adalah kata yang tepat :) Saya secara khusus mencoba untuk menghilangkan sumber luar entropi, kesalahan memori, urutan thread, input yang tidak dapat diprediksi seperti sumber cahaya, dll. Saya pikir pertanyaan saya berasal dari kurangnya pemahaman tentang algoritma acak dan mungkin Saya bisa membuat pertanyaan lebih umum. Saya benar-benar bertanya-tanya apakah mungkin untuk membuat fungsi apa pun yang mengembalikan hasil yang berbeda diberikan input yang identik (termasuk semua sumber entropi). Sepertinya jawabannya adalah tidak
ConditionRacer
7

Tahukah Anda bahwa orang bekerja sangat keras untuk memastikan bahwa, mengingat benih yang sama, urutan nomor acak yang sama dihasilkan setiap saat? Ini adalah properti yang diinginkan untuk hal-hal seperti simulasi Monte Carlo, karena artinya hasil sepenuhnya dapat direproduksi. Jika Anda tidak menentukan benih, sesuatu seperti waktu akan digunakan, tetapi reproduksibilitas yang tepat sangat diinginkan.

Satu-satunya RNG di mana ini benar-benar tidak diinginkan adalah yang digunakan untuk kriptografi, dan yang biasanya mencapainya dengan menggunakan sumber nomor acak sistem operasi itu sendiri (yang tidak dapat diputar ulang dalam keadaan normal dan yang mungkin menggunakan perangkat keras mewah) untuk menyediakan benih mereka.

Donal Fellows
sumber
Ya, saya mengerti apa yang Anda katakan. Saya tidak mencoba menerapkan sesuatu yang baru, ini hanya rasa ingin tahu larut malam.
ConditionRacer
1

Saya kira jika Anda menerapkan algoritma pada platform perangkat keras yang berbeda dan menggunakan teknik seperti mengambil bit N tengah dari integer, Anda bisa mendapatkan jawaban yang berbeda jika pengkodean integer berbeda (besar / kecil / mid-endian). Anda juga mungkin mengalami masalah berjalan pada mesin dengan FPU versus yang tidak jika Anda memanipulasi angka floating-point. Mungkin bukan masalah pada mesin kelas desktop, tetapi bisa menjadi masalah pada ponsel.

TMN
sumber