Konuyu Paylaş : facebook gplus twitter

Konuyu Oyla:
  • Derecelendirme: 0/5 - 0 oy
  • 1
  • 2
  • 3
  • 4
  • 5
Rastgele Sayı Üretimi Random Number Generation.
#1
Information 
C kursunda rastgele sayı üretimi ile ilgili dersten aldığım notlar.


RASTGELE SAYI ÜRETİMİ
Rastgele sayı üretimi programlama da çok yerde kullanılıyor.
Sadece matematiğin bir konusu değil programlama da çok sık kullanılan bir araç
Mesela nerelerde kullanılıyor rastgele sayı üretimi oyunlar (nerdeyse bütün oyunlar da rastgele sayı üretimi söz konusu), şifreleme (encryption), Genetik algoritmalar, simülasyon, test işlemleri
 
Örnek: Bir kod yazıldı test edilmesi gerekiyor siz milyonlarca kişinin datasını girmeniz gerekiyor nereden bulacaksınız milyonlarca kişinin datasını ama rastgele sayı üretimin de bunu bir şekilde çözümleyebilirsiniz.
En basit oyunlardan Tetris şekiller neye göre geliyor rastgele sayı üretimine göre geliyor.
Genetik algoritmalar ağırlıklı olarak rastgele sayı üretimi ile ilgili mesela.
 
Bunlardan önce tartışılması gereken bir şey var işin biraz matematiksel tarafını anlamamız gerekiyor
1. Soru şu rastgele sayı üretimi ne demek mesela ben size şöyle bir soru sorsam bana ne dersiniz 6 bu rastgele bir sayımı
Cevap: Soru saçma bir sayının rastgele olup olmaması için bir sayı sekansı olması gerekiyor 6 rastgele bir sayımı diyemezsiniz 6’nın rastgele bir sayı olup olmaması ne ile ilgili bir sekans içerisinde yer alıp almaması ile ilgili

Mesela soru şu şekilde sorulmuş olsaydı:
 6-6-6-6-6-6-6-6-6-6-? soru işaretli yere hangi sayı gelecek deseydik bir çok kişi bakınca 6 derdi; bu 6 bu 6 e o zaman buda 6 gelecek diyebiliyoruz rastgelelik bu anlamda ne ile  ilgili öngörülememezlik ile ilgili demek ki rastgeleliğin bizim için en kısa en öz tanımı ne öngörülememezlik bir sekans içinde ki öngörülememezlik bir sayı sekansına bağlı olarak  yeni bir sayının önceden ne olacağı beli ise o zaman orada bir rastgelelik söz konusu değil.
 Demek ki  rastgelelik öngörülememezlik ile ilgili öngörülememezlik ne kadar yüksekse entropi ne kadar yüksekse rastgelelik o kadar yüksek demektir.
 
 2 ayrı rastgele sayı üretiminden bahsediyoruz.
 1) True random number generation (Gerçek rastgele sayı üretimi)
 2) Pseudo random number generation (Sözde rastgele sayı üretimi)
 
 True burada gerçek anlamda gerçek rastgele sayı üretimi diğeri sözde rastgele sayı üretimi aslı gibi ama aslı olmayan
 
 İkisi arasında ki fark ne
 True random generation doğadan gelen bir rastgelelik arkasında matematiksel bir süreç yok burada rastgeleliğin kaynağı doğanın kendisi ya da öngörülememezlik matematiksel bir süreçle üretilen bir öngörülememezlik değil.
