[C++] Approssimazione di $pi$

Messaggioda Landau » 09/06/2018, 14:09

Salve a tutti, sono alle prese con un nuovo problema di informatica: l'approssimazione di $pi$ con un metodo Monte Carlo.

Allora, l'esercizio si dovrebbe articolare in quattro step. Quello che mi crea più problemi è il primo:

1) Definire una funzione float misuraPi(int nPunti, float a); che, presi in ingresso il numero di punti da utilizzare e il lato a del quadrato centrato nell’origine che include la circonferenza di raggio unitario, restituisca una misura di $pi$.

Infatti non saprei dove mettere le mani per scrivere questa funzione. L'idea sarebbe considerare un generatore di numeri casuali nel quadrato in modo tale che le loro coordinate siano o dentro o fuori la circonferenza unitaria. Da quello che mi ricordo poi il rapporto \(\displaystyle \text{punti nella circonferenza}/\text{punti totali} \) dovrebbe essere un'approssimazione di $pi$. Quindi pensavo di fare così: con un ciclo for, genero una coppia di numeri casuali $(x, y)$ per ogni punto in input, imponendo la condizione $-a/2<x,y<a/2$. Dopodiché calcolo la distanza dall'origine di ciascuno di questi punti e se essa risulta $<=1$ aumento un contatore per i punti che entrano nella circonferenza. Infine esco dal ciclo e calcolo il rapporto.

Questo è quello che mi è uscito:

