Hemen hemen tüm bilgisayarların yazılımı, sözde rasgele, yarı düzgün bir şekilde dağıtılmış sayıların bir dizisini oluşturmak için yerleşik bir işleve sahiptir. Ancak istatistiksel modelleme için rastgele sayı üretimine yönelik artan gereksinimler vardır. Bu tür bir modellemenin sonuçlarının kalitesi doğrudan düzgün dağıtılmış rastgele sayılar üretecinin kalitesine bağlıdır, çünkü bu sayılar aynı zamanda belirli bir dağılım yasasıyla diğer rastgele değişkenleri elde etmek için kaynaklardır (ilk veriler).
Ne yazık ki ideal jeneratörler mevcut değil ve bilinen özelliklerinin listesi bir dezavantaj listesiyle dolduruluyor. Bu, bilgisayar deneyinde hatalı bir jeneratör kullanma riskine yol açar. Bu nedenle, bir bilgisayar deneyi yapmadan önce, ya bilgisayarda yerleşik olan rastgele sayı üretme fonksiyonunun kalitesini değerlendirmek ya da uygun bir rastgele sayı üretme algoritması seçmek gerekir.
Hesaplamalı fizikte kullanılabilmesi için jeneratörün aşağıdaki özelliklere sahip olması gerekir:
Hesaplama verimliliği, bir sonraki döngü için mümkün olan en kısa hesaplama süresi ve jeneratörü çalıştırmak için gereken bellek miktarıdır.
Büyük uzunlukta L rastgele sayı dizisi. Bu süre en azından istatistiksel bir deney için gerekli olan rastgele sayılar kümesini içermelidir. Ayrıca L'nin sonuna yaklaşmak bile bir tehlike oluşturur ve bu durum istatistiksel bir deneyin yanlış sonuçlara yol açmasına neden olabilir.
Sahte rasgele bir dizinin yeterli uzunlukta olması için kriter aşağıdaki hususlardan seçilir. Monte Carlo yöntemi, simüle edilmiş bir sistemin çıkış parametrelerinin, verilen dağıtım yasalarıyla dalgalanan giriş parametrelerinin etkisi altında tekrarlanan hesaplamalarından oluşur. Yöntemin uygulanmasının temeli rastgele sayıların üretilmesidir. üniforma verilen dağılım yasalarına sahip rastgele sayıların oluşturulduğu aralıktaki dağılım. Daha sonra, simüle edilen olayın olasılığı, başarılı sonuç veren model deneylerinin tekrar sayısının, modelin belirli başlangıç koşulları (parametreler) altında deneylerin toplam tekrar sayısına oranı olarak hesaplanır.
Bu olasılığın istatistiksel anlamda güvenilir bir şekilde hesaplanması için, deneyin tekrar sayısı aşağıdaki formül kullanılarak tahmin edilebilir:
Nerede 
- işlev, ters fonksiyon normal dağılım, 
- güven hata olasılığı 
Olasılık ölçümleri.
Bu nedenle hatanın güven aralığının dışına çıkmaması için örneğin güven olasılığı ile =0,95 deneyin tekrar sayısının aşağıdakilerden az olmaması gerekir:
(2.2)
Örneğin %10'luk bir hata için (
=0.1) şunu elde ederiz 
ve %3'lük bir hata için (
=0,03) zaten elde ettik 
.
Başkaları için başlangıç koşulları modelde, farklı bir sözde rastgele dizi üzerinde yeni bir dizi tekrar deneyi gerçekleştirilmelidir. Bu nedenle, sözde rastgele dizi oluşturma işlevinin onu değiştiren bir parametreye sahip olması gerekir (örneğin, R 0 ) veya uzunluğu en az şu şekilde olmalıdır:
Nerede k - başlangıç koşullarının sayısı (eğri üzerindeki Monte Carlo yöntemiyle belirlenen noktalar), N - Verilen başlangıç koşulları altında model deneyinin tekrar sayısı, L - sözde rastgele dizinin uzunluğu.
Daha sonra her seri N her deneyin tekrarları sözde rastgele dizinin kendi bölümünde gerçekleştirilecektir.
Yeniden üretilebilirlik. Yukarıda belirtildiği gibi, sözde rasgele sayıların oluşturulmasını değiştiren bir parametrenin olması arzu edilir. Genellikle bu R'dir 0 . Bu nedenle değişim çok önemli 0 rastgele sayı üretecinin kalitesini (yani istatistiksel parametreleri) bozmadı.
İyi istatistiksel özellikler. Bu, rastgele sayı üretecinin kalitesinin en önemli göstergesidir. Ancak herhangi bir kriter veya testle değerlendirilemez çünkü Sonlu bir sayı dizisinin rastgeleliği için gerekli ve yeterli bir kriter yoktur. Sözde-rastgele sayı dizisi hakkında söylenebilecek en fazla şey, onun rastgele "göründüğü"dür. Hiçbir istatistiksel test tek başına güvenilir bir doğruluk göstergesi değildir. En azından rastgele sayı üretecinin kalitesinin en önemli yönlerini yansıtan çeşitli testlerin kullanılması gereklidir; ideal bir jeneratöre yaklaşma derecesi.
Bu nedenle, jeneratörü test etmenin yanı sıra, sonuçların analitik veya sayısal yöntemlerle bağımsız olarak değerlendirilmesine olanak tanıyan standart problemler kullanılarak test edilmesi son derece önemlidir.
Sözde rastgele sayıların güvenilirliği fikrinin, bunların kullanılması sürecinde, sonuçların mümkün olduğunca dikkatlice kontrol edilmesiyle yaratıldığı söylenebilir.
Sahte rastgele sayılar elde etmek için ilk algoritma J. Neumann tarafından önerildi. Buna karelerin ortası yöntemi denir.
4 basamaklı bir R sayısı verilsin 0 =0,9876. Karesini alalım. 8 basamaklı bir R sayısını alalım 0 2 =0,97535376. Bu sayıdan ortadaki 4 rakamı seçip R koyalım. 1 =0,5353. Sonra tekrar karesini alıyoruz ve ortadaki 4 rakamı çıkarıyoruz. R'yi alıyoruz 2 vesaire. Bu algoritma kendini kanıtlayamadı. R'nin gereğinden fazla küçük değerleri olduğu ortaya çıktı Ben .
Bununla birlikte, R'nin rakam seçim grubunun sağa kaydırılmasıyla bu üretecin kalitesinin araştırılması ilgi çekicidir. Ben 2 :
burada a, belirli bir bilgisayar için kesrin maksimum değeridir (örneğin, a = 8).
b-R sayısındaki ondalık basamak sayısı Ben(örneğin, 5).
INT(A)- Bütün parça sayılar.
a=8,b=5,R için 0 =0,51111111 PC ZX-Spectrum'da bu, yaklaşık 1200 tekrarlanmayan sayıyla sonuçlanır.
Egzersiz yapmak: Çalışma a, b, R değiştirilerek yürütülmelidir. 0 . A, b, R'nin hangi değerlerinde olduğunu bulun 0 Tekrarlanmayan sayılar dizisinin en büyük uzunluğu L, "iyi" stokastik parametrelerle elde edilir. R değerinin etkileyip etkilemediğini belirleyin 0 sensörün kalitesine bağlı. Eğer öyleyse, R parametresinin “kabul edilebilir” değerlerinin aralığını belirleyin. 0 . A, b, R değerlerinin optimal değişkenini test etmenin sonuçlarını sunun 0 .
Çarpımsal algoritmalar. Sensör #2: Lehmer 1951 Doğrusal Uyumlu Jeneratör.
Neredesin Ben,M,Cip – tamsayılar.
AmodB, A'nın B'ye bölünmesinden kalan kısımdır,
A mod B =A-B*INT (A/B)
Oluşturulan dizi, p sayısını aşmayan bir tekrarlanan döngüye sahiptir.
Maksimum periyot C0'da elde edilir, ancak böyle bir üreteç zayıf stokastik sonuçlar verir.
C=0 olduğunda üreteçlere çarpımsal denir. Daha iyi stokastik parametrelere sahiptirler. Bunları kullanma formüllerine aynı zamanda kesinti yöntemi de denir.
Sahte rastgele sayılar elde etmenin en popüler yöntemi, aşağıdaki formülü kullanan kesinti yöntemidir:
Neredesin Ben,M,p-tamsayılar, 0
U'yu seçerseniz 0 ve M öyle ki R için 0 =U 0 /p'nin indirgenemez bir kesir olduğu ortaya çıktı ve p ile M'yi aralarında asal olarak alırsak, o zaman R'nin tümü Ben formun indirgenemez kesirleri olacaktır: R Ben=U Ben/P.
Tekrarlanmayan bir sayı dizisinin en büyük (fakat p'den fazla olmayan) uzunluğunu elde edelim. U değerleri 0 ,pM asal sayılar arasından seçim yapmak uygundur.
Egzersiz yapmak: Ne olduğunu araştırın 0 ,pM, tekrarlanmayan sayılar dizisinin uzunluğu "iyi" stokastik parametrelerle en az 10000 olacaktır. R değerinin olup olmadığını belirleyin 0 Mip = sensörün istatistiksel özelliklerine bağlı olduğunda. Eğer öyleyse, izin verilen değerlerin aralığını belirleyinU 0 . Optimum p, Mi ve U değerleri için jeneratör testinin sonuçlarını sunun 0 .
Sensör No. 3: Korobov modifikasyonu.
burada p büyük bir asal sayıdır, örneğin 2027, 5087, ...
M, koşulları karşılayan bir tam sayıdır:
n bir tamsayıdır. Onlar. M = p – 3 n sayıları kümesinden p/2'ye yakın M'yi seçin.
Örneğin p=5087 için n=7 alıyoruz. Çünkü 3 7 =2187 ve 3 8 =6561 zaten daha büyük olacaktır. Yani: M=5087-2187=2900.
U rakamlarını alıyoruz Ben= ve sayılar aralığında R Ben(0,1) aralığında.
Egzersiz yapmak: Sensörün en iyi istatistiksel parametrelerinin ve en uzun L uzunluğunun elde edildiği Mp'yi seçin. R değerinin olup olmadığını öğrenin 0 sensörün stokastik özelliklerine göre ve etkilenirse izin verilen R değerlerinin aralığını belirleyin 0 . Optimum M, p ve R değerleri için sensör test sonuçlarını sunun 0 .
Deterministik PRNG'ler
Hiçbir deterministik algoritma tamamen rastgele sayılar üretemez; yalnızca rastgele sayıların bazı özelliklerine yaklaşık olarak yaklaşabilir. John von Neumann'ın dediği gibi, " Rasgele sayılar elde etmek için aritmetik yöntemlere karşı zayıflığı olan herkes, şüphesiz günahkardır».
Sınırlı kaynaklara sahip herhangi bir PRNG, er ya da geç döngülere girer - aynı sayı dizisini tekrarlamaya başlar. PRNG döngülerinin uzunluğu jeneratörün kendisine bağlıdır ve ortalamaları yaklaşık 2n/2'dir; burada n, dahili durumun bit cinsinden boyutudur, ancak doğrusal uyumlu ve LFSR jeneratörleri 2n düzeyinde maksimum döngülere sahiptir. Bir PRNG çok kısa döngülere yakınlaşabilirse, PRNG öngörülebilir ve kullanılamaz hale gelir.
Basit aritmetik üreteçlerin çoğu, çok hızlı olmalarına rağmen birçok ciddi dezavantaja sahiptir:
- Dönem/dönemler çok kısa.
- Ardışık değerler bağımsız değildir.
- Bazı bitler diğerlerinden daha az rastgeledir.
- Düzensiz tek boyutlu dağılım.
- Tersine çevrilebilirlik.
Özellikle ana bilgisayar algoritmasının çok zayıf çıkması, bu algoritmayı kullanan birçok çalışmanın sonuçlarının geçerliliği konusunda şüpheleri artırdı.
Entropi kaynağı veya RNG'li PRNG
Kolayca tekrarlanabilen rastgele sayı dizileri üretmeye ihtiyaç olduğu gibi, tamamen öngörülemeyen veya tamamen rastgele sayılar üretmeye de ihtiyaç vardır. Bu tür jeneratörlere denir rastgele sayı üreteçleri(RNG - İngilizce) rastgele sayı üreteci, RNG). Bu tür oluşturucular çoğunlukla şifreleme için benzersiz simetrik ve asimetrik anahtarlar oluşturmak için kullanıldığından, çoğunlukla kriptografik olarak güçlü bir PRNG ile harici bir entropi kaynağının birleşiminden oluşturulurlar (ve artık yaygın olarak bir anahtar olarak anlaşılan da tam olarak bu kombinasyondur). RNG).
Hemen hemen tüm büyük çip üreticileri, donanım RNG'lerini kaçınılmaz öngörülebilirlikten arındırmak için çeşitli yöntemler kullanarak çeşitli entropi kaynaklarıyla tedarik ediyor. Ancak şu anda mevcut tüm mikroçipler tarafından rastgele sayıların toplanma hızı (saniyede birkaç bin bit), modern işlemcilerin hızına karşılık gelmiyor.
Kişisel bilgisayarlarda, yazılım RNG yazarları, ses kartı gürültüsü veya işlemci saat döngüsü sayacı gibi çok daha hızlı entropi kaynaklarını kullanır. Saat sayacı değerlerinin okunması mümkün olmadan önce entropi toplanması, RNG'nin en savunmasız noktasıydı. Bu sorun birçok cihazda (örn. akıllı kartlar) hala tam olarak çözülmemiştir ve bu nedenle savunmasız kalmaktadır. Birçok RNG hala entropi toplamak için geleneksel (modası geçmiş) yöntemler kullanıyor; örneğin kullanıcı tepkilerini (fare hareketi vb.) ölçmek veya Java güvenli rastgele örneğinde olduğu gibi iş parçacıkları arasındaki etkileşimi ölçmek.
RNG ve entropi kaynaklarına örnekler
Entropi kaynakları ve üreteçleriyle birlikte RNG'lere birkaç örnek:
| Entropinin kaynağı | PRNG | Avantajları | Kusurlar | |
|---|---|---|---|---|
| Linux'ta /dev/random | CPU saat sayacı ancak yalnızca donanım kesintileri sırasında toplanır | LFSR, çıkış karma değeriyle | Çok uzun süre "ısınır", uzun süre "sıkışabilir" veya PRNG gibi çalışır ( /dev/urandom) | |
| Civanperçemi kaydeden Bruce Schneier | Geleneksel (modası geçmiş) yöntemler | AES-256 ve | Esnek kriptoya dayanıklı tasarım | "Isınması" uzun zaman alır, çok küçük dahili durum, seçilen algoritmaların kriptografik gücüne çok fazla bağlıdır, yavaştır, yalnızca anahtar üretimi için uygulanabilir |
| Jeneratör, Leonid Yuryev | Ses kartı gürültüsü | ? | Büyük olasılıkla iyi ve hızlı bir entropi kaynağı | Bağımsız, bilinen, kripto açısından güçlü bir PRNG yok, yalnızca Windows olarak mevcut |
| Microsoft | Windows'a yerleşiktir, takılıp kalmaz | Küçük dahili durum, tahmin edilmesi kolay | ||
| İş parçacığı arasındaki iletişim | Henüz Java'da başka seçenek yok, büyük bir dahili durum var | Yavaş entropi toplama | ||
| Ruptor'dan Kaos | Sürekli olarak toplanan işlemci saat sayacı | Marsaglia oluşturucunun doğrusal olmayan bir varyantına dayalı olarak 4096 bitlik dahili durumu karma oluşturma | En hızlısı, büyük iç devlet “sıkışıp kalana” kadar | |
| Ruptor'dan RRAND | CPU döngü sayacı | Dahili durumu bir akış şifresiyle şifrelemek | Çok hızlı, isteğe bağlı boyutta dahili durum, "sıkışmış" değil |
Kriptografide PRNG
PRNG'nin bir türü, çeşitli akış şifrelerinin yanı sıra sahte rastgele bitlerin üreteçleri olan PRBG'lerdir. PRNG'ler, akış şifreleri gibi, bir dahili durumdan (genellikle boyutu 16 bit ila birkaç megabayt arasında değişen) oluşur; dahili durumu bir anahtar veya tohum(İngilizce) tohum), dahili durum güncelleme fonksiyonları ve çıkış fonksiyonları. PRNG'ler basit aritmetik, kırık kriptografik ve güçlü kriptografik olarak ayrılır. Genel amaçları, hesaplamalı yöntemlerle rastgele olarak ayırt edilemeyen sayı dizileri oluşturmaktır.
Birçok güçlü PRNG veya akış şifresi çok daha fazla "rastgele" sayılar sunsa da, bu tür üreteçler geleneksel aritmetik üreteçlerden çok daha yavaştır ve işlemcinin daha kullanışlı hesaplamalar için özgür olmasını gerektiren herhangi bir araştırma türü için uygun olmayabilir.
Askeri amaçlar için ve saha koşullarında yalnızca gizli senkronize kriptografik güçlü PRNG'ler (akış şifreleri) kullanılır; blok şifreler kullanılmaz. İyi bilinen kripto-güçlü PRNG'lere örnek olarak ISAAC, SEAL, Snow, Bloom, Bloom ve Shub'un çok yavaş teorik algoritmasının yanı sıra çıkış işlevi yerine kriptografik hash işlevlerine veya güçlü blok şifrelerine sahip sayaçlar verilebilir.
Donanım PRNG'si
20. yüzyılda donanım PRNG'leri olarak yaygın şekilde kullanılan eski, iyi bilinen LFSR jeneratörlerinin yanı sıra, çoğu askeri amaçlar için geliştirildiğinden ve gizli tutulduğundan ne yazık ki modern donanım PRNG'leri (akış şifreleri) hakkında çok az şey biliniyor. . Neredeyse mevcut tüm ticari donanım PRNG'leri patentlidir ve aynı zamanda gizli tutulur. Donanım PRNG'leri, tüketilebilir bellek (çoğunlukla bellek kullanımı yasaktır), hız (1-2 saat döngüsü) ve alan (birkaç yüz FPGA - veya
İyi donanım PRNG'lerinin bulunmaması nedeniyle, üreticiler ellerindeki çok daha yavaş ama iyi bilinen blok şifreleri kullanmak zorunda kalıyorlar (Computer Review No. 29 (2003)
Rastgele sayıların elde edilmesi ve dönüştürülmesi.
Rasgele sayılar elde etmenin iki ana yolu vardır:
1) Rastgele sayılar, bilgisayara takılan özel bir elektronik eklenti (rastgele sayı sensörü) tarafından üretilir. Bu yöntemin uygulanması, rastgele sayı sensörüne erişim dışında neredeyse hiçbir ek işlem gerektirmez.
2) Algoritmik yöntem - özel bir program kullanılarak makinenin kendisinde rastgele sayılar üretilmesine dayanır. Bu yöntemin dezavantajı, bilgisayar zamanının ek tüketimidir, çünkü bu durumda makine, elektronik set üstü kutunun işlemlerini kendisi gerçekleştirir.
Belirli bir dağıtım yasasını kullanarak rastgele sayılar üreten bir program hantal olabilir. Bu nedenle, belirli bir dağılım yasasına sahip rasgele sayılar genellikle doğrudan değil, belirli bir standart dağılıma sahip rasgele sayıların dönüştürülmesiyle elde edilir. Çoğunlukla bu standart dağılım tekdüze dağılımdır (elde edilmesi kolay ve diğer yasalara dönüştürülmesi kolaydır).
Bilgisayarı ek bilgisayar zamanı maliyetlerinden kurtaran elektronik bir set üstü kutu kullanarak tekdüze bir yasaya sahip rastgele sayılar elde etmek en avantajlı olanıdır. Bit ızgarasının sınırlı doğasından dolayı bilgisayarda tamamen tekdüze bir dağılım elde etmek imkansızdır. Bu nedenle (0, 1) aralığında sürekli bir sayı kümesi yerine ayrık bir sayı kümesi kullanılır 2n sayılar, nerede N– makine sözcüğünün bit derinliği.
Böyle bir nüfusun dağılım yasasına denir yarı-üniform . n³20'de, tekdüze ve yarı-tekdüze yasalar arasındaki farklar önemsiz hale gelir.
Yarı düzgün rastgele sayılar elde etmek için iki yöntem kullanılır:
1) bazı rastgele süreçleri modelleyerek elektronik bir set üstü kutu kullanarak rastgele sayılar üretmek;
2) özel algoritmalar kullanarak sözde rastgele sayıların elde edilmesi.
Almak için N basamaklı ikili rasgele sayı, ilk yöntem bağımsız rasgele değişkenlerin bir dizisini simüle eder z ben 0 veya 1 değerini alır. Kesirli bir sayı olarak düşünürsek, ortaya çıkan dizi 0 ve 1'dir ve (0, 1) aralığında yarı-üniform dağılıma sahip rastgele bir değişkeni temsil eder. Bu sayıları elde etmek için kullanılan donanım yöntemleri, yalnızca uygulamayı elde etme şekilleri açısından farklılık gösterir. z ben.
Yöntemlerden biri, belirli bir süre boyunca radyoaktif parçacıkların sayısının sayılmasına dayanmaktadır. Dt parçacık sayısı fazla ise Dt o zaman bile z ben=1 ve eğer tuhafsa o zaman z ben=0 .
Başka bir yöntem, vakum tüpünün gürültü etkisini kullanır. Zamanın belirli noktalarında gürültü voltajının değerini kaydederek ben bağımsız rastgele değişkenlerin değerlerini elde ediyoruz U(t ben) yani voltaj (Volt).
Büyüklük z ben kanunla belirlenir:
Nerede A– eşik voltajının belirli bir değeri.
Büyüklük A genellikle şu durumdan seçilir:
Donanım yönteminin dezavantajı, tekrarlanan çalıştırmalar aynı rastgele sayıları elde edemeyeceğinden, herhangi bir sorunu çözmek için algoritmanın çalışmasını kontrol etmek amacıyla çift çalıştırma yönteminin kullanılmasına izin vermemesidir.
Sahte rastgeleÖzel programlar kullanarak bilgisayarda oluşturulan numaraları tekrarlı bir şekilde çağırırlar: her rastgele sayı, özel dönüşümler kullanılarak bir öncekinden elde edilir.
Bu dönüşümlerin en basiti aşağıdaki gibidir. Biraz olsun N– aralıktaki bit ikili sayı nО (0, 1). Karesini alalım ve şunu elde edelim 2n dijital numara. Ortalamaları vurgulayalım N deşarj olur. Bu şekilde elde edilen N– rakamlı sayı, rastgele sayının yeni değeri olacaktır. Tekrar karesini alırız, vb. Bu dizi sözde rastgeledir, çünkü teorik açıdan bakıldığında rastgele değildir.
Tekrarlayan algoritmaların dezavantajı, rastgele sayı dizilerinin dejenere olabilmesidir (örneğin, yalnızca bir sıfır dizisini veya bir dizisini alırız veya periyodiklik ortaya çıkabilir).
İdeal olarak rastgele sayı dağılım yoğunluk eğrisinin Şekil 2'de gösterildiği gibi görüneceğini unutmayın. 22.3. Yani ideal olarak her aralık aynı sayıda noktayı içerir: N Ben = N/k , Nerede N toplam puan sayısı, k aralık sayısı, Ben= 1, , k .
ideal bir jeneratör tarafından teorik olarak üretilir
Rastgele bir rastgele sayı üretmenin iki aşamadan oluştuğu unutulmamalıdır:
- normalleştirilmiş bir rastgele sayının üretilmesi (yani 0'dan 1'e eşit şekilde dağıtılması);
- normalleştirilmiş rastgele sayı dönüşümü R Ben rastgele sayılara X Ben Kullanıcının gerektirdiği (keyfi) dağıtım yasasına göre veya gereken aralıkta dağıtılanlar.
Sayı elde etme yöntemine göre rastgele sayı üreteçleri ikiye ayrılır:
- fiziksel;
- tablo halinde;
- algoritmik.
Fiziksel RNG
Fiziksel bir RNG örneği şunlar olabilir: bir madeni para (“tura” 1, “yazı” 0); zar; sayılarla sektörlere bölünmüş oklu bir tambur; Örneğin bir transistör gibi gürültülü bir termal cihaz kullanan donanım gürültü üreteci (HS).
| Görev “Para kullanarak rastgele sayılar üretme” | |
|
Bir madeni para kullanarak 0 ile 1 arasında eşit olarak dağıtılan üç basamaklı rastgele bir sayı oluşturun. Doğruluk üç ondalık basamak. |
|
Sorunu çözmenin ilk yolu
0'dan 1'e kadar bir aralık çizin. Sayıları soldan sağa sırayla okuyun, aralığı ikiye bölün ve her seferinde bir sonraki aralığın parçalarından birini seçin (0 alırsanız soldakini, 0 alırsanız soldakini) a 1, sonra sağdaki). Böylece aralıktaki herhangi bir noktaya istediğiniz kadar doğru bir şekilde ulaşabilirsiniz. Bu yüzden, 1 : aralık ikiye bölünür ve sağ yarı seçilir, aralık daraltılır: . Sonraki numara 0 : aralık ikiye bölünür ve sol yarı seçilir, aralık daraltılır: . Sonraki numara 0 : aralık ikiye bölünür ve sol yarı seçilir, aralık daraltılır: . Sonraki numara 1 : aralık ikiye bölünür ve sağ yarı seçilir, aralık daraltılır: . Sorunun doğruluk koşuluna göre bir çözüm bulunmuştur: Aralıktan herhangi bir sayıdır, örneğin 0,625. Prensip olarak, eğer katı bir yaklaşım izlersek, aralıkların bölünmesi, bulunan aralığın sol ve sağ sınırları üçüncü ondalık basamak doğruluğu ile ÇAĞDAŞ olana kadar devam ettirilmelidir. Yani doğruluk açısından bakıldığında, oluşturulan sayı artık bulunduğu aralıktaki hiçbir sayıdan ayırt edilemeyecektir.
Sorunu çözmenin ikinci yolu
|
Tablo RNG'si
Tablolu RNG'ler, rastgele sayıların kaynağı olarak, ilişkisiz olduğu doğrulanmış, yani hiçbir şekilde birbirine bağımlı olmayan sayılar içeren özel olarak derlenmiş tablolar kullanır. Masada Şekil 22.1 böyle bir tablonun küçük bir bölümünü göstermektedir. Tabloyu soldan sağa, yukarıdan aşağıya doğru hareket ettirerek, gerekli sayıda ondalık basamakla 0'dan 1'e eşit olarak dağıtılmış rastgele sayılar elde edebilirsiniz (örneğimizde, her sayı için üç ondalık basamak kullanıyoruz). Tablodaki sayılar birbirine bağlı olmadığından, tablo yukarıdan aşağıya veya sağdan sola gibi farklı şekillerde hareket edebilir veya örneğin eşit konumdaki sayıları seçebilirsiniz.
| Tablo 22.1. Rastgele numaralar. Eşit olarak 0'dan 1'e kadar dağıtılan rastgele sayılar |
||||||||||||||||||||||||||||||||||||||||||||
| Rastgele numaralar | Aynı oranda paylaştırılmış 0'dan 1'e kadar rastgele sayılar |
|||||||
| 9 | 2 | 9 | 2 | 0 | 4 | 2 | 6 | 0.929 |
| 9 | 5 | 7 | 3 | 4 | 9 | 0 | 3 | 0.204 |
| 5 | 9 | 1 | 6 | 6 | 5 | 7 | 6 | 0.269 |
Bu yöntemin avantajı, tablonun doğrulanmış ilişkisiz sayılar içermesi nedeniyle gerçekten rastgele sayılar üretmesidir. Yöntemin dezavantajları: Çok sayıda rakamı saklamak çok fazla bellek gerektirir; Bu tür tabloların oluşturulmasında ve kontrol edilmesinde büyük zorluklar vardır; bir tablo kullanılırken yapılan tekrarlar artık sayısal dizinin rastgeleliğini ve dolayısıyla sonucun güvenilirliğini garanti etmez.
Kesinlikle rastgele doğrulanmış 500 sayı içeren bir tablo vardır (I. G. Venetsky, V. I. Venetskaya "Ekonomik analizde temel matematiksel ve istatistiksel kavramlar ve formüller" kitabından alınmıştır).
Algoritmik RNG
Bu RNG'ler tarafından oluşturulan sayılar her zaman sözde rastgeledir (veya yarı rastgeledir), yani üretilen her sonraki sayı bir öncekine bağlıdır:
R Ben + 1 = F(R Ben) .
Bu tür sayılardan oluşan diziler döngüler oluşturur, yani sonsuz sayıda tekrarlanan bir döngünün olması gerekir. Tekrarlanan döngülere periyot denir.
Bu RNG'lerin avantajı hızlarıdır; jeneratörler neredeyse hiç bellek kaynağı gerektirmez ve kompakttır. Dezavantajları: Sayılar tam olarak rastgele olarak adlandırılamaz, çünkü aralarında bir bağımlılık olduğu gibi yarı rastgele sayılar dizisindeki dönemlerin varlığı da vardır.
RNG elde etmek için birkaç algoritmik yöntemi ele alalım:
- medyan kareler yöntemi;
- orta ürünler yöntemi;
- karıştırma yöntemi;
- doğrusal uyumlu yöntem.
Orta kare yöntemi
Dört basamaklı bir sayı var R 0. Bu sayının karesi alınır ve girilir. R 1. Sonraki R 1 ortadaki (ortadaki dört rakamlı) yeni rastgele sayıyı alır ve bunu içine yazar R 0. Daha sonra prosedür tekrarlanır (bkz. Şekil 22.6). Aslında rastgele bir sayı olarak almamanız gerektiğini unutmayın. ghij, A 0.ghij sola bir sıfır ve bir ondalık nokta eklenerek. Bu gerçek Şekil 2'de olduğu gibi yansıtılmaktadır. 22.6 ve sonraki benzer şekillerde.
 |
