Ana Sayfa » Ankara Üniversitesi ANKADEM » Mühendislik Fakültesi » Computer Simulation and Modelling

Computer Simulation and Modelling

Ünite 8: Randomnumbers

John von Neumann'ın 1951 Tarihli Uyarısı

Ünlü matematikçi John von Neumann, 1951 yılında yaptığı açıklamada aritmetik yöntemlerle gerçek rastgele sayı üretilemeyeceğini belirtmiş ve bunu deneyenlerin 'günah içinde' olduğunu söyleyerek deterministik bilgisayarların sınırlarına dikkat çekmiştir.

Park ve Miller'ın 1988 Standart Parametreleri

Park ve Miller, 1988 yılında yayınladıkları çalışmada LCG için M = 2147483647 (Mersenne asalı) ve a = 16807 parametrelerini önermişlerdir. Bu kombinasyon, uzun yıllar boyunca birçok sistem kütüphanesinde standart olarak kullanılmıştır.

Robert D. Carmichael'ın 1910 Kanıtı

Matematikçi Robert D. Carmichael, 1910 yılında LCG algoritmalarında maksimum periyodun elde edilebilmesi için modülün Mersenne asalı olması ve a^(M-1) mod M = 1 koşulunu sağlayan en küçük tam sayı a'nın seçilmesi gerektiğini ispatlamıştır.

Marin Mersenne ve 1626 Yılındaki Tanımı

Fransız rahip ve matematikçi Marin Mersenne, 1626 yılında kendi adıyla anılan M_q = 2^q - 1 formülündeki asal sayıları tanımlamıştır. Bu sayılar günümüzde bilgisayarlarda uzun periyotlu rastgele sayı üretiminin temelini oluşturur.

Anahtar Kavramlar

Rastgele Sayı (Random Number)Gelecekteki değerleri tamamen öngörülemez olan ve belirli bir olasılık dağılımından tamamen bağımsız olarak çekilen sayılardır. Doğadaki radyoaktif bozunma gibi fiziksel süreçler gerçek rastgele sayılara örnek teşkil eder.

Sözde Rastgele Sayı (Pseudo-Random Number)Tamamen deterministik matematiksel formüller kullanılarak üretilen ancak istatistiksel olarak gerçek rastgele sayıların özelliklerini taklit eden sayılardır. Başlangıç değeri bilindiğinde tüm dizi tekrar üretilebilir.

Doğrusal Eşlik Yöntemi (Linear Congruential Generator - LCG)x_{n+1} = (a * x_n + c) mod M formülüyle çalışan, bilgisayarlarda en yaygın kullanılan sözde rastgele sayı üretim algoritmasıdır. Parametrelerin seçimi üretecin kalitesini doğrudan etkiler.

Çekirdek Değeri (Seed)Sözde rastgele sayı üreteçlerinin diziyi başlatmak için kullandığı ilk tam sayı değeridir (x_0). Aynı çekirdek değeri kullanıldığında üreteç her zaman aynı sayı dizisini oluşturur.

Maksimum Periyot (Maximum Period)Bir rastgele sayı üretecinin kendini tekrar etmeye başlamadan önce üretebileceği benzersiz sayıların maksimum miktarıdır. LCG için bu değer en fazla modül değeri olan M veya M-1 olabilir.

Mersenne Asalı (Mersenne Prime)q bir asal sayı olmak üzere M_q = 2^q - 1 formülüyle hesaplanan asal sayılardır. LCG algoritmalarında modül (M) olarak seçildiklerinde maksimum periyodun elde edilmesini kolaylaştırırlar.

Modül (Modulus - M)LCG algoritmasında üretilecek sayıların üst sınırını belirleyen ve modüler aritmetikte bölme işleminden kalanı bulmak için kullanılan tam sayı parametresidir. Genellikle bilgisayar mimarisine uygun olarak 2^31 - 1 gibi büyük değerler seçilir.

Çarpan (Multiplier - a)LCG formülünde bir önceki adımda üretilen sayı ile çarpılan tam sayı katsayısıdır. Bu parametre, üretilen sayıların dizilimindeki düzgünlüğü ve periyot uzunluğunu belirlemede kritik rol oynar.

Artış Miktarı (Increment - c)LCG formülünde çarpım işleminden sonra eklenen sabit tam sayı değeridir. Eğer bu değer sıfır seçilirse üreteç çarpımsal eşlik yöntemi olarak adlandırılır.

