Умные способы оценить ценность PI.

В мире математики существует бесконечное количество способов оценить значение PI. В этой статье я не хочу показывать вам, ребята, какие способы это сделать.

Способ 1: Использование случайных точек

Чтобы понять этот алгоритм, давайте посмотрим на этот график:

У нас есть круг, вписанный внутрь квадрата. Уравнение окружности можно записать так:

Это означает, что для любой точки P(x,y), если уравнение выполняется, точка попадет внутрь круга.

Наша оценка начинается с вопроса: если мы сгенерируем много случайных точек внутри квадрата, сколько из них попадет внутрь круга?

Что ж, точка с большей вероятностью попадет внутрь фигуры, чем больше ее площадь. Это означает, что количество точек внутри круга и за его пределами будет пропорционально площади круга на площадь квадрата. И мы знаем обе эти области!

Посмотрим на нашем примере:

У нас есть квадрат со стороной 2 и круг радиусом 1.

Итак, если мы сгенерируем много случайных точек внутри квадрата, мы можем оценить значение числа Пи, разделив количество точек, попавших внутрь круга, на количество сгенерированных точек!

Если мы возьмем только первый квадрант, с 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1 площадь останется пропорциональной, поэтому:

Давайте проверим это с помощью Python:

import random

def estimate_pi(total_points):
  points_inside_circle = 0
 
  for _ in range (1,total_points+1):
    x = random.random() #Generates a random number >= 0 and <= 1 for x
    y = random.random() #Generates a random number >= 0 and <= 1 for y

    if ((x)**2 + (y)**2) <= 1:
      points_inside_circle+=1
  
  print(points_inside_circle*4/total_points)

estimate_pi(1_000_000)     # 3.141996    --> 0.1s
estimate_pi(10_000_000)    # 3.1411976   --> 1.1s
estimate_pi(100_000_000)   # 3.14149764  --> 11.6s
estimate_pi(1_000_000_000) # 3.141562248 --> 1m 55s

Идеальный! Имея всего миллиард точек, мы можем оценить PI с точностью до 4 знаков после запятой! Но на это ушло почти 2 минуты. Посмотрим, сможем ли мы сделать быстрее!

Метод 2: Формула Лейбница

Готфрид Вильгельм Лейбниц был немецким эрудитом, который придумал другой способ оценки PI. Мы можем использовать его бесконечный ряд для оценки значения числа Пи, давайте проверим это на Python:

def leibniz(iter):
  pi = 4
  sign = -1
  
  for denominator in range(3,iter,2):
    pi += sign * 4 / denominator
    sign = sign * -1

  print(pi)

leibniz(1_000_000)     # 3.141590653589692   --> 0.0s  
leibniz(10_000_000)    # 3.1415924535897797  --> 0.1s
leibniz(100_000_000)   # 3.1415926335902506  --> 1.8s
leibniz(1_000_000_000) # 3.141592651589258   --> 17.6s

Ух ты!!! С 1 миллиардом итераций почти за 1/4 часть времени мы могли бы оценить число пи с точностью до 8-го знака после запятой!!! Но можем ли мы сделать лучше?

Метод 3: Серия Нилакантха

Келаллур Нилаканта Сомаяджи был математиком и астрономом из Южной Индии, и он придумал еще лучший способ оценки PI. Давайте посмотрим на эту формулу в действии:

def nilakantha(iter):
   
   sum=3
   n=2
   sign=1
   
   #for loop to add terms
   for i in range(0,iter):       
       sum+=(sign*(4/((n)*(n+1)*(n+2))))       
       
       sign = sign * -1
       n=n+2
       
   print(sum)

nilakantha(10_000) # 3.141592653589538 --> 0.0s

МОЙ БОГ!! Всего за 10 000 итераций менее чем за десятую долю секунды мы получили число пи с точностью до 12-го знака после запятой!!!

С этого момента, если мы хотим проверить, насколько быстрым может быть наш алгоритм Нилаканта, нам нужно использовать библиотеку python под названием Decimal, чтобы мы могли повысить точность наших чисел с плавающей запятой. Давайте сделаем это:

from decimal import Decimal

def nilakantha(iter):
   
   sum = Decimal(3)
   n = 2
   sign = Decimal(1)
   
   #for loop to add terms
   for i in range(0,iter):       
       sum = sum + sign * ( Decimal(4) / (Decimal(n)*Decimal(n+1)*Decimal(n+2)) )   
       
       sign = sign * Decimal(-1)
       n=n+2
       
   print(sum)

nilakantha(100_000) # 3.141592653589792988470143325      --> 0.0s
nilakantha(1_000_000) # 3.141592653589793238212643770    --> 0.6s
nilakantha(10_000_000) # 3.141592653589793238462392870   --> 6.5s
nilakantha(100_000_000) # 3.141592653589793238462643602  --> 1m 4.5s

Большой!!! Всего за 6,5 с, используя 10 миллионов итераций, мы довели число Пи до 21-го знака после запятой!! Это абсурд!! Мы не можем победить это… Или можем?