Added a solution with Monte Carlo simulation

Мето Трајковски · Мето Трајковски · commit 8d1e21d7e58e · 2020-01-19T21:37:06.000+01:00
diff --git a/Math/estimate_pi.py b/Math/estimate_pi.py
@@ -0,0 +1,60 @@
+'''
+Estimation of Pi
+
+Write a program to compute the value of PI using a random number generator/method.
+
+
+=========================================
+To solve this problem we'll use the Monte Carlo simulation/method.
+Generate N random points (0 <= X, Y <= 1) in the first quadrant.
+Count all points that are inside the circle using the squared euclidean distance (between origin <0,0> and point <X,Y>).
+The ratio between all points in the quarter circle and quarter square should be
+approximately equal to the ratio between a quarter of the circle area and a quarter of the square area.
+(more points = better estimation)
+Equation: (((r^2)*PI)/4) / (((2*r)^2)/4) = circle_points / total_points
+Solve the first part: (((r^2)*PI)/4) / (((2*r)^2)/4) = ((1^2)*PI) / ((2*1)^2) = (1*PI) / (2^2) = PI/4
+Simple equation: PI / 4 = circle_points / total_points
+Final form: PI = 4 * circle_points / total_points
+    Time Complexity:    O(N)
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+from random import random
+
+def estimate_pi(n):
+    total_points = 0
+    circle_points = 0
+
+    for i in range(n):
+        # generate N random points in the first quadrant
+        x, y = random(), random()
+
+        if x*x + y*y <= 1:
+            # using squared euclidean distance find the distance from (0, 0) to (x, y)
+            circle_points += 1
+        total_points += 1
+
+    # this formula is a short form of this: quarter_circle_area / quarter_square_area = circle_points / total_points
+    return 4 * circle_points / total_points
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => Doesn't give a good estimation at all (often the integer part is wrong)
+print(estimate_pi(10))
+
+# Test 2
+# Correct result => Gives a good estimation to the first decimal (3.1xxx)
+print(estimate_pi(10000))
+
+# Test 3
+# Correct result => Gives a good estimation to the second decimal (3.14xxx)
+print(estimate_pi(10000000))
diff --git a/README.md b/README.md
@@ -12,7 +12,7 @@ All solutions are written in [Python](https://www.python.org/) (more precisely,
 - [math](https://docs.python.org/3/library/math.html) (used for constants like math.pi, math.inf and functions like math.ceil, math.floor, math.gcd, math.log, math.pow, math.sqrt, etc)
 - [collections](https://docs.python.org/3/library/collections.html) (used for [collections.deque](https://docs.python.org/3/library/collections.html#collections.deque) when there is a need for [Stack](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) or [Queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)) data structures)
 - [heapq](https://docs.python.org/3/library/heapq.html) (used when there is a need for [Priority Queue](https://en.wikipedia.org/wiki/Priority_queue) data structure).
-- [random](https://docs.python.org/3/library/random.html) (used for [nondeterministic algorithms](https://en.wikipedia.org/wiki/Nondeterministic_algorithm), like shuffling arrays).
+- [random](https://docs.python.org/3/library/random.html) (used for [nondeterministic algorithms](https://en.wikipedia.org/wiki/Nondeterministic_algorithm), like shuffling arrays and Monte Carlo methods).
 
 So, to execute these solutions there is no need from installing any external packages. \
 Coding style and name conventions are described in the official [PEP8](https://www.python.org/dev/peps/pep-0008) page.