Mesela bir örnek; Bir akvaryum olsa akvaryum içinde bir Japon balığı olsa sizden de bir kod yada bir kişi rastgele sayı istese dese ki bana 0 ile 5 arasında rastgele bir sayı ver her istediğinde sizde balığa bakıyorsunuz sola giderse 0 sağa giderse 1 yukarı giderse 2 aşağı giderse 3.Her bir dakika da bir ne yöne gittiğine bağlı olarak bir sayı veriyorsunuz eğer yemleme zamanı değilse balığın ne yöne gideceğini tahmin edebilir misiniz hayır artı burada önemli olan şu diyelim böyle bir yöntemle X kişisi benden istedi bende ondan sayı sekansını verdim 0,1,1,2,0,1,1,0... ertesi gün tekrar istese ben tekrar aynı sayıları verebilir miyim hayır çünkü balık aynı yolu izlemek zorunda değil ama sözde rastgelelik böyle değil!
Sözde rastgelelik şu; rastgele izlenimi veren bir sayı sekansı var ama arkada matematiksel bir süreç var matematiksel süreç derken kastedilen şu aynı süreç tekrar edildiğinde aynı sayıları elde etme garantisi var aynı süreç tekrar edildiğinde aynı sayılar üretilecek.
 
 Mesela Tipik bir örnek: Benden rastgele bir sayı istendiğinde 
646223567 bu sayının karesini alacağım aldığımda oda = 417604898546203500 baştan ve sondan  4 basamağı sileceğim ortadaki 0489854620 bu sayıyı ilk rasgele sayı olarak isteyen kişiye verdim şimdi benden bir daha rastgele sayı istiyor en son verdiğim sayının (0489854620) da karesini alıyorum oda 239957548735344400 buna da aynı işlemi uyguluyorum 5754873534 bunu da isteyen kişiye verdim her rastgele sayı istediğinde bu işlemi tekrar ediyorum  yani benden her rasgele sayı istendiğinden en son elimde kalan sayının karesini alıp baştan ve sondan 4 basamağı silip veriyorum.
Başka bir zaman benden yine rastgele sayı isterse yine bu değerden (646223567) başlayıp yine bu süreç tekrar edersem aynı sayıları elde ederim değil mi? işte bu sözde rastgele sayı üretimi ortada doğaya bağlı bir faktör yok.
Yazılım sal süreçler söz konusu olduğunda aslında çoğu zaman bahsedilen sözde rasgele sayı üretimi, random number generation denildiğinde aslında bahsedilen sözde rasgele sayı üretimi olur.
 Soru: Peki gerçek rasgele sayı üretimi de kullanıyor mu?
 Cevap: Tabi ki öyle yerler var ki sözde rastgele sayı üretiminin bir takım dezavantajı olduğu için gerçek rasgele sayı üretimine ihtiyaç duyuyorsunuz şifreleme vs. gibi durumlarda
 Peki, nasıl üretiliyor rasgele sayı üretimi en tipik yollardan biri Atmospheric noise atmosferde ki gürültüyü ölçmekle ilgili rasgele sayı üretilebiliyor bunla ilgili cihazlar falan var.
Yeni bilgisayarların çoğunda Gerçek sayı üretimine yakın rasgele sayı üretimi imkanı var mesela ne yapıyor keyboard’u takibe alıyor keyboardan tuşların basılması arasında ki zamansal farkları alıyor çünkü keyboard’ı kullanan ne yazacak onu bilmek mümkün değil dimi? Oradan bir rastgele sayı üretimi yoluna gidiyor bu neden gerçek rastgele sayı üretimine yakın çünkü keyboard’ı her gün farklı şekilde kullanılabilir değil mi? mesela şöyle yapanlar var işlemcide yada elektronik bazı componentler de ısınmayı baz alıp oradan rastgele sayı üretimi yoluna gidiyor, ama burada ki en büyük gelişme şu eskiden bu çok daha zorluydu şimdi artık 50$ 100$ mertebesinde gerçek rasgele sayı üreticisi satın alabiliyorsunuz bu konuda satın alınabilecek cihazlar var.
  