Yöntemin dezavantajları: 1) eğer bir yinelemede sayı R 0 sıfıra eşit olur, ardından jeneratör dejenere olur, dolayısıyla başlangıç değerinin doğru seçimi önemlidir R 0; 2) jeneratör diziyi tekrarlayacaktır M N adımlar (en iyi ihtimalle), nerede N sayı haneli R 0 , M sayı sisteminin temeli
Örneğin Şekil 2'de. 22.6: eğer sayı Rİkili sayı sisteminde 0 temsil edilecek, daha sonra sözde rastgele sayılar dizisi 2 4 = 16 adımda tekrarlanacaktır. Başlangıç numarasının kötü seçilmesi durumunda dizinin tekrarının daha erken gerçekleşebileceğini unutmayın.
Yukarıda açıklanan yöntem John von Neumann tarafından önerilmiştir ve tarihi 1946 yılına kadar uzanmaktadır. Bu yöntemin güvenilmez olduğu ortaya çıkınca hızla terk edildi.
Orta ürün yöntemi
Sayı R 0 ile çarpıldı R 1, elde edilen sonuçtan R 2 ortası çıkarılır R 2 * (bu başka bir rastgele sayıdır) ve ile çarpılır R 1. Sonraki tüm rastgele sayılar bu şema kullanılarak hesaplanır (bkz. Şekil 22.7).
 |
