Estimación del valor de Pi usando Monte Carlo | Método de computación en paralelo

Dados dos números enteros N y K que representan el número de intentos y el número total de subprocesos en el procesamiento paralelo. La tarea es encontrar el valor estimado de PI usando el algoritmo Monte Carlo usando la técnica Open Multi-processing (OpenMP) de paralelizar secciones del programa.

Ejemplos:

Entrada: N = 100000, K = 8 
Salida: Estimación final de Pi = 3,146600

Entrada: N = 10, K = 8
Salida: Estimación final de Pi = 3,24

Entrada: N = 100, K = 8
Salida: Estimación final de Pi = 3,0916

Enfoque: El problema dado anteriormente Estimar el valor de Pi usando Monte Carlo ya se resolvió usando un algoritmo estándar. Aquí la idea es usar computación paralela usando OpenMp para resolver el problema. Siga los pasos a continuación para resolver el problema:

• Inicialice 3 variables, digamos x, y y d para almacenar las coordenadas X e Y de un punto aleatorio y el cuadrado de la distancia del punto aleatorio desde el origen.
• Inicialice 2 variables, digamos pCircle y pSquare con valores 0 para almacenar los puntos que se encuentran dentro del círculo de radio 0.5 y cuadrado de longitud de lado 1 .
• Ahora comienza el procesamiento paralelo con OpenMp junto con la reducción() de la siguiente sección:
  • Itere sobre el rango [0, N] y encuentre x e y en cada iteración usando srand48() y drand48() luego encuentre el cuadrado de la distancia del punto ( x, y) desde el origen y luego si la distancia es menor o igual a 1 y luego incremente pCircle en 1 .
  • En cada iteración del paso anterior, incremente el recuento de pSquare en 1 .
• Finalmente, después del paso anterior, calcule el valor de pi estimado como se muestra a continuación y luego imprima el valor obtenido.
  •  Pi = 4.0 * ((doble)pCirculo / (doble)(pCuadrado))

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find estimated
// value of PI using Monte
// Carlo algorithm
void monteCarlo(int N, int K)
{
   
    // Stores X and Y coordinates
    // of a random point
    double x, y;
   
    // Stores distance of a random
    // point from origin
    double d;
 
    // Stores number of points
    // lying inside circle
    int pCircle = 0;
 
    // Stores number of points
    // lying inside square
    int pSquare = 0;
    int i = 0;
 
// Parallel calculation of random
// points lying inside a circle
#pragma omp parallel firstprivate(x, y, d, i) reduction(+ : pCircle, pSquare) num_threads(K)
    {
       
        // Initializes random points
        // with a seed
        srand48((int)time(NULL));
 
        for (i = 0; i < N; i++)
        {
           
            // Finds random X co-ordinate
            x = (double)drand48();
 
            // Finds random X co-ordinate
            y = (double)drand48();
 
            // Finds the square of distance
            // of point (x, y) from origin
            d = ((x * x) + (y * y));
 
            // If d is less than or
            // equal to 1
            if (d <= 1)
            {
               
                // Increment pCircle by 1
                pCircle++;
            }
           
            // Increment pSquare by 1
            pSquare++;
        }
    }
   
    // Stores the estimated value of PI
    double pi = 4.0 * ((double)pCircle / (double)(pSquare));
 
    // Prints the value in pi
    cout << "Final Estimation of Pi = "<< pi;
}
 
// Driver Code
int main()
{
   
    // Input
    int N = 100000;
    int K = 8;
   
    // Function call
    monteCarlo(N, K);
}
 
// This code is contributed by shivanisinghss2110

// C program for the above approach
 
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
// Function to find estimated
// value of PI using Monte
// Carlo algorithm
void monteCarlo(int N, int K)
{
    // Stores X and Y coordinates
    // of a random point
    double x, y;
    // Stores distance of a random
    // point from origin
    double d;
 
    // Stores number of points
    // lying inside circle
    int pCircle = 0;
 
    // Stores number of points
    // lying inside square
    int pSquare = 0;
 
    int i = 0;
 
// Parallel calculation of random
// points lying inside a circle
#pragma omp parallel firstprivate(x, y, d, i) reduction(+ : pCircle, pSquare) num_threads(K)
    {
        // Initializes random points
        // with a seed
        srand48((int)time(NULL));
 
        for (i = 0; i < N; i++) {
            // Finds random X co-ordinate
            x = (double)drand48();
 
            // Finds random X co-ordinate
            y = (double)drand48();
 
            // Finds the square of distance
            // of point (x, y) from origin
            d = ((x * x) + (y * y));
 
            // If d is less than or
            // equal to 1
            if (d <= 1) {
                // Increment pCircle by 1
                pCircle++;
            }
            // Increment pSquare by 1
            pSquare++;
        }
    }
    // Stores the estimated value of PI
    double pi = 4.0 * ((double)pCircle / (double)(pSquare));
 
    // Prints the value in pi
    printf("Final Estimation of Pi = %f\n", pi);
}
 
// Driver Code
int main()
{
    // Input
    int N = 100000;
    int K = 8;
    // Function call
    monteCarlo(N, K);
}

Final Estimation of Pi = 3.146600

Salida del programa C anterior

Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)