Discussione sul pi greco

arulbero (OP)

Legendary

Offline

Activity: 1915
Merit: 2074

Discussione sul pi greco

March 04, 2015, 02:43:27 PM
Last edit: March 15, 2015, 09:32:29 PM by HostFat

Cerco un programmatore disposto a modificare (o sarebbe meglio dire a riscrivere

) un mio piccolissimo programmino (< 100 righe di codice!). Ovviamente pago in btc.

Il programmino in questione non c'entra nulla con il mondo bitcoin, è una semplice implementazione del metodo Monte Carlo per la stima del valore di pi greco.

L'idea è molto semplice, il programma genera dei "punti" casuali nel primo quadrante del piano cartesiano (una coppia di variabili pseudo-casuali comprese tra 0 e 1). Tutti questi punti quindi cadono necessariamente in un quadrato immaginario di vertici (0,0),(1,0),(1,1),(0,1). Poi il programma calcola quanti di questi punti cadono anche nel settore circolare (x^2 + y^2 <= 1,x>=0, y>=0). Se genero molti punti, il rapporto tra il numero di punti che cadono nel quarto di cerchio e quelli totali che cadono nel quadrato è all'incirca uguale al rapporto tra le aree delle due figure, cioè pigreco / 4.

Qui di seguito l'algoritmo di base del programma (è in Pascal):

Code:

for i:=1 to num_punti do
          begin
               x:= random ;
               y:= random ;

               if (x*x+y*y<1.0) then num_centri:=num_centri+1;
          end;


          num_centri_reale:=num_centri;
          num_punti_reale:=num_punti;

          stima_pi_greco:=4.0*num_centri_reale/num_punti_reale;
          writeln('');
          writeln('Stima di Pi greco dopo ',i,' punti: ', stima_pi_greco:1:9);

          pi_greco:=3.1415926535;
          writeln('Valore esatto Pi greco:                 ', pi_greco:1:9);

Il programma di per sè funziona, volevo farne però una versione "multithread"*; non mi intendo affatto di questa tecnica di programmazione e per questo chiedo l'aiuto di qualcuno che se ne intenda.

(*Ho dato un'occhiata a questo http://wiki.freepascal.org/Multithreaded_Application_Tutorial e ho capito che non ho il tempo/voglia di studiarmi da solo la cosa).

Grazie.

davvo

Hero Member

Offline

Activity: 588
Merit: 500

⇾ Re: [CERCO PROGRAMMATORE]

March 04, 2015, 04:17:15 PM

Non ho capito sinceramente se lo volevi per forza in pascal o ti andava bene qualsiasi linguaggio.

Ora, se lo volevi in pascal passo, non è il mio linguaggio.
Se ti va bene in altro (vedi php) ti ho messo giù una bozza.

Certo, non è ottimizzata nella comunicazione tra i thread (scrivono su un file alla fine, non proprio bello ma funzionale).
Il programma sembra funzionare e sfrutta tutte le cpu di cui disponi in modo parallelo per fare la "pioggia" di puntini all'interno del quadrato. Ogni thread fa la sua pioggia e poi si sommano i valori.

Il codice è il seguente, commentato, dovrebbe esser semplice da capire:

Code:

<?php

$approx_decim = 10000000;  // Approssimazione dei numeri, con 10 i punti vanno da 0.0 a 1.0 mentre con 100 uso due cifre decimali e cosi via
$num_punti = 10000000; // Numero di punti (pioggia) che ogni thread deve generare
$num_thread = 4; // Numero di thread da usare
$tot = 0; // Totale dei punti interni

for ($i = 1; $i <= $num_thread; ++$i) {
	// Genero i figli
	$pid = pcntl_fork(); 
	if (!$pid) {
		// Per ogni figlio chiamo la funzione
		$tmp = calcola($num_punti, $approx_decim);
		// E scrivo il risultato su file
		file_put_contents("result.txt", "$tmp*", FILE_APPEND | LOCK_EX);
		exit($i); 
	} 
} 

// Aspetto la fine di tutti i figli
echo "Ho lanciato tutti i figli, aspetto la fine....\n";
while (pcntl_waitpid(0, $status) != -1) { 
	$status = pcntl_wexitstatus($status); 
	echo "Figlio numero $status terminato\n"; 
}

// Quando ogni figlio ha finito
echo "Hanno finito tutti i figli, faccio la somma...\n";
// Leggo il contenuto del file
$tmp = file_get_contents("result.txt");
// Cancell il file
unlink("result.txt");
// Divido il file in array
$tmp = explode("*", $tmp);
// Elimino l'ultimo elemento che e' sempre vuoto
array_pop($tmp);

// Stampo i risultati di ogni thread
echo "\nPer ogni thread questi sono i punti interni:\n";
print_r($tmp);
// Sommo i punti interni di ogni thread (quelli esterni sono ugauli a $num_thread per $num_punti
foreach($tmp as $v)
	$tot += $v;

// Calcolo pigreco
$pig = 4*$tot/($num_thread*$num_punti);
// Ti stampo il risultato mettendo un speratore di centinaia nel numero di thread per bellezza :)
echo "\nValore esatto Pi greco dopo ".number_format(($num_thread*$num_punti),0,"",".")." di cui interi ".number_format($tot,0,"",".")." viene $pig\n";



// Alla funzione passo quanti punti calcolare (prima parametro) e l'appossimazione decimale (con 100 i punti interni vanno da 0.00 a 1.00)
function calcola($num_punti, $approx_decim){
	$num_centri = 0;
	for($i = 0; $i < $num_punti; $i++){
		$x = rand(0, $approx_decim) / $approx_decim;
		$y = rand(0, $approx_decim) / $approx_decim;

		if ((($x*$x)+($y*$y)) < 1.0)
			$num_centri += 1;
	}
	return $num_centri;
}

?>

Come detto, dove lo lanci crea un file result.txt in cui scrivo i vari risultati.
Basta che lo prendi, lo salvi su un qualsiasi server unix (windows è più complicato da usare come thread per php) e lo lanci con php5-cli.

L'output che genera è il seguente:

Code:

root@x:/tmp$ php pigreco.php
Ho lanciato tutti i figli, aspetto la fine....
Figlio numero 3 terminato
Figlio numero 4 terminato
Figlio numero 1 terminato
Figlio numero 2 terminato
Hanno finito tutti i figli, faccio la somma...

Per ogni thread questi sono i punti interni:
Array
(
    [0] => 7853664
    [1] => 7854466
    [2] => 7853005
    [3] => 7854225
)

Valore esatto Pi greco dopo 40.000.000 di cui interi 31.415.360 viene 3.141536

golikcoin

Legendary

Offline

Activity: 952
Merit: 1000