Как вычислить число пи c

Как приближенно вычислить значение числа Пи с использованием объема сферы?

Моя задача — вычислить приближенное значение числа Пи с точностью не менее 10^-6. Алгоритм Монте-Карло не обеспечивает требуемой точности. Мне нужно использовать расчет с использованием объема шара. Что посоветуете?

Отслеживать
13.8k 12 12 золотых знаков 44 44 серебряных знака 77 77 бронзовых знаков
задан 12 июн 2021 в 10:42
11 2 2 бронзовых знака
А чем вас Монте-Карло не устраивает собственно? Уточните.
13 июн 2021 в 8:31
Попробуйте ряд Нилаканта. и уточните что там про шар ? какие данные есть ?
13 июн 2021 в 8:42

Если критично именно сферу использовать — просто тремя циклами проходите по координатам от 0 до R, проверяйте попадает ли координата внутрь сферы. Но тогда не не будет постепенного приближения к точному значению, а нужно будет дождаться до конца выполнения всех циклов, и только потом получить результат.

13 июн 2021 в 8:57

@Asan Монте-Карло (да и любой другой алгоритм перебора) надо запускать и оставлять не до того момента, как он впервые покажет 3,141592**, а дольше. Насколько точно дольше — не подскажу, тут надо теорию вспоминать/знать ..

13 июн 2021 в 9:45
Посоветую численное интегрирование для вычисления объема шара.
15 июн 2021 в 5:58

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Приблизим осьмушку шара треугольным мешем. Вершины меша будут лежать на поверхности единичной сферы. Тело ограниченное координатными плоскостями и мешем лежит целиком внутри осьмушки шара. Его объём используем для оценки pi снизу. Отыщем множитель на который нужно умножить координаты всех вершин меша так чтобы после умножения фигура содержала осьмушку шара внутри себя. Объём новой (раздутой) фигуры используем для оценки pi сверху. Так как мы не знаем заранее сколько должно быть треугольников в меше, то будем повторять процедуру со всё более подробными мешами пока оценки pi не сблизятся на расстояние 10^-6. Поехали.

Четыре поколения поверхностей:

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

Объём полигонального тела складывается из объёмов тетраэдров. Тетраэдр строится на треугольнике поверхности и точке (0, 0, 0) . Шестикратный объём такого тетраэдра вычисляется как определитель.

Имеем последовательность оценок числа pi снизу. Как оценить pi сверху?

Каждый треугольник поверхности определяет плоскость. Вычислим минимальное расстояние от этой плоскости до начала координат: строим единичный нормальный вектор к треугольнику, скалярно умножаем его на координаты любой вершины треугольника. Расстояние получится меньше единицы.

Если все координаты всех вершин треугольника умножить на величину обратную к найденному расстоянию, то новые вершины образуют новую плоскость (параллельную старой), для которой расстояние будет единичным.

Выберем минимум из расстояний для всех треугольников поверхности. Все вершины поверхности домножим на обратную величину. Получим новую поверхность гомотетичную старой. Новая поверхность целиком проходит вне шара. То есть объём нового тела будет больше pi . Конечно, суммировать его заново не надо, он вычисляется из объёма поверхности внутри шара умножением на некоторый коэффициент.

import math def add(p1, p2): x1, y1, z1 = p1 x2, y2, z2 = p2 return x1 + x2, y1 + y2, z1 + z2 def sub(p1, p2): x1, y1, z1 = p1 x2, y2, z2 = p2 return x1 - x2, y1 - y2, z1 - z2 def scale(f, p): x, y, z = p return f * x, f * y, f * z def mid(p1, p2): return scale(1 / 2, add(p1, p2)) def dot(p1, p2): x1, y1, z1 = p1 x2, y2, z2 = p2 return x1 * x2 + y1 * y2 + z1 * z2 def norm(p): return math.sqrt(dot(p, p)) def normalized(p): return scale(1 / norm(p), p) def cross(p1, p2): x1, y1, z1 = p1 x2, y2, z2 = p2 return \ y1 * z2 - z1 * y2, \ z1 * x2 - x1 * z2, \ x1 * y2 - y1 * x2 def normal(p1, p2, p3): return normalized(cross(sub(p2, p1), sub(p3, p1))) def height(p1, p2, p3): return dot(normal(p1, p2, p3), p1) def volume6(p1, p2, p3): x1, y1, z1 = p1 x2, y2, z2 = p2 x3, y3, z3 = p3 # | x1, y1, z1 | # | x2, y2, z2 | # | x3, y3, z3 | return \ ((x1 * y2) - (x2 * y1)) * z3 - \ ((x1 * y3) - (x3 * y1)) * z2 + \ ((x2 * y3) - (x3 * y2)) * z1 def subdiv(p1, p2, p3): p12 = normalized(mid(p1, p2)) p23 = normalized(mid(p2, p3)) p31 = normalized(mid(p3, p1)) yield p1, p12, p31 yield p2, p23, p12 yield p3, p31, p23 yield p12, p23, p31 def main(): surface = (((1, 0, 0), (0, 1, 0), (0, 0, 1)), ) for i in range(1, 1000): print(f'(): ', flush=True, end='') min_height = min(height(*t) for t in surface) v_low = sum(volume6(*t) for t in surface) v_high = v_low * (1 / min_height) ** 3 print(f' < pi < , ') if v_high - v_low < 1e-6: break surface = tuple(tt for t in surface for tt in subdiv(*t)) main() 