Biz gerçek sayı üretimini bırakalım sözde rastgele sayı üretimine geri dönelim.
Sözde rastgele sayı üretilen sayıların ne derece rastgele olduğunu matematiksel olarak ölçmeniz mümkün, yani entropi nin ne olduğunu ölçmeniz mümkün burada gerçekten çok başarılı algoritmalar var.
Mesela mersenne twister algoritması var endüstri de en çok kullanılan algoritma sözde rasgele sayı üretimi için eğer siz bu algoritmayı kullanarak rastgele sayı üretirseniz rastgele ligi bir hayli yüksek yani son derece başarılı.
Böyle onlarca algoritma var bu algoritmayı veya bu algoritmalardan herhangi birini kullanarak rastgele sayı üreten sisteme teknik olarak engine deniliyor. Random number generation engine den kısaltma yani bizim sözde rastgele sayı üretimi için neye ihtiyacımız var bir motora ihtiyacımız var yani işlem yapan bir koda ihtiyacımız var o kod çalışacak arka planda matematiksel bir süreçte size sürekli rastgele sayı verecek o motorun ne kadar başarılı olduğu ölçülebilir.
Şimdi son derece başarılı bir motor olabilir ama bir kriter daha var Hız motor o kadar çok işlem yapıyordur ki sizin bu sayılara çok hızlı ihtiyacınız vardır ve yavaş kalıyor olabilir demek ki birçok parametre var.
Rastgele ligin ne kadar yüksek olduğu bir parametre bir başka parametre de bu değerleri elde etmek için yapılması gereken hesaplamalar ne kadar zamanda oluyor
Mesela dev gibi matrisleri bir biri ile çarpıyorsam çok fazla zaman alır değil mi ama son derece başarılı entropisi yüksek bir rastgele sayı sekansı size verebilir.
Bilmemiz gereken önemli bir noktada rastgele sayı üretimi ile dağılımı bir biri ile karıştırmamak (distribution) rastgele sayı üreten motor yani kod aslında sadece neden sorumlu 1 leri 0 ları üretmekten sorumlu yani rastgele sayı üreticisinin yaptığı size böyle bir sekans vermek burayı anlamak çok önemli şimdi burada ki 1 leri ve 0 ları üretilecek rastgele sayıya dönüştürmek kimin görevi distribution kodunun görevi o bambaşka bir modül.
Mesela sizin istediğiniz rastgele sayıların sizi ilgilendiren özelliğinin ne olduğuna bağlı olarak o distribution değişebilir mesela bir oyun programını ele alalım zar la oynanan bir oyun programı olsun oyunun başarılı olması için gerçek hayata hilesiz bir zar nasılsa burada da 6 gelme olasılığının 1/6 olması gerekir değil mi? İstediğimiz buysa iyi bir distribution kodu ne yapmalı burada elde edilen rastgele sayıları 1-6 arasında uniform bir şekilde dağıtmalı buna mesela uniform distribution deniliyor ama başla bir örnek verelim siz şimdi bir test datası hazırlayacaksınız bir test datasında insanların boyları kiloları gibi veriler var şimdi siz uniform dağılım uygulasanız insanların boyları hangi aralıkta diyelim sizin istediğiniz değer şu 1.40 ila 2.10 şimdi uniform dağıtılsa çok komik bir şey olur değil mi uniform dağılım ne demek 1.40 boyun da kaç kişi varsa 2.10 boyunda da o kadar kişi olacak ama doğada ki bu tür dağılımlar normal dağılım dediğimiz dağılıma uyuyor yani ortalama etrafında bir yığılma var ortalamadan uzaklaştıkça miktar azalıyor böyle onlarca farklı dağılım modeli var dolayısı ile ortada bir problem daha var çoğu zaman üretilen rastgele sayıları yani bu 0 1 bitlerini uygun bir dağılımla rastgele sayılara dönüştürmek.
Başka bir örnek şimdi siz bu sefer hileli bir tavla oyunu oynatmak istiyorsunuz iyi niyetle veya kötü niyetle mesela size daha fazla 6 gelsin ama rakibinize daha az 6 gelsin e bu durumda 6 gelme olasılığını 1,2,3,4,5 gelme olasılığından daha fazla olması gerekiyor hata bunu sayısal bir şekilde de ayarlayabilirsiniz diyebilirsiniz ki %2 oranın da 6 daha fazla gelsin veya %1 oranın da 6 daha fazla gelsin o zaman arkada ki kodun ne yapması gerekiyor burada ki 1’leri ve 0’ları öyle bir şekilde rastgele dağıtacak ki uniform dağıtsaydı hepsi büyük bir zar atma sayısı için örneğin bir milyar kere zar atıldığında hepsi 1/6 ya yakınsayacaktı ama şimdi 6  1,2,3,4,5 ten daha fazla olacak.
 
