Bir Algoritma Bağlamında Güzellik ve Performans – I

Monte Carlo metodu, algoritmik çözümü zor olan matematiksel ve fiziksel problemleri, rastgele (random) sayılar üreterek, simule ederek çözmeyi amaçlayan yaklaşımlara verilen ortak addır. Monte Carlo’daki gazinolardaki kumar aletlerinin rastgele sonuç üretmesine atıf olarak bu isim verilmiştir. Optimizasyon problemlerinde sıklıkla kullanılır.

Monte Carlo metodunu, pi sayısını bulmak için de kullanabiliriz. Bakın şöyle: Kartezyen koordinat sisteminde merkezi (0,0) noktasında olan ve yarı çapı 1 birim olan bir çember çizin ile bu çembere teğet geçen bir de kare çizin. Çemberin ve karenin alanlarının oranı pi/4 yapar. Bu şu demektir: Bu çizime rastgele bir nokta atarsanız, bu noktanın, çemberin içine düşmesi ihtimali pi/4 eder.

Bu gerçeği tersten okuyalım şimdi de: Eğer bu çizime sonsuz tane nokta atılırsa, bu şekli tamamen kapsamış oluruz. Yani bu şekile n tane nokta atalım ve bu noktaların r tanesinin çemberin içine düştüğünü varsayalım. n sonsuza giderken, 4r/n oranının pi‘ye yaklaştığını görürsünüz. n‘yi 1 yaparsanız, yani 1 nokta atarsanız bu oran ya 0 ya da 4 olacaktır. n sayısını arttırdıkça bu oranın gittikçe pi sayısına yakınsadığını, ne kadar çok nokta atarsanız, pi‘nin gerçek değerine (ki böyle bir şey yok! dolayısıyla daha doğru tabirle, virgülden sonraki rakamları doğru bir şekilde bulmaya başlarsınız) yakınsarsınız. Bu durumu şuradaki ya da şuradaki applet ile görebilirsiniz ya da Youtube’taki pek çok videodan birini seyredebilirsiniz.

Bu algoritmayı Java ile şöyle gerçekleştirebiliriz:

import java.util.Scanner;

public class MonteCarloPI {
	public static void main(String[] args) {
		int dotsInCircle = 0;
		System.out.print("Number of points: ");
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		
		double start = System.currentTimeMillis();
		for(int i = 0; i<n; i++){
			double x = Math.random();
			double y = Math.random();
//			double distance = Math.sqrt(Math.pow(x, 2) + Math.pow(y,2));
			double distance = x*x + y*y;
			if(distance <= 1.0)
				dotsInCircle++;
		}
		double finish = System.currentTimeMillis();
		
		double seconds = (finish-start)/1000;
		double myPI = (double) 4*dotsInCircle/n;
		System.out.println("My PI is: " + myPI + " and Java's PI is: " + Math.PI);
		System.out.println("Time is: " + seconds);
	}
}

Yukarıdaki program, girilen sayı kadar rasgele (x, y) noktası üreterek, her bir noktanın (0, 0) merkez noktasına uzaklığı hesaplanır ve bu uzaklığın 1’e eşit ya da ondan küçük olup olmadığı kontrol edilir, eğer eşit ya da küçük ise, bu demektir ki nokta çemberin içine düşmüştür ve yukarıdaki algoritmanın anlatımında r dediğimiz ve programda dotsInCircle ile temsil ettiğimiz değişkenin değeri arttırılır.

Yukarıdaki kodu n=1 için çalıştırırsanız sonuç ya 0 ya da 4 çıkacaktır. Çünkü o tek nokta ya dairenin içine ya da dışına düşecektir. Dolayısıyla salınım 0 ile 4 arasında gerçekleşecektir. Ama örneğin n=10 yaparsanız gelebilecek sonuçlardan birisi şöyle olabilir: Hesaplanan pi = 2.800000  ve hata yüzdesi %10.873232. Yani yaklaşık %11 hatayla Java’nın Math sınıfındaki PI’ye (3.141592653589793) yakınsanmış demektir. Ama n sayısını 1.000.000.000 yapınca pi = 3.141536  ve hata yüzdesi % 0.001809 olarak elde ettim.

Tabi sağlıklı ortalama değerler için, aynı n sayısı için olarak olabildiğince çok çalıştırma yapılmalıdır. Ben de bu amaçla yukarıdaki algoritmayı aşağıdaki gibi değiştirdim.

