Sözde Rastlantısal Sayı Üreteci

(Eğlenceli müzik) (Hışırdayan yapraklar) Fiziksel dünyayı gözlemlediğimizde Biz her yerde rasgele dalgalanmalar bulabiliriz. Gerçekten rasgele sayılar üretebiliriz Rasgele dalgalanmaları ölçmek, gürültü olarak bilinir. Örnek olarak bilinen bu gürültüyü ölçtüğümüzde, sayılar elde edebiliriz. Bir iki üç dört-- örneğin biz tv statik akımını ölçtüğümüz zaman gerçekten bizim istediğimiz rasgele bir dizi oluşturur. Bu rasgele diziyi görselleştirebiliriz. Yön değiştiren bir yol çizerek her bir sayıya karşı bir bilinen rasgele yürüyüş. tüm şekillerde eksik olamamasına dikkat edin. serideki her noktada daima bir sonraki hamle öngörülemez. Rastgele süreçlerin nondeterministic (belirleyici olmayan) olduğu söylenir; Çünkü önceden belirlemek imkansızdır. Makineler ise deterministiktir(belirleyici olan). Onların çalışması öngörülebilir ve tekrarlanabilir. 1946'da John von Neumann ordu için hesaplamalar yapmakla görevlendirildi; Özellikle hidrojen bombasının tasarımında yer aldı. ENIAC adı verilen bir bilgisayar kullanarak, nükleer fisyon (çekirdek birleşmesi) aşamaları ile ilgili Yaklaşık hesaplamayı ard arda yapmayı planladı. Ancak bunun için hızlı erişim gerekiyordu gerekirse rasgele tekrarlanabilir sayılar üretebilmeliydi. Bununla birlikte, ENIAC'in dahili belleği çok sınırlıydı; rasgele uzun serilerin depolanması imkasızdı. Böylece, Neumann bir algoritma geliştirdi görünüşünü karıştırmak için mekanik olarak taklidi rasgele sürdürdü. Önce, "tohum" olarak adlandırılan gerçekten rasgele bir numara seçin. Bu sayı, gürültünün ölçülmesinden, veya milisaniye cinsinden mevcut zamandan gelebilir. Sonra, bu tohum girdi olarak öngörülür. Basit bir hesaplamayla. Tohumu tek başına çoğaltın, ve çıktı bu ortadaki sonuç. Sonra bir sonraki tohum olarak bu çıkışı kullanın, Ve süreci gerektiği kadar tekrarlayın. Bu, orta kareler yöntemi olarak bilinir Ve sadece uzun bir çizgide ilk rassal sayı üretecinde. Dizinin rassallığı, yalnızca ilk tohumun rasgelelik derecesine bağlıdır. Aynı tohum, aynı sıra. Peki, farklar nelerdir bir rasgele üretilen ile rassal üretilen seri arasında? Her seriyi rastgele bir yürüyüş olarak temsil edelim. biz artışı hızlandırana kadar işler benzer görünüyor. rassal seri eninde sonunda tekrarlanmalıdır. bu algoritma bir tohum ulaştığında görülür. daha önce kullanılmış döngüyü tekrarlar. bir rassal seri tekrarlarının uzunluğuna ''periyod'' denir periyod kesinlikle sınırlı ilk tohumun uzunluğuna bağlı. Örneğin, iki basamaklı bir tohum kullanırsak, O zaman bir algoritma Bir tohum tekrar kullanılmadan önce en fazla 100 sayı ve döngüyü tekrarlar Üç basamaklı bir tohum 1,000 sayıdan sonra genişleyemez Döngüsünü tekrarlamadan önce, Ve dört basamaklı bir tohum genişleyemez 10.000 sayıdan sonra tekrarlamadan önce Gerçi yeterince büyük bir tohum kullansak , Dizi büyüyebilir Tekrarlamadan önce trilyonlarca ve trilyonlarca haneye ulaşır. Anahtar ayrımı önemli olsa da. rassal sayılar ürettiğinizde, Gerçekleşemeyen birçok seri vardır. Örneğin, Alice gerçekten rasgele bir dizi oluşturursa 20 yerdeğiştirme, tek biçimli bir seçime eşdeğerdir Tüm olası yerdeğiştirme serilerinde bu yıgın 26 üzeri 20 sayfa gibi astronomik bir boyut. Eğer altta durup yukarı doğru bir ışık parlattırsak, En üstteki kişi ışığı Yaklaşık 200.000.000 yıl civarı göremiyecektir. Bunu Alice'nin üreteniyle karşılaştırın 20 basamaklı bir rassal seri Dört basamaklı rasgele bir tohum kullanarak. şimdi.bu tekdüze bir seçime eşdeğerdir. 10.000 olası başlangıç tohumlarından, O bir tek anlam üretebilir. 10.000 farklı dizilim, çok küçük bir kesir olası tüm serilerde. rasgeleden rassala geçtiğimizde Anahtar alanı daralttık Çok daha küçük tohumluk alanı. Yani, sözde rassal bir serinin ayırt edilemez olması rasgele bir seriden bir bilgisayar için kullanışsız olmalıdır. Tüm tohumları denemek ve bir eş aramak için. Bu, önemli bir ayrıma yol açar Bilgisayar bilimlerinde, mümkün olanın arasında, makul bir süre içinde mümkün. Bisiklet kilidi satın alırken aynı mantığı kullanırız. Herkesin deneyebileceğini biliyoruz. Tüm olası kombinasyonlar, bir eş bulunca açılıyor. Ancak bunları yapmak günlerce sürer. Yani sekiz saat boyunca pratik olarak güvenli olduğunu varsayıyoruz. rassal üreteci ile Tohumun uzunluğu arttıkça güvenlik artar. daha güçlü bilgisayarlala 100'lerce yıl tohumları baştan sona çalıştırmak gerekir. O zaman pratik bir şekilde güvenli olduğunu varsayabiliriz, yerine göre tamamen güvenli. Bilgisayarlar daha hızlı hale geldiğinde Buna göre tohum büyüklüğü de arttırılmalıdır. rassallar Alice ve Bob'u özgür bırakıyor. onların paylaşımları için Tüm rastgele yerdeğiştirme sırasını girmek yerine, nispeten kısa rasgele bir tohum paylaşıyorlar, ve içeriyi aynı şekilde genişletiyor. seri lazım olduğu zamam rasgele bakan bu rasgele tohumla asla karşılaşamazsa nolur?