Şimdi bunlar rastgele sayı üretimi ile ilgili temel bilgiler rastgele sayı üretimi ne? Gerçek rastgele sayı üretimi ne? Sözde rastgele sayı üretimi ne? Rastgele sayı nasıl üretiliyor? Dağılım nedir?
Gelelim şimdi programlama dili ile ilgili kısmına programlama dillerinin standart kütüphaneleri rastgele sayı üretimi konusun da az ya da çok destek veriyorlar tipik olarak mesela C dilinde verilen destek yok denilecek kadar az standart olarak verilen destek çünkü son derece primitif bir rastgele sayı üreticisi söz konusu C’ de yani imkânlar çok dar ama C++ a geldiğiniz de C++ ın random isimli standart bir kütüphanesi var bu kütüphane de 20 farklı rastgele sayı motorunu hazır olarak kullanabiliyorsunuz ben mersenne twister algoritmasını kullanmak istiyorum diyorsunuz mersenne twister algoritması hazır yine 20 civarı dağılımı hazır olarak verebiliyor yani az evvelki hileli zar oyununu c++ yazıyor olsak harici bir kütüphaneye ihtiyacımız olmayacak.
Ama C’ de olanak çok ilkel ama bunun ilkel yada kötü olması hiçbir işe yaramayacağı anlamına gelmiyor rastgeleliğin yüksek olması gereken yerde bunu kullanmanız kesinlikle önerilmez ve sizin işinize de yardımcı olmaz.
 
Rastgele sayı üretiminde çok önemli terimlerden biri seed value Türkçeye çevirirsek tohum değeri. Yukarıda ki karesini aldığımız ilk sayı olan 646223567 bizim seed value muz ilk değere tohum değeri deniyor bu şu demek bu tohum değerini kullanacağım zaman hep aynı rastgele sayı zincirini üreteceğim (algoritma sabit kalmak üzere) garanti altında.
 
X kişisine bir milyar sayı versem 1 gün sonra Y kişisine aynı seed value ile bir milyar sayı versem aynı sekansa sahip rastgele sayı vermiş olacağım.

Bu durumda bizim tohum değerimiz 0 ila 65535 sayı aralığında değişiyorsa bu kaç farklı sayı zinciri elde edebiliriz demek 65535 ayrı sayı zinciri edebiliriz demek ama bizim tohum değerimiz 10 tane olsaydı bu çok kolay çözülürdü deneme yanılma yoluyla çok rahat çözülebilirdi.
Ama şimdi tohum değerinin 4 byte işaretsiz tam sayı sınır değerinde olduğunu düşünelim bu ne demek 4294967295 rastgele sayı zinciri olacak mesela bunun yazılımsal yolla üretilecek sayının kaç olacağını anlamaya çalışacak kodun toplamda kaç deneme yapması gerekiyor 4294967295 adet deneme yapması gerekiyor ama kullanılan tohum değeri 8 byte işaretsiz tam sayı sınırında olsaydı bu durumda da 18446744073709551615 (onsekiz kentilyon dörtyüzkırkaltı katrilyon yediyüzkırkdört trilyon yetmişüç milyar yediyüzdokuz milyon beşyüzellibir bin altıyüzonbeş) olacaktır.

“Do. Or do not. There is no try.”
Cevapla

Konuyu Paylaş : facebook gplus twitter





Konuyu Okuyanlar: 1 Ziyaretçi