Codice:
float misurePi(int nPunti, float a){

   float x, y;
   int centri=0;
   for(unsigned int j=0; j<nPunti; j++){
      x=randUnif(-a/2,a/2);
      y=randUnif(-a/2,a/2);
      
      if(distO(x,y)<=1){
         centri++;
      }
   return (float) centri/nPunti;
   }


dove le funzioni randUnif e distO sono definite così:

Codice:
float randUnif(float a, float b){
   if (a==b)
      return a;
   if (a>b){
      float tmp;
      tmp=a;
      a=b;
      b=tmp;
   }

   srand(time(NULL));
   return ((float)rand()*(b-a)/RAND_MAX+a); //oppure rand()%(b-a)+a
}

float distO (float x, float y){
   return sqrt(x*x+y*y);
}


Cosa ne dite, fino a qui può avere senso il procedimento? Nel secondo punto, dovrei salvare un certo numero di misure in un array dinamico:

Codice:
float *esperimentoPi(int nPunti, float a, int nMisure){

   float* results=new float[nMisure];
   for(unsigned int i=0; i<nMisure; i++){
      results[i]=misurePi(nPunti, a);
   }
   return &results;
}


Ho due dubbi essenziali: è corretto usare & per la variabile di return? E quando chiamo la funzione nel main con i parametri attuali, devo mettere l'*?
Landau
Junior Member
Junior Member
 
Messaggio: 38 di 118
Iscritto il: 05/09/2017, 20:42

Re: [C++] Approssimazione di $pi$

Messaggioda Super Squirrel » 09/06/2018, 21:13

Per quanto riguarda il primo punto ci sono varie cose che non mi convincono.

Perché la circonferenza dovrebbe avere raggio unitario?
Bisogna considerare la circonferenza inscritta nel quadrato (che avrà quindi un raggio pari ad a/2), altrimenti non ha senso.

Chiamati n i punti totali e m quelli che ricadono nella circonferenza, il rapporto m/n sarà sicuramente <=1 (essendo n>=m) e quindi non potrebbe in alcun caso essere un'approssimazione di pi che sappiamo essere pari a 3,14.
In pratica l'idea è che il rapporto tra l'area del cerchio e quella del quadrato sia uguale al rapporto tra i punti che ricadono nel cerchio e quelli che ricadono nel quadrato (ossia quelli totali). Quindi:
$ (pi*r^2)/a^2=m/n => pi/a^2*(a/2)^2=m/n=>pi=4*m/n $
Inoltre lo stesso ragionamento vale anche se si considera solo un quadrante e quindi per semplicità conviene operare solo nel primo quadrante dove x e y sono entrambe positive.

Relativamente al codice:
- la funzione srand() va richiamata una sola volta e quindi va messa nel main e non nella funzione randUnif che viene richiamata più e più volte;
- la funzione randUnif l'hai copiata da qualche parte? Lo dico perchè per il caso in questione basta passargli un solo argomento e di conseguenza tutti quei controlli diventano inutili e l'espressione che restituisce il valore di ritorno si semplifica in (float)rand/RAND_MAX*a+a.
Inoltre la suddetta funzione oltre ad essere molto poco random, ritorna solo valori contenuti nell'intervallo [-a;-a/2] che ovviamente non vanno bene. Potresti provare con qualcosa del genere magari:
Codice:
float randUnif(float a)
{
    return rand() % (int)a + (float)rand() / RAND_MAX;
}

E' la prima cosa che mi è venuta in mente, ma sembra funzionare bene. Il valore di ritorno sarà compreso tra 0 e a, e considerando la precedente osservazione relativa al primo quadrante sarebbe già sufficiente, ma se vuoi valori compresi tra -a e a basta aggiungere un if e moltiplicare quel valore per -1 quando (float)rand()/RAND_MAX<0.5;

- per quanto riguarda la funzione distO puoi anche evitare di scomodare la radice quadrata controllando semplicemente che sia x^2+y^2<=r^2.

EDIT:
La formula che ho postato funziona bene solo se il valore di a è intero, altrimenti non restituisce valori maggiori della parte intera di a. Per esempio per a=3.4 non va oltre 3.
Qualche idea per aggiustarla ce l'avrei, nel caso domani provo a metterla in pratica.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 224 di 1486
Iscritto il: 16/05/2013, 22:05

Re: [C++] Approssimazione di $pi$

Messaggioda Landau » 10/06/2018, 14:22

La funzione randUnif l'ho presa da un vecchio esercizio. L'idea sarebbe di avere una funzione che mi restituisca un numero casuale compreso tra due numeri fissati, in questo caso voglio che le coordinate $x$ e $y$ del mio punto siano comprese tra $-a/2$ e $a/2$. Non capisco perché non dovrebbero essere casuali i numeri ottenuti... l'unica modifica che mi viene in mente è scrivere return rand()%(b-a)+a; nel modo più semplice possibile.

Hai ragione per quanto riguarda il fatto che una circonferenza unitaria non avrebbe molto senso, però così recita il testo del problema. :| Quindi a questo punto dovrei considerare come raggio la metà del lato. Il codice diventa così:

Codice:
float misuraPi(int nPunti, float a){

   float x, y;
   int centri=0;
   for(unsigned int j=0; j<nPunti; j++){
      x=randUnif(-a/2,a/2);
      y=randUnif(-a/2,a/2);
      
      if(distO(x,y)<=a/2){
         centri++;
      }
   }
   return (float) 4*centri/nPunti;
   }

float randUnif(float a, float b){
   if (a==b)
      return a;
   if (a>b){
      float tmp;
      tmp=a;
      a=b;
      b=tmp;
   }

   return ((float)rand()*(b-a)/RAND_MAX+a);

float distO (float x, float y){
   return sqrt(x*x+y*y);
}


Però testandolo il codice restituisce subito zero (un main in cui stampo soltanto la funzione) quindi c'è qualcosa che non torna :?
Landau
Junior Member
Junior Member
 
Messaggio: 40 di 118
Iscritto il: 05/09/2017, 20:42

Re: [C++] Approssimazione di $pi$

Messaggioda Super Squirrel » 10/06/2018, 20:06

La funzione randUnif l'ho presa da un vecchio esercizio. L'idea sarebbe di avere una funzione che mi restituisca un numero casuale compreso tra due numeri fissati, in questo caso voglio che le coordinate x e y del mio punto siano comprese tra −a/2 e a/2. Non capisco perché non dovrebbero essere casuali i numeri ottenuti...

In effetti va bene, avevo letto io male la funzione.
In ogni caso se segui il mio consiglio di considerare solo il primo quadrante, la funzione randUnif dovrà ritornare un valore compreso tra 0 e a e si semplifica quindi nel seguente modo:
Codice:
float randUnif(const float &a)
{
    return a * rand() / RAND_MAX;
}


Come già detto nel precedente post lascia perdere la radice quadrata, ho notato che rallenta notevolmente il programma.

Però testandolo il codice restituisce subito zero (un main in cui stampo soltanto la funzione) quindi c'è qualcosa che non torna :?

Strano... nel main hai richiamato la funzione srand()?
In ogni caso posta il codice completo.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 225 di 1486
Iscritto il: 16/05/2013, 22:05

Re: [C++] Approssimazione di $pi$

Messaggioda Landau » 13/06/2018, 15:29

Ecco a te Squirrel!

Codice:
#include <iostream>
#include <fstream>
#include <ctime>
#include <cmath>
#include <cstdlib>

using namespace std;

float randUnif(float, float);
float distO (float, float);
float misuraPi(int, float);

//************************************************************************//

int main(){

   srand(time(NULL));

   int n;
   float lato;
   
   cout << "Inserire nPunti: ";
   cin >> n;
   cout << "Inserire lato: ";
   cin >> lato;
   
   cout << misuraPi(n, lato) << endl;

   return 0;
}

//************************************************************************//

float randUnif(const float &a)
{
    return a * rand() / RAND_MAX;
}

float distO (float x, float y){
   return (x*x+y*y);
}

//************************************************************************//

float misuraPi(int nPunti, float a){

   float x, y;
   int centri=0;
   for(unsigned int j=0; j<nPunti; j++){
      x=randUnif(a/2);
      y=randUnif(a/2);
      
      if(distO(x,y)<=pow(a,2)/4){
         centri++;
      }
   }
   return (float) 4*(centri/nPunti);
}
Landau
Junior Member
Junior Member
 
Messaggio: 45 di 118
Iscritto il: 05/09/2017, 20:42

Re: [C++] Approssimazione di $pi$

Messaggioda Super Squirrel » 13/06/2018, 18:34

Codice:
if(distO(x,y)<=pow(a,2)/4)

Perchè scomodare la funzione pow() e creare la funzione dist0 quando basta fare
Codice:
if(x * x + y * y <= a * a / 4)

?

Le librerie fstream e cstdlib (e anche cmath se non utilizzi pow) sono superflue.

Il motivo per cui il programma restituisce 0 si trova nella seguente riga di codice:
Codice:
return (float) 4*(centri/nPunti);

Quello che avviene, nell'ordine, è:
- conversione di 4 da int a float;
- divisione intera tra centri e nPunti (essendo entrambi di tipo int) che restituisce 0;
- prodotto tra 4.0 e 0 che fa 0.
In ogni caso c'è qualcosa che non mi torna... nel precedente post avevi scritto:
Codice:
return (float) 4*centri/nPunti;

che va bene. Mi sembra strano che il programma ritornasse 0!
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 226 di 1486
Iscritto il: 16/05/2013, 22:05

Re: [C++] Approssimazione di $pi$

Messaggioda apatriarca » 13/06/2018, 20:59

Una regola che cerco di impormi quando scrivo delle espressioni il cui valore può cambiare in base alle regole arbitrarie* di precedenza e associatività di un linguaggio è quella di forzare la precedenza usando delle parentesi. E' per esempio il caso nell'espressione
Codice:
return a * rand() / RAND_MAX;

Il valore è infatti quello "corretto" se l'espressione viene valutata come
Codice:
return (a * rand()) / RAND_MAX;

ma è uguale a zero nel caso in cui l'espressione sia valutata come
Codice:
return a * (rand() / RAND_MAX);

Ovviamente è necessario fare attenzione alla differenza tra divisione intera e tra float per non usare le parentesi in modo errato come hai fatto nell'altra situazione simile.
Codice:
return (float) 4*(centri/nPunti);


Altre cose che ho notato sono:
1. Non c'è alcuna ragione di passare un valore in virgola mobile per riferimento se non deve essere modificato. Rendi il codice solo piú lento..
2. Siccome il risultato è indipendente dal lato del quadrato usato per calcolare l'approssimazione di \(\pi\), è in realtà possibile estrarre valori compresi tra \([0, 1]\) e ignorare \(a\)..
3. Piuttosto che dividere è in generale meglio moltiplicare. Per cui \( a \leq b/c \) è meglio scritto come \( a*c \leq b \)..


* Ci sono regole come la precedenza della moltiplicazione sulla somma che vengono dall'algebra, ma altre sono piú arbitrarie e non sono necessariamente le stesse quando si cambia linguaggio.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5062 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [C++] Approssimazione di $pi$

Messaggioda Super Squirrel » 13/06/2018, 22:55

1. Non c'è alcuna ragione di passare un valore in virgola mobile per riferimento se non deve essere modificato. Rendi il codice solo piú lento..

Non sono molto informato sull'argomento, in termini di tempo e di memoria conviene maggiormente il passaggio per valore o quello per riferimento?

3. Piuttosto che dividere è in generale meglio moltiplicare. Per cui a≤b/c è meglio scritto come a∗c≤b..

Come mai? Ti riferisci alla divisione in generale oppure bisogna fare una distinzione con la divisione intera?
Per esempio se sto operando con interi grandi, optando per la divisione non mi tutelo dal rischio di overflow?

Ci sono regole come la precedenza della moltiplicazione sulla somma che vengono dall'algebra, ma altre sono piú arbitrarie e non sono necessariamente le stesse quando si cambia linguaggio.

Ma nel C++ operazioni che hanno la stessa precedenza vengono effettuate sempre da sinistra verso destra o ci possono essere delle eccezioni dettate per esempio da ottimizzazioni del compilatore?
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 227 di 1486
Iscritto il: 16/05/2013, 22:05

Re: [C++] Approssimazione di $pi$

Messaggioda apatriarca » 13/06/2018, 23:33

1. Quando passi una variabile per riferimento, stai in pratica passando il suo indirizzo. Quando il valore non viene modificato stai rendendo l'accesso piú lento perché invece di usare un indirizzo costante, accedi ad esso tramite una variabile. Il potenziale vantaggio risiede invece nel fatto di non aver bisogno di copiare tutta la memoria della relativa variabile. Se la variabile è grossa, conviene passare per riferimento, altrimenti per valore. Nel caso di un float stai in realtà copiando piú memoria perché la dimensione di un float è nelle moderne architetture a 64bit inferiore ad un indirizzo in memoria.

3. Dipende in effetti dalla situazione, potrebbe essere una preferenza personale in effetti. La divisione impedisce l'overflow, ma mi è capitato piú volte di aver problemi con la divisione. Per esempio non notando che l'espressione è intera o perché ho diviso per un valore troppo piccolo o altro. Discorso simile vale per somma e sottrazione per me. Preferisco scrivere le espressioni con la somma invece che con la sottrazione se possibile. Ma tutte le "regole" di questo tipo vanno valutate caso per caso.

La precedenza/associatività di un operatore è sempre la stessa. Il compilatore non può cambiare il significato del codice durante le ottimizzazioni e non può quindi certamente cambiare qualcosa come precedenza o associatività. In C++ le operazioni binarie ad eccezione degli assegnamenti vanno da sinistra verso destra. La differenza si può avere quando si passa ad altri linguaggi e il problema è piú che altro legato alla leggibilità e al fatto che quando dopo mesi tocchi di nuovo il codice non ricordi necessariamente che l'ordine delle operazioni era importante.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5063 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [C++] Approssimazione di $pi$

Messaggioda Super Squirrel » 14/06/2018, 00:01

Molto chiaro, grazie per la spiegazione.

... e il problema è piú che altro legato alla leggibilità e al fatto che quando dopo mesi tocchi di nuovo il codice non ricordi necessariamente che l'ordine delle operazioni era importante.

Vero, non ci avevo pensato.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 228 di 1486
Iscritto il: 16/05/2013, 22:05

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite