Solving Computational Problems Using Randomization

 

Solving Computational Problems Using Randomization

Let us look at how to solve computational problems using randomization. To get an idea of how to solve computational problems using randomization, let us start with the problem of estimating the value of Pi (π).A common randomized approach to estimate the value of Pi (π) is the Monte Carlo method. This method involves simulating random points in a square that contains a quarter circle and calculating the ratio of points that fall inside the quarter circle to the total number of points.

Monte Carlo Method to Estimate π

1. Generate random points within a unit square (1 × 1).

2. Count how many points fall inside a quarter circle of radius 1.

3. The ratio of points inside the quarter circle to the total points approximates

the area of the quarter circle ( π/4 ).

4. Multiply this ratio by 4 to estimate π.

Here is a Python code to estimate π using the Monte Carlo method:

import random

num_samples = 1000000 # Number of random points to generate

inside_circle = 0 # points inside unit circle

for _ in range(num_samples):

        x = random.random()

        y = random.random()

        if x**2 + y**2 <= 1:

            inside_circle += 1 #increment count if the point is inside circle

pi_estimate = (inside_circle / num_samples) * 4

print(f"Estimated value of pi with {num_samples} samples:{pi_estimate}")

Output:

Estimated value of pi with 1000000 samples:3.14306