$ time python pi_approximation.py 1(1): 1 < pi < 5.196152422706629, 4.196152422706629 2(4): 2.207106781186547 < pi < 4.054714066307733, 1.8476072851211862 3(16): 2.8632972148712703 < pi < 3.4166084802548, 0.5533112653835297 4(64): 3.0687004650644996 < pi < 3.2136638054952016, 0.14496334043070203 5(256): 3.123152697186476 < pi < 3.1598235333433777, 0.03667083615690192 6(1024): 3.136968953405614 < pi < 3.1461637781466827, 0.009194824741068697 7(4096): 3.140435869168335 < pi < 3.142736273849948, 0.0023004046816126333 8(16384): 3.1413034037353573 < pi < 3.141878611120626, 0.0005752073852685058 9(65536): 3.141520337766175 < pi < 3.1416641462518413, 0.00014380848566641902 10(262144): 3.1415745744239363 < pi < 3.141610526960324, 3.595253638755125e-05 11(1048576): 3.1415881337850373 < pi < 3.141597121945071, 8.988160033585046e-06 12(4194304): 3.141591523637882 < pi < 3.141593770679511, 2.2470416292108553e-06 13(16777216): 3.141592371100547 < pi < 3.1415929328610557, 5.617605087770983e-07 real 2m59.102s user 2m57.320s sys 0m1.480s 

Как вычислить значение Пи

Соавтор(ы): Grace Imson, MA. Грейс Имсон — преподаватель математики с более чем 40 годами опыта. В настоящее время преподает математику в Городском колледже Сан-Франциско, ранее работала на кафедре математики в Сент-Луисском университете. Преподавала математику на уровне начальной, средней и старшей школы, а также колледжа. Имеет магистерскую степень по педагогике со специализацией на руководстве и контроле, полученную в Сент-Луисском университете.

Количество источников, использованных в этой статье: 7. Вы найдете их список внизу страницы.

Количество просмотров этой статьи: 256 987.

В этой статье:

Пи (π) — одно из самых важных и интригующих чисел в математике. Эта константа, примерно равная 3,14, используется для вычисления длины окружности с учетом ее радиуса. [1] X Источник информации Это также иррациональное число, то есть оно может быть вычислено до бесконечного числа знаков после запятой. [2] X Источник информации Это не так-то просто сделать, но все-таки возможно.

Метод 1 из 5:

Вычисление Пи через измерение окружности

Убедитесь, что вы используете идеальный круг. Этот метод не работает с эллипсами, овалами и чем-либо иным, этот метод подходит только для идеальной окружности. Окружность определяется как совокупность всех точек на плоскости, которые лежат на одинаковом расстоянии от одной центральной точки. Крышка банки — идеальный предмет для этого метода. Если вы хотите сделать наиболее точные вычисления, используйте карандаш с очень тонким грифелем.

• Оберните нитку вокруг крышки как можно плотнее. Отметьте точку совпадения начала и конца, а затем измерьте длину нитки с помощью линейки.

Измерьте диаметр окружности. Диаметр — длина отрезка, проходящего через центр окружности и любые две точки, лежащие на окружности.

Используйте формулу. Длина окружности вычисляется по формуле C= π*d = 2*π*r. Таким образом, Пи равно длине окружности, деленной на ее диаметр. Посчитайте Пи (с вашими значениями) на калькуляторе. Результат должен быть примерно равен 3,14. [3] X Источник информации

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

Как вычислить число пи c

rui_er → Codeforces Round 942 (Div. 1, Div. 2)