Donanımsal Rastgele Sayı Üreteci (Hardware RNG)Bilgisayar dışındaki fiziksel dünyadan gelen gürültü, foton emilimi gibi kaotik süreçleri ölçerek çalışan üreteçlerdir. Deterministik olmadıkları için gerçek rastgele sayılar üretirler.

Tekrarlanabilirlik (Reproducibility)Bir rastgele sayı dizisinin aynı başlangıç parametreleriyle tekrar çalıştırıldığında birebir aynı şekilde elde edilebilmesi özelliğidir. Hata ayıklama ve simülasyon doğrulamalarında çok önemlidir.

Düzgün Dağılım (Uniform Distribution)Belirli bir aralıktaki tüm sayıların seçilme olasılığının birbirine eşit olması durumudur. Rastgele sayı üreteçlerinin temel amacı öncelikle [0, 1) aralığında düzgün dağılımlı sayılar üretmektir.

rand() FonksiyonuC programlama dilinde standart kütüphane tarafından sunulan ve LCG algoritmasını kullanarak 0 ile RAND_MAX arasında sözde rastgele tam sayılar üreten fonksiyondur.

srand() Fonksiyonurand() fonksiyonunun kullanacağı başlangıç çekirdek (seed) değerini ayarlayan fonksiyondur. Programın her çalışmasında farklı sonuçlar vermesi için genellikle zaman parametresiyle çağrılır.

RAND_MAXC dilindeki standart kütüphanelerde tanımlı olan ve rand() fonksiyonunun üretebileceği en büyük tam sayı değerini belirten sabit makrodur.

Ortalama Testi (Average Test)Üretilen rastgele sayıların aritmetik ortalamasının teorik değer olan 0.5'e yakınlığını ölçen en temel istatistiksel doğrulama testidir.

Dağılım Testi (Distribution Test)Üretilen sayıların belirlenen alt aralıklara ne kadar homojen dağıldığını ölçen testtir. Her aralıktaki sayı miktarının birbirine yakın olması beklenir.

Kare Testi (Square Test)Ardışık rastgele sayı çiftlerinin iki boyutlu düzlemde noktalar olarak çizilmesiyle yapılan görsel testtir. Sayılar arasında kısa vadeli korelasyon (ilişki) olup olmadığını ortaya çıkarır.

Ki-Kare Testi (Chi-Square Test)Gözlemlenen veri dağılımı ile teorik olarak beklenen dağılım arasındaki farkın istatistiksel olarak anlamlı olup olmadığını denetleyen hipotez testidir.

Spektral Test (Spectral Test)Rastgele sayıların Fourier dönüşümünü alarak frekans boyutunda analiz eden ve dizide gizli periyodik desenler veya tepe noktaları olup olmadığını inceleyen gelişmiş bir testtir.

Üstel Dağılım (Exponential Distribution)Olaylar arasındaki zaman aralıklarını modellemek için kullanılan ve x = -ln(1 - y) dönüşümü ile düzgün dağılımlı sayılardan elde edilebilen sürekli olasılık dağılımıdır.

Normal Dağılım (Normal Distribution)Çan eğrisi şeklinde olan ve doğadaki birçok ölçümün dağılımını temsil eden istatistiksel dağılımdır. Box-Muller dönüşümü kullanılarak düzgün dağılımlı sayılardan üretilir.

Box-Muller Dönüşümüİki bağımsız düzgün dağılımlı rastgele sayı kullanarak, trigonometrik ve logaritmik işlemlerle normal dağılıma sahip iki bağımsız rastgele sayı üreten matematiksel yöntemdir.

Von Neumann Reddetme Yöntemi (Rejection Method)Analitik olarak integrali alınamayan karmaşık olasılık yoğunluk fonksiyonlarından rastgele sayı üretmek için kullanılan, önerilen noktaları belirli bir olasılıkla kabul veya reddeden algoritmadır.

Lagged-Fibonacci ÜreteciTausworth tarafından 1965 yılında önerilen, Fibonacci dizisine benzer şekilde geçmişteki iki veya daha fazla terimin modüler toplamını kullanarak rastgele sayı üreten alternatif bir algoritmadır.

Diğer Önemli Bilgiler

32-Bit Bilgisayarlar ve 2^31 - 1 Modülü

32-bit kelime uzunluğuna sahip bilgisayarlarda M = 2^31 - 1 = 2147483647 değeri, hem bir Mersenne asalı olması hem de donanım sınırlarına tam uyması nedeniyle rand() ve random() fonksiyonlarında standart modül olarak tercih edilir.