Karıştırma yöntemi
Karıştırma yöntemi, bir hücrenin içeriğini döngüsel olarak sola ve sağa kaydırmak için işlemleri kullanır. Yöntemin fikri şu şekildedir. Hücrenin ilk sayıyı saklamasına izin ver R 0. Hücre içeriğini döngüsel olarak hücre uzunluğunun 1/4'ü kadar sola kaydırarak yeni bir sayı elde ederiz. R 0 * . Aynı şekilde hücrenin içeriğini döngüye sokmak R 0 hücre uzunluğunun 1/4'ü kadar sağa doğru ikinci sayıyı elde ederiz R 0**. Sayıların toplamı R 0* ve R 0** yeni bir rastgele sayı verir R 1. Daha öte R 1 girildi R 0 ve tüm işlem sırası tekrarlanır (bkz. Şekil 22.8).
 |
Lütfen toplamdan elde edilen sayının R 0* ve R 0 ** , hücreye tam olarak sığmayabilir R 1. Bu durumda, ortaya çıkan sayıdan fazla rakamların atılması gerekir. Bunu Şekil 2'de açıklayalım. 22.8, burada tüm hücreler sekiz ikili rakamla temsil edilir. İzin vermek R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Daha sonra R 0 * + R 0 ** = 100110010 2 = 306 10 . Gördüğünüz gibi 306 sayısı 9 rakamı kaplar (ikili sayı sisteminde) ve hücre R 1 (aynısı R 0) maksimum 8 bit içerebilir. Bu nedenle değeri girmeden önce R 1'de, 306 sayısından en soldaki bir "ekstra" biti kaldırmak gerekir; R 1 artık 306'ya değil, 00110010 2 = 50 10'a gidecek. Ayrıca Pascal gibi dillerde, bir hücre taşması durumunda ekstra bitlerin "kırpılmasının", değişkenin belirtilen türüne göre otomatik olarak gerçekleştirildiğini unutmayın.
Doğrusal uyumlu yöntem
Doğrusal eş yöntem şu anda rastgele sayıları simüle eden en basit ve en yaygın kullanılan prosedürlerden biridir. Bu yöntem modu kullanır ( X, sen) , ilk argüman ikinciye bölündüğünde kalanı döndürür. Sonraki her rastgele sayı, aşağıdaki formül kullanılarak önceki rastgele sayıya göre hesaplanır:
R Ben+ 1 = mod( k · R Ben + B, M) .
Bu formül kullanılarak elde edilen rastgele sayılar dizisine denir doğrusal uyumlu dizi. Birçok yazar aşağıdaki durumlarda doğrusal uyumlu dizi adını verir: B = 0 çarpımsal uyumlu yöntem, ve ne zaman B ≠ 0 karışık uyumlu yöntem.
Kaliteli bir jeneratör için uygun katsayıların seçilmesi gerekir. Sayının olması gerekli M oldukça büyüktü, çünkü dönem daha fazlasına sahip olamaz M elementler. Öte yandan, bu yöntemde kullanılan bölme oldukça yavaş bir işlem olduğundan, ikili bilgisayar için mantıksal seçim şöyle olacaktır: M = 2 Nçünkü bu durumda bölmenin geri kalanını bulmak bilgisayar içinde ikili mantıksal "VE" işlemine indirgenir. En büyük asal sayıyı seçmek de yaygındır M, 2'den az N: özel literatürde, bu durumda ortaya çıkan rastgele sayının düşük sıralı rakamlarının olduğu kanıtlanmıştır. R Ben+ 1, eskileri kadar rastgele davranır ve bu, bir bütün olarak rastgele sayılar dizisinin tamamı üzerinde olumlu bir etkiye sahiptir. Örnek olarak aşağıdakilerden biri Mersenne numaraları, 2 31 1'e eşittir ve dolayısıyla, M= 2 31 1 .
Doğrusal uyumlu dizilerin gereksinimlerinden biri, periyot uzunluğunun mümkün olduğu kadar uzun olmasıdır. Dönemin uzunluğu değerlere bağlıdır M , k Ve B. Aşağıda sunduğumuz teorem, belirli değerler için maksimum uzunlukta bir süreye ulaşmanın mümkün olup olmadığını belirlememizi sağlar. M , k Ve B .
Teorem. Sayılarla tanımlanan doğrusal uyumlu dizi M , k , B Ve R 0, bir periyoda sahiptir M ancak ve ancak:
- sayılar B Ve M görece basit;
- k 1 kez P her asal sayı için P, bu bir bölendir M ;
- k 1 4'ün katı ise M 4'ün katı.
Son olarak, rastgele sayılar üretmek için doğrusal eş yöntemin kullanımına ilişkin birkaç örnekle bitirelim.
Örnek 1'deki verilere dayanarak oluşturulan bir dizi sözde rastgele sayının her seferinde tekrarlanacağı belirlendi. M/4 sayı. Sayı Q hesaplamalara başlamadan önce keyfi olarak belirlenir, ancak serinin genel olarak rastgele olduğu izlenimini verdiği unutulmamalıdır. k(ve bu nedenle Q). Sonuç şu şekilde iyileştirilebilir: B tuhaf ve k= 1 + 4 · Q bu durumda satır her seferinde tekrarlanacaktır M sayılar. Uzun bir aramanın ardından k araştırmacılar 69069 ve 71365 değerleri üzerinde anlaştılar.
Örnek 2'deki verileri kullanan bir rastgele sayı üreteci, 7 milyon periyotlu rastgele, tekrarlanmayan sayılar üretecektir.
Sahte rastgele sayılar üretmek için çarpımsal yöntem, 1949'da D. H. Lehmer tarafından önerildi.
Jeneratörün kalitesini kontrol etme
Tüm sistemin kalitesi ve sonuçların doğruluğu RNG'nin kalitesine bağlıdır. Bu nedenle, RNG tarafından oluşturulan rastgele dizinin bir dizi kriteri karşılaması gerekir.
Yapılan kontroller iki türlüdür:
- dağıtımın tekdüzeliğini kontrol eder;
- İstatistiksel bağımsızlık testleri.
Dağıtımın tekdüzeliğini kontrol eder
1) RNG, tekdüze bir rastgele yasanın karakteristik istatistiksel parametrelerinin aşağıdaki değerlerine yakın üretmelidir:
2) Frekans testi
Frekans testi, bir aralıkta kaç sayının bulunduğunu bulmanızı sağlar (M R σ R ; M R + σ R) yani (0,5 0,2887; 0,5 + 0,2887) veya sonuçta (0,2113; 0,7887) olur. 0,7887 · 0,2113 = 0,5774 olduğundan, iyi bir RNG'de çekilen tüm rastgele sayıların yaklaşık %57,7'sinin bu aralığa düşmesi gerektiği sonucuna varıyoruz (bkz. Şekil 22.9).
frekans testi için kontrol edilmesi durumunda
Ayrıca (0; 0,5) aralığına düşen sayıların sayısının (0,5; 1) aralığına düşen sayıların sayısına yaklaşık olarak eşit olması gerektiğini de dikkate almak gerekir.
3) Ki-kare testi
Ki-kare testi (χ 2 testi) en iyi bilinen istatistiksel testlerden biridir; diğer kriterlerle birlikte kullanılan ana yöntemdir. Ki-kare testi 1900 yılında Karl Pearson tarafından önerildi. Dikkat çekici çalışması, modern matematiksel istatistiğin temeli olarak kabul ediliyor.
Bizim durumumuz için, ki-kare kriterini kullanarak test yapmak, gerçek RNG, RNG kıyaslamasına yakındır, yani tekdüze dağıtım gerekliliğini karşılayıp karşılamadığı.
Frekans diyagramı referans RNG Şekil 2’de gösterilmektedir. 22.10. Referans RNG'nin dağıtım yasası tekdüze olduğundan, (teorik) olasılık P Ben sayıları içine almak Ben inci aralık (tüm bu aralıklar k) eşittir P Ben = 1/k . Ve böylece her birinde k aralıklarla vuracak düzİle P Ben · N sayılar ( N oluşturulan toplam sayı sayısı).
Gerçek bir RNG, ülke genelinde dağıtılan (ve mutlaka eşit olması gerekmeyen!) sayılar üretecektir. k aralıklar ve her aralık şunları içerecektir N Ben sayılar (toplamda N 1 + N 2 + N k = N ). Test edilen RNG'nin ne kadar iyi olduğunu ve referans olana ne kadar yakın olduğunu nasıl belirleyebiliriz? Ortaya çıkan sayı sayısı arasındaki kare farklarını dikkate almak oldukça mantıklıdır. N Ben ve "referans" P Ben · N . Bunları toplayalım ve sonuç:
χ 2 deneyim = ( N 1 P 1 · N) 2 + (N 2 P 2 · N) 2 + + ( N k P k · N) 2 .
Bu formülden, terimlerin her birindeki fark ne kadar küçük olursa (ve dolayısıyla χ2 exp.'nin değeri ne kadar küçük olursa), gerçek bir RNG tarafından oluşturulan rastgele sayıların dağılım yasasının tekdüze olma eğiliminde olduğu sonucu çıkar.
Önceki ifadede terimlerin her birine aynı ağırlık (1'e eşit) atanmıştır; bu aslında doğru olmayabilir; bu nedenle ki-kare istatistikleri için her birinin normalleştirilmesi gerekir Ben inci terime bölerek P Ben · N :
Son olarak ortaya çıkan ifadeyi daha kompakt bir şekilde yazalım ve basitleştirelim:
Ki-kare testi değerini elde ettik deneysel veri.
Masada 22.2 verilmiştir teorik ki-kare değerleri (χ 2 teorik), burada ν = N 1 serbestlik derecesinin sayısıdır, P bu, RNG'nin tekdüze dağıtım gerekliliklerini ne kadar karşılaması gerektiğini gösteren, kullanıcı tarafından belirlenen bir güven düzeyidir veya P χ 2 exp'nin deneysel değerinin olasılığıdır. tablodaki (teorik) χ 2 teorisinden daha az olacaktır. veya ona eşit.
| Tablo 22.2. χ 2 dağılımının bazı yüzde noktaları |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| p = %1 | p = %5 | p = %25 | p = %50 | p = %75 | p = %95 | p = %99 | |
| ν = 1 | 0.00016 | 0.00393 | 0.1015 | 0.4549 | 1.323 | 3.841 | 6.635 |
| ν = 2 | 0.02010 | 0.1026 | 0.5754 | 1.386 | 2.773 | 5.991 | 9.210 |
| ν = 3 | 0.1148 | 0.3518 | 1.213 | 2.366 | 4.108 | 7.815 | 11.34 |
| ν = 4 | 0.2971 | 0.7107 | 1.923 | 3.357 | 5.385 | 9.488 | 13.28 |
| ν = 5 | 0.5543 | 1.1455 | 2.675 | 4.351 | 6.626 | 11.07 | 15.09 |
| ν = 6 | 0.8721 | 1.635 | 3.455 | 5.348 | 7.841 | 12.59 | 16.81 |
| ν = 7 | 1.239 | 2.167 | 4.255 | 6.346 | 9.037 | 14.07 | 18.48 |
| ν = 8 | 1.646 | 2.733 | 5.071 | 7.344 | 10.22 | 15.51 | 20.09 |
| ν = 9 | 2.088 | 3.325 | 5.899 | 8.343 | 11.39 | 16.92 | 21.67 |
| ν = 10 | 2.558 | 3.940 | 6.737 | 9.342 | 12.55 | 18.31 | 23.21 |
| ν = 11 | 3.053 | 4.575 | 7.584 | 10.34 | 13.70 | 19.68 | 24.72 |
| ν = 12 | 3.571 | 5.226 | 8.438 | 11.34 | 14.85 | 21.03 | 26.22 |
| ν = 15 | 5.229 | 7.261 | 11.04 | 14.34 | 18.25 | 25.00 | 30.58 |
| ν = 20 | 8.260 | 10.85 | 15.45 | 19.34 | 23.83 | 31.41 | 37.57 |
| ν = 30 | 14.95 | 18.49 | 24.48 | 29.34 | 34.80 | 43.77 | 50.89 |
| ν = 50 | 29.71 | 34.76 | 42.94 | 49.33 | 56.33 | 67.50 | 76.15 |
| ν > 30 | ν + sqrt(2 ν ) · X P+ 2/3 · X 2 P 2/3 + Ö(1/sqrt( ν )) | ||||||
| X P = | 2.33 | 1.64 | 0,674 | 0.00 | 0.674 | 1.64 | 2.33 |
Kabul edilebilir sayılır P %10'dan %90'a.
Eğer χ 2 exp. χ 2 teorisinden çok daha fazlası. (yani P büyük), sonra jeneratör tatmin etmiyor gözlemlenen değerler nedeniyle tekdüze dağılım gereksinimi N Ben Teorik olmaktan çok uzaklara gitmek P Ben · N ve rastgele kabul edilemez. Yani o kadar büyük bir güven aralığı oluşturuluyor ki sayılara ilişkin kısıtlamalar çok gevşek oluyor, sayılara ilişkin gereksinimler zayıflıyor. Bu durumda çok büyük bir mutlak hata gözlenecektir.
D. Knuth bile “Programlama Sanatı” adlı kitabında χ 2 exp. küçük olanlar için genel olarak da iyi değil, ancak bu ilk bakışta tekdüzelik açısından harika görünüyor. Aslında, 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, 0,7, 0,8, 0,9, 0,1, 0,2, 0,3, 0,4, 0,5, 0,6 sayı dizisini alın, bunlar tekdüzelik açısından idealdir ve χ 2 deneyim neredeyse sıfır olacaktır, ancak bunları rastgele olarak tanımanız pek mümkün değildir.
Eğer χ 2 exp. χ 2 teorisinden çok daha az. (yani P küçük), ardından jeneratör tatmin etmiyor gözlemlenen değerler nedeniyle rastgele tekdüze bir dağılım gereksinimi N Ben teoriye çok yakın P Ben · N ve rastgele kabul edilemez.
Ama eğer χ 2 exp. χ 2 teorisinin iki değeri arasında belirli bir aralıkta yer alır. örneğin şuna karşılık gelir: P= %25 ve P=%50 ise sensörün ürettiği rastgele sayı değerlerinin tamamen rastgele olduğunu varsayabiliriz.
Ayrıca tüm değerlerin dikkate alınması gerekir. P Ben · N yeterince büyük olmalıdır, örneğin 5'ten fazla (deneysel olarak bulunmuştur). Ancak o zaman (yeterince büyük bir istatistiksel örnekle) deneysel koşulların tatmin edici olduğu düşünülebilir.
Yani doğrulama prosedürü aşağıdaki gibidir.
İstatistiksel bağımsızlık testleri
1) Sıradaki sayıların görülme sıklığının kontrol edilmesi
Bir örneğe bakalım. Rastgele sayı 0,2463389991, 2463389991 rakamlarından oluşur ve 0,5467766618 sayısı, 5467766618 rakamlarından oluşur. Rakam dizilerini bağladığımızda, elimizde: 24633899915467766618 bulunur.
Teorik olasılığın açık olduğu açıktır. P Ben kayıp Ben 0'dan 9'a kadar olan rakam 0,1'e eşittir.
2) Aynı sayı serisinin görünümünün kontrol edilmesi
ile belirtelim N L uzunluktaki bir satırdaki aynı rakam serisinin sayısı L. Her şeyin kontrol edilmesi gerekiyor L 1'den M, Nerede M bu, kullanıcı tarafından belirlenen bir sayıdır: bir seride oluşan maksimum aynı basamak sayısı.
“24633899915467766618” örneğinde uzunluğu 2 (33 ve 77) olan 2 seri bulunmuştur, yani N 2 = 2 ve 2 uzunluğunda 3 serisi (999 ve 666), yani N 3 = 2 .
Bir dizi uzunluğun ortaya çıkma olasılığı L eşittir: P L= 9 10 L (teorik). Yani, bir karakter uzunluğunda bir dizinin oluşma olasılığı şuna eşittir: P 1 = 0,9 (teorik). İki karakterden oluşan bir serinin ortaya çıkma olasılığı: P 2 = 0,09 (teorik). Üç karakterden oluşan bir serinin ortaya çıkma olasılığı: P 3 = 0,009 (teorik).
Örneğin bir karakter uzunluğundaki bir dizinin oluşma olasılığı P L= 0,9, çünkü 10 sembolden yalnızca biri olabilir ve toplamda 9 sembol vardır (sıfır sayılmaz). Ve iki özdeş "XX" sembolünün arka arkaya gelme olasılığı 0,1 · 0,1 · 9'dur, yani "X" sembolünün ilk sırada görünme olasılığı 0,1, ilk konumda görünme olasılığı 0,1 ile çarpılır. aynı sembol ikinci "X" konumunda görünecek ve bu kombinasyonların sayısı 9 ile çarpılacaktır.
Serilerin oluşma sıklığı, daha önce tartıştığımız ki-kare formülü kullanılarak hesaplanır. P L .
Not: Jeneratör birden fazla kez test edilebilir ancak testler tamamlanmaz ve jeneratörün rastgele sayılar ürettiğini garanti etmez. Örneğin, 12345678912345 dizisini üreten bir jeneratör, testler sırasında ideal kabul edilecektir ki bu kesinlikle tamamen doğru değildir.
Sonuç olarak, Donald E. Knuth'un Programlama Sanatı (Cilt 2) adlı kitabının üçüncü bölümünün tamamen rastgele sayıların incelenmesine ayrıldığını not ediyoruz. Rastgele sayılar üretmeye yönelik çeşitli yöntemleri, istatistiksel rastgelelik testlerini ve düzgün dağıtılmış rastgele sayıların diğer rastgele değişken türlerine dönüştürülmesini inceler. Bu materyalin sunumuna iki yüzden fazla sayfa ayrılmıştır.
