coderz.py

Problem Statement (Asked By Google)

The formula for the area of a circle is given by πr². Use the Monte Carlo method to approximate the value of π to three decimal places.

Hint: The equation of a circle is x² + y² = r².

Problem link: N/A

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Explanation:

Monte Carlo methods use random sampling to estimate numerical results. In this case, we estimate the value of π\piπ using the ratio of the areas of a circle and a square:

1. Setup:
   • Consider a unit circle (radius r=1) inscribed within a square with side length 2r=2.
2. Random Sampling:
   • Randomly generate points within the square [−1,1]×[−1,1].
3. Circle Check:
   • For a point (x,y), it lies inside the circle if x^2 + y^2 < 1.
4. Approximation:
   • The ratio of points inside the circle to the total number of points approximates π/4. Multiply this ratio by 4 to estimate π.
5. Precision:
   • To approximate π up to three decimal places, we need an error of less than 10^-3. The error scales with 1/sqrt{n}​, so approximately 10^6 iterations are required.

Single-Threaded Monte Carlo Simulation in Java

import java.util.Random;

public class MonteCarloPi {

    public static double estimatePi(int iterations) {
        Random random = new Random();
        int inCircle = 0;

        for (int i = 0; i < iterations; i++) {
            double x = random.nextDouble() * 2 - 1; // Random x in [-1, 1]
            double y = random.nextDouble() * 2 - 1; // Random y in [-1, 1]

            if (x * x + y * y <= 1) { // Check if point is inside the circle
                inCircle++;
            }
        }

        return 4.0 * inCircle / iterations;
    }

    public static void main(String[] args) {
        int iterations = 1_000_000;
        double pi = estimatePi(iterations);
        System.out.printf("Estimated value of Pi: %.5f%n", pi); // Output Pi up to 5 decimal places
    }
}

Multi-Threaded Monte Carlo Simulation in Java

To parallelize the workload:

1. Divide the total iterations across multiple threads.
2. Each thread performs its share of the computations.
3. Combine the results from all threads to compute the final estimate.

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class MonteCarloPiParallel {

    public static double estimatePi(int iterations, int threads) throws Exception {
        ExecutorService executor = Executors.newFixedThreadPool(threads);
        int iterationsPerThread = iterations / threads;

        Callable<Integer> task = () -> {
            Random random = new Random();
            int inCircle = 0;
            for (int i = 0; i < iterationsPerThread; i++) {
                double x = random.nextDouble() * 2 - 1; // Random x in [-1, 1]
                double y = random.nextDouble() * 2 - 1; // Random y in [-1, 1]
                if (x * x + y * y <= 1) { // Check if point is inside the circle
                    inCircle++;
                }
            }
            return inCircle;
        };

        // Submit tasks to threads
        Future<Integer>[] results = new Future[threads];
        for (int i = 0; i < threads; i++) {
            results[i] = executor.submit(task);
        }

        // Aggregate results
        int totalInCircle = 0;
        for (Future<Integer> result : results) {
            totalInCircle += result.get();
        }

        executor.shutdown();
        return 4.0 * totalInCircle / iterations;
    }

    public static void main(String[] args) throws Exception {
        int iterations = 1_000_000;
        int threads = 4;

        double pi = estimatePi(iterations, threads);
        System.out.printf("Estimated value of Pi (Parallel): %.5f%n", pi); // Output Pi up to 5 decimal places
    }
}

Key Points:

1. Single-Threaded Solution:
   • Straightforward but may take a long time for large iterations.
2. Multi-Threaded Solution:
   • Distributes the workload across multiple threads, reducing execution time.
   • Uses ExecutorService for managing threads and Future to collect results.
3. Precision:
   • With 10^6 iterations, the estimated value of π\piπ is accurate up to three decimal places.

Complexity:

1. Time Complexity:
   • Both single-threaded and multi-threaded solutions take O(n), where n is the total number of iterations.
2. Space Complexity:
   • O(1) for single-threaded.
   • O(t) for multi-threaded, where t is the number of threads (due to task storage).

This solution demonstrates the power of Monte Carlo simulations and how parallelization can significantly improve performance.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.