package org.javaturk.oop.ch05;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MonteCarloPITiming {
	private static int runCount = 100;
	private static int n;
	
	private static List<Double> pis = new ArrayList<Double>();
	private static List<Double> times = new ArrayList<Double>();
	private static List<Double> percentages = new ArrayList<Double>();
	
	public static void main(String[] args) {
		System.out.print("Number of points: ");
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		for(int i = 0; i < runCount; i++){
			calculatePI();
		}
		printResults();
	}

	private static void printResults() {
		double meanTime = 0;
		double meanError = 0;
		System.out.printf("%10s %10s %10s\n", "Time  ", "Calculated PI", "Error %  ");
		for(int i = 0; i < runCount; i++){
			meanTime += times.get(i).doubleValue();
			meanError += percentages.get(i).doubleValue();
			System.out.printf("%10f %10f %10f\n", times.get(i).doubleValue(), pis.get(i).doubleValue(), percentages.get(i).doubleValue());
		}
		meanTime /= runCount;
		meanError /= runCount;
		System.out.printf("Mean time: %10f\n", meanTime);
		System.out.printf("Mean error: %10f", meanError);
	}

	public static void calculatePI() {
		int dotsInCircle = 0;
		double start = System.currentTimeMillis();
		for (int i = 0; i < n; i++) {
			double x = Math.random();
			double y = Math.random();
			// double distance = Math.sqrt(Math.pow(x, 2) + Math.pow(y,2));
			double distance = x * x + y * y;
			if (distance <= 1.0)
				dotsInCircle++;
		}
		double finish = System.currentTimeMillis();
		double seconds = (finish - start);
		times.add(seconds);
		double myPI = (double) 4 * dotsInCircle / n;
		pis.add(myPI);
		double diff = Math.abs((Math.PI - myPI)); 
		double percentage = diff * 100 / Math.PI;
		percentages.add(percentage);
	}

}

Yani programın başındaki runCount (ki değeri 100) kadar aynı n sayısı için algoritmayı çalıştırıyorum ve her çalışmanın sonuçlarını List nesnelerine koyuyorum. runCount defa çalışma bitince de hem sürenin hem de hata yüzdesinin ortalamasını alıyorum. Beklentim şu: n arttıkça süre de artacak çünkü daha çok nokta atacağım ama tabi olarak hata yüzdesi azalacak çünkü pi‘ye daha çok yakınsayacağım. Örneğin farklı n sayıları için aşağıdaki ortalama ölçümleri elde ettim:

MacBook Pro i7 2,5 GHz. 16 GB RAM, MacOS 10.10.1 Yosemite konfigürasyonunda:

Toshiba Satellite i7 2,4 GHz. 8 GB RAM, Windows 8.1 konfigürasyonunda:

Her iki konfigürasyonda da Java 1.8.0_25 HotSpot 64-bit server JVM çalışıyordu.

Yukarıdaki sonuçlardan şunları söyleyebiliriz:

• Algoritmada n tane for döngüsünün her birinde iki defa Math.random() çağrısı, iki defa çarpma işlemi, bir tane kıyas (<=), bir tane de artım yapılıyor. Dolayısıyla algoritmanın karmaşıklığı 0(n) (bigO(n)) görünüyor. Yani algoritmanın zaman ihtiyacı doğrusal olarak artacaktır. Zaten sonuçlar da bunu gösteriyor. n sayısı 10 katına çıkınca, gerekli süre de yaklaşık 10 katına çıkıyor.
• İkincisi konfigürasyonları çok yakın, JVMleri aynı sürüm olmasına rağmen MacBook Pro, Toshiba’dan yaklaşık %10 civarında daha hızlı çalıştı. Bu durum MacBookPro’daki CPU’nun biraz daha hızlı olması yanında envai çeşit farklı faktörler üzerinden açıklanabilir. Çok önemli bir fark değil açıkçası.

Bu algoritma o kadar basit ki, anlaşılması, kodlanması vs. çok kolay. Ama bu algoritma bir o kadar da güzel, güzel ötesi, neffiiisss. Matematiğin ve sayıların güzelliğini ortaya koyuyor, herkesin anlayacağı basitlikte.

Toplam görüntülenme sayısı: 1124