rui_er → Codeforces Round 942 (Div. 1, Div. 2) Editorial

Abito → Who's going to IIOT 2024?

Kolyanchick → До скорых встреч

MikeMirzayanov → Изменение правил об использовании стороннего кода в соревнованиях Codeforces

Errichto → IOI Camp, USACO Classes

awoo → Educational Codeforces Round 165 [рейтинговый для Div. 2]

Zanite → [Photos Dump] Jollybee CP Team, the Luxor WF, and the Indomie Aftermath

awoo → Разбор Educational Codeforces Round 165

galen_colin → fix problem ratings pls (the rainboy effect)

matheusazevedo → Stairway to Deven: a maratona do caos

Lyde → (Kind of) A brief overview about the near future of Competitive Programming

atcoder_official → AtCoder Beginner Contest 351 Announcement

jdurie → Codeforces Round #941 (Div. 1, Div. 2)

Sagy13 → Compilation Error in Educational Codeforces Round 165 after code got AC

Asuna_Yuuki → MEME

Termodinamico → We say thank you to MikeMirzayanov

EnDeRBeaT → [Tool] Graph Debugger

tallnut_liu → (Plenty of) useful blogs in CodeForces

Loserinlife → Need help

ppavic → Croatian Olympiad in Informatics (COI) 2024

Sahilamin219 → Google Question Asked Onsite

dp_16 → Doubt with Maps, Sets with Custom Structs

akzytr → Pleasant pairs -> O(n log n)

sdyakonov → Make proofs

Блог пользователя Abra

Автор Abra, 13 лет назад ,

Сегодняшняя дата напомнила мне об интересной задачке на spoj.pl.
Все просто - нужно вывести как можно больше верных знаков числа Пи в десятичной записи за 25 секунд.
Я перепробовал множество методов:
от самых простых, (~200 знаков)

через забавные, (~1000 знаков)

к наиболее эффективному из тех, что я пробовал (~7300 знаков)

Витает еще идея использовать хитрую формулу

для получения шестнадцатиричной записи, и уже потом перевести что получится в десятичную.
Лучшее мое решение написано на яве с использованием BigDecimal и самописного квадратного корня.

Может оптимизировать длинку? Или искать другие методы, ведь есть же решения, выводящие 20002 знаков за 2.5 секунд?

Подскажите, как вычислить миллион знаков =)

вычисления, оптимизация, число пи

Комментарии (21)

13 лет назад , # |

А какое ограничение на размер кода? Можно какое-то число последних разрядов просто запомнить в константную строку, а потом эффектно выбухнуть в выходной файл.

13 лет назад , # ^ |

← Rev. 2 → 0

Предусмотрено: максимальная длина кода - 4 Кб.
13 лет назад , # ^ |
Дык а можно сжать 😉
13 лет назад , # ^ |
Вот только в лучшем результате 720002 цифр)
13 лет назад , # |
Это скорее математиков надо спрашивать.
13 лет назад , # ^ |
Задача-то на вычисления, так что тут ей самое место =)
13 лет назад , # ^ |

Да, но все сколь угодно клёвые формулы, приближающие число Pi, которые, немного подумав, могут изобрести программисты, математики уже давно изобрели.

13 лет назад , # |

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

13 лет назад , # |

В яве длинка с базой равной степени двойки. Если делать с базой 10 k то возможно на вывод потребуется гораздо меньше времени.

13 лет назад , # ^ |

Только мне кажется, что вывести 20000 знаков, преобразовав их в десятичную запись - дело
13 лет назад , # ^ |
Да, только тебе)
Обычный алгоритм смены системы счисления (без быстрого умножения) работает за O(n^2)
13 лет назад , # ^ |

← Rev. 2 → 0

На самом деле нормально написанное преобразование 20000 знаков в десятичную запись за O(n 2 ) работает быстрее, чем за 0.1 секунды. У меня на ноутбуке число из 66666 двоичных цифр переводится в число из 20069 десятичных цифр примерно за 40 миллисекунд. Но это на C++. Попробовал то же самое на Java. Работает 12-13 миллисекунд. Перевод числа из 666666 двоичных цифр в число из 200687 десятичных на C++ проработал 4 секунды, а на Java 1.2 секунды (действительно O(n 2 ) ^^). Хмм. Некоторые программы, оказывается, можно ускорить, переписав их с C++ на Java. 🙂 Хотя, дело скорее всего в 64-битном компиляторе для Java. Если скомпилировать код на C++ 64-битным компилятором под линуксом, то он работает 1.3 секунды.