Lehmer'in 1948 Yılındaki Buluşu

Doğrusal Eşlik Yöntemi (LCG), ilk kez 1948 yılında Lehmer tarafından geliştirilmiştir. Bu buluş, bilgisayar simülasyonları tarihinde yazılımsal rastgele sayı üretiminin başlangıç noktası olarak kabul edilir.

Tausworth'ün 1965 Alternatifi

Tausworth, 1965 yılında yayınladığı çalışmada LCG'ye alternatif olarak Lagged-Fibonacci üretecini tanıtmıştır. Bu yöntem, özellikle LCG'nin yetersiz kaldığı çok büyük boyutlu simülasyonlarda daha uzun periyotlar sunar.

Knuth'un Programlama Sanatı Kitabı (1997)

Donald Knuth'un ünlü 'The Art of Computer Programming' serisinin 3. baskısında (1997, Cilt 2, Bölüm 3.3.1), sözde rastgele sayı üreteçlerinin matematiksel analizleri ve maksimum periyot koşulları detaylıca incelenmiştir.

Gentle'ın 2003 Tarihli Referans Kitabı

J.E. Gentle tarafından 2003 yılında Springer'den basılan 'Random Number Generation and Monte Carlo Methods' kitabı, simülasyon dünyasında rastgele sayı testleri ve dağılım dönüşümleri konusunda en kapsamlı rehberlerden biridir.

LCG Maksimum Periyot Koşulu 1: gcd(c, M) = 1

Bir LCG üretecinin periyodunun tam olarak M olabilmesi için artış miktarı c ile modül M sayılarının en büyük ortak böleninin 1 olması, yani bu iki sayının aralarında asal olması şarttır.

LCG Maksimum Periyot Koşulu 2: a Mod p = 1

M sayısını bölen her p asal sayısı için, çarpan a değerinin (a mod p) = 1 koşulunu sağlaması gerekir. Bu kural, üretilen sayıların tüm olası değerleri taramasını güvence altına alır.

LCG Maksimum Periyot Koşulu 3: a Mod 4 = 1

Eğer modül M sayısı 4'ün tam katı ise, çarpan a parametresinin (a mod 4) = 1 koşulunu sağlaması zorunludur. Aksi takdirde üreteç tam periyoda ulaşamadan kendini tekrarlamaya başlar.

RAND_MAX ve stdlib.h İlişkisi

C programlama dilinde rastgele sayıların üst sınırını belirleyen RAND_MAX sabiti, stdlib.h kütüphanesinde tanımlıdır. Bu sabit, üretilen tam sayıların [0, 1) aralığına normalize edilmesinde payda olarak kullanılır.

time(NULL) ve time.h Kütüphanesi

C dilinde time.h kütüphanesinde yer alan time(NULL) fonksiyonu, 1 Ocak 1970'ten beri geçen saniye sayısını döndürür. Bu dinamik değer, srand() fonksiyonuna çekirdek olarak verilerek her çalıştırmada benzersiz sayılar üretilmesini sağlar.

Rastgele Sayıların Tarihsel Hataları

Bilimsel literatürde, test edilmeden kullanılan kalitesiz rastgele sayı üreteçleri yüzünden hatalı sonuçlar veren ve araştırmacıları utandıran birçok simülasyon projesi ve akademik yayın bulunmaktadır.

Sınavda Dikkat Et

LCG formülünü (x_{n+1} = (a * x_n + c) mod M) adınız gibi bilin; sınavda parametreler verilip sonraki sayıyı hesaplamanız istenebilir.
c = 0 durumunda seed (x_0) değerinin asla 0 seçilemeyeceğini unutmayın, çünkü bu durum üreteci kilitler.
rand() ve random() fonksiyonlarının varsayılan olarak aynı çekirdek değerini kullandığını ve her çalıştırmada aynı diziyi ürettiğini aklınızda tutun.
Her çalıştırmada farklı sayı üretmek için 'srand(time(NULL))' kalıbının kullanıldığını ve bunun için time.h kütüphanesinin gerektiğini unutmayın.
Düzgün dağılımdan üstel dağılıma geçiş formülünün 'x = -ln(1 - y)' olduğunu ve normal dağılım için Box-Muller dönüşümünün kullanıldığını mutlaka ezberleyin.
Kare Testinin (Square Test) ardışık sayıları (x=r_i, y=r_{i+1}) grafikleyerek kısa vadeli korelasyonları ve paralel çizgileri tespit ettiğini unutmayın.