13 лет назад , # ^ |

>Хмм. Некоторые программы, оказывается, можно ускорить, переписав их с C++ на Java. 🙂

У явы очень мощный JIT оптимизатор, но он помогает только если программа работает достаточно долго чтобы он успел сработать)

13 лет назад , # |

Попробуйте использовать ту хитрую формулу)) Она позволяет находить цифры числа π независимо друг от друга и весьма точно. Идея такая - домножим эту формулу на 16 t и потом целую часть отбросим, а потом в даблах вычислим дробную часть и округлим.

Подробностей не помню - давно решал подобную задачу. В той задаче нужно было вывести i -ю цифру двоичной записи π . Можно ли хитрую формулу эффективно распространить на много цифр - не знаю.

13 лет назад , # |
Топ решений - на Haskell, Python и LISP. Как они это делают??
13 лет назад , # |

← Rev. 3 → +3

I think this algorithm can be useful.
13 лет назад , # ^ |

This algorithm is useful in some way, but, despite very fast increasing number of correct digits, it's slower than the best I tried, 3000 digits against 7000.

13 лет назад , # |

Вообще, при правильном использовании третья("забавная") формула позволяет считать миллионы знаков:

13 лет назад , # |

← Rev. 2 → 0

If you want to try a funny method for calculating Pi digits, I suggest you try some fixed point iterations:
x[0] = 3.14 (or anything close to Pi) and then:
x[i+1] = x[i] + sin(x[i]) -- cubic convergence (i.e. x[i+1] has ~3 times more exact digits than x[i]),
or better:
x[i+1] = x[i] + sin(x[i]) + 1/6*sin^3(x[i]) -- order 5 convergence
or perhaps even:
x[i+1] = x[i] + sin(x[i]) + 1/6*sin^3(x[i]) + 3/40*sin^5(x[i]) -- order 7 convergence.

An advantage of these methods is that they are 'fixed point iterations'. As a consequence, you don't actually need to be precisely accurate in your computations, because the iteration will converge to Pi for any decent approximation. So you should gradually (according to convergence order) increase arithmetic accuracy as the iteration proceeds.
Also notice that only one sin() has to be computed at each iteration, the rest is just a polynomial combination.

So the whole difficulty is now in calculating sin(x). Note that using some standard series around x=0 would be very inefficient, because x will be closer to Pi each time. A funny recursive method to calculate sin(x) is

sin(x, depth) = 3t-4t^3, where t=sin(x/3, depth-1)
sin(x, 0) = x

More depth - more accuracy. Also you could replace base condition by e.g.
sin(x,0) = x - 1/6*x^3,
or include even more terms, then you'll be able to use smaller depth. You'll need to find an optimal combination.

13 лет назад , # ^ |

← Rev. 2 → +5

Also, forgot to mention, fixed point iterations natually lean themselves to different convergence acceleration methods. For this concrete case I would suggest Aitken's acceleration method: calculate 3 values of iteration, then using those three values calculate

And start the next iteration from Ax (instead of x[n+2]).

Март, четырнадцатое. Как вычислить число Пи

Каждый год 14 марта мы публикуем материал, посвященный числу Пи. На этот раз по просьбе N + 1 математик Владимир Потапов рассказал о том, как число Пи можно вычислить математическим путем, с помощью различных — подчас необычных — формул.

Еще в древности люди заметили, что отношение длины окружности к ее диаметру близко к трем, но не точно три, а чуть больше. Причем это отношение не зависит ни от диаметра окружности, ни от места, где она проведена. В те времена это отношение, названное впоследствии числом Пи, не сильно выделялось из множества других чисел, которые можно определить опытным путем. Таких как отношение диагонали квадрата к его стороне или отношение площадей квадрата и равностороннего треугольника с такой же, как у квадрата, стороной.

Отцом числа Пи следует считать Архимеда, которого называют автором удивительных открытий, что отношение Пи не приближенно, а в точности связывает не только диаметр и длину окружности, но и площадь круга и квадрат его радиуса, объем шара и куб его радиуса и даже площадь сферы и квадрат ее радиуса. То есть Архимед доказал известные всем со школы формулы: L = 2πr, S1 = πr2, V = 4/3 x πr3 и S2 = 4πr2.

Архимеду принадлежит также первая не опытная, а теоретическая (методом построения описанных и вписанных в круг многоугольников) оценка числа Пи: 3 + (10/71) < < 3 + (1/7). То есть он нашел первые три десятичные цифры числа Пи = 3,14. что и определило сегодняшнюю дату.

Впоследствии математики поняли, что число Пи связывает объем многомерного шара и степень его радиуса при любой размерности пространства (с рациональным множителем, уже зависящим от размерности: для 2х измерений это 1, для 3х измерений — 4/3). Таким образом, число Пи не изменится даже для исследователей, живущих в пространствах с другим числом измерений.

Однако отношение длины окружности к ее диаметру меняется при искривлении пространства и совпадает с нашей константой только в «плоском» однородном случае, проще говоря в пространстве, для которого справедлива теорема Пифагора. Как утверждает теория относительности, рядом с горизонтом событий черной дыры пространство сильно искривлено. Неужели цивилизация, которой повезло возникнуть в подобном месте, может не подозревать о существовании константы Пи?

Оказывается, число Пи неожиданно возникает просто из натурального ряда чисел. Английский математик Джон Валлис, старший современник Исаака Ньютона, открыл удивительную формулу:

Многоточие в конце формулы означает, что если мы перемножим достаточно много четных чисел в числителе и нечетных в знаменателе, то получим результат, сколь угодно близкий к числу Пи /2.

Еще более удивительную для непосвященных формулу с участием числа вывел великий математик Леонард Эйлер, бóльшую часть своей долгой научной карьеры проработавший в Петербургской академии наук:

Эта формула была признана «самой красивой теоремой в математике». Здесь e = 2,71828. — константа Эйлера, i = √-1 — мнимая единица и Пи — конечно, наше число Пи. На самом деле формулаЭйлера эквивалентна сразу двум равенствам:

где n! = 1×2 x 3···(n — 1) x n.

Конечно, затруднительно вычислять Пи из этих формул как корень уравнения бесконечной степени. А уравнения конечной степени с целыми коэффициентами, корнем которого было бы число Пи, не существует! Это доказал в конце XIX века немецкий математик Фердинанд фон Линдеман, решив заодно знаменитую античную проблему «квадратуры круга». То есть он показал, что, имея отрезок, равный диаметру круга, невозможно только с помощью циркуля и линейки построить квадрат, площадь которого равна площади круга.

Другая знаменитая формула Эйлера:

уже пригодна для приближенного вычисления числа Пи. И даже более подходит для этой цели, чем формула великого немецкого философа и математика Готфрида Лейбница:

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

при подстановке x = 1. Долгое время наиболее удобным для вычисления приближений числа Пи считалось равенство английского математика Джона Мэчина, который был секретарем Лондонского королевского общества, когда его возглавлял Исаак Ньютон. Вот это равенство Мэчина:

Для вычисления числа Пи по формуле Мэчина нужно сначала вычислить arctg1/5 и arctg1/239 с помощью приведенного выше разложения арктангенса в ряд Тейлора, которое, по-видимому, впервые нашел сам Исаак Ньютон.

Число возникает в математике в самых неожиданных местах. Например, математик Абрахам де Муавр (бежавший в Англию из Франции, где его преследовали как гугенота) обнаружил формулу:

Теперь ее называют формулой Эйлера-Пуассона, или интегралом Гаусса.

Сам Муавр, а также выдающиеся математики Пьер-Симон де Лаплас и Карл Фридрих Гаусс в разной степени общности и строгости доказали, что функция Φ(x) = e-x2/2/√2 (из формулы Эйлера-Пуассона следует, что интеграл от функции Φ по вещественной прямой равен 1) является плотностью нормального, или гауссова, распределения, которое является предельным для средних арифметических последовательности независимых случайных величин.

Это означает, например, если мы будем n серий по m раз подбрасывать монету, вычислять разность между числом выпавших «орлов» и «решек» и записывать результат в таблицу, то при росте n и m построенная по таблице гистограмма будет все больше походить на график функции Φ. Эта теорема служит фундаментом для современной квантовой физики, обеспечивая возможность извлекать из многократных измерений случайных событий строгие закономерности.

Казалось бы, тысячелетняя история исследований позволяет предположить, что мы не упустили ничего важного о числе. Однако в 1997 году, совсем недавно в историческом масштабе, произошла сенсация. Саймон Плафф нашел новое представление для числа в виде ряда:

которое не только требует гораздо меньше слагаемых для вычисления числа с заранее заданной точностью, но и позволяет вычислить любую цифру в двоичном представлении числа Пи, не вычисляя предыдущие цифры.