Как определить, насколько точен мой расчет числа пи?

772

Я пробовал различные методы для реализации программы, которая дает цифры числа Пи последовательно. Я попробовал метод рядов Тейлора , но он оказался очень медленным (когда я сравнил свой результат с онлайн-значениями через некоторое время). Во всяком случае, я пытаюсь лучшие алгоритмы.

Итак, при написании программы я застрял в проблеме, как и во всех алгоритмах: как мне узнать, nчто вычисленные мной цифры точны?

Ишан Шарма
источник
20
больше математической проблемы. Хорошие алгоритмы также дают оценку ошибки.
пример
35
Сравните с пи?
Дэйв Ньютон,
55
@chris: «Буквально везде»?
Гонки легкости на орбите
32
Я могу проверить для вас до 3.141592653589793238462643383279502, кроме того, зачем вам такое большое количество цифр? (Это что-то вроде точности атомного уровня с кругом размером с вселенную.)
AJ Henderson
65
Почему бы вам просто не разделить на пи и проверить, если результат равен 1? (шучу)
user541686

Ответы:

1629

Поскольку я являюсь держателем мирового рекорда по большинству цифр числа пи, я добавлю два моих цента :

Если вы на самом деле не устанавливаете новый мировой рекорд, обычная практика - просто проверять вычисленные цифры по известным значениям. Это достаточно просто.

На самом деле, у меня есть веб-страница, на которой перечислены фрагменты цифр с целью проверки вычислений против них: http://www.numberworld.org/digits/Pi/


Но когда вы попадаете на территорию с мировым рекордом, не с чем сравнивать.

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

Это обычно вдвое больше необходимого времени (поскольку второй алгоритм обычно медленнее). Но это единственный способ проверить вычисленные цифры после того, как вы попали на неизведанную территорию с ранее не вычисленными цифрами и новым мировым рекордом.


В те дни, когда суперкомпьютеры устанавливали рекорды, обычно использовались два разных алгоритма AGM :

Это оба O(N log(N)^2)алгоритма, которые довольно легко реализовать.

Однако в настоящее время все немного по-другому. В последних трех мировых рекордах вместо двух вычислений мы выполнили только одно вычисление, используя самую быструю известную формулу (формула Чудновского ):

Введите описание изображения здесь

Этот алгоритм намного сложнее реализовать, но он намного быстрее, чем алгоритмы AGM.

Затем мы проверяем двоичные цифры, используя формулы BBP для извлечения цифр .

Введите описание изображения здесь

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

Преимущество этого заключается в следующем:

  1. Требуется только одно дорогое вычисление.

Недостатком является:

  1. Реализация Бейли-Borwein-Plouffe (ВВР) формулы требуется.
  2. Дополнительный шаг необходим для проверки преобразования радиуса из двоичного в десятичное.

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


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

Итак, я вытащил этот фрагмент из своего блога:

N = # of decimal digits desired
p = 64-bit prime number

Введите описание изображения здесь

Вычислить A, используя арифметику по основанию 10, а B - двоичную арифметику.

Введите описание изображения здесь

Если A = B, то с «чрезвычайно высокой вероятностью», преобразование является правильным.


Для дальнейшего чтения, см. Мой пост в блоге Pi - 5 триллионов цифр .

Mysticial
источник
15
И чтобы ответить на другой вопрос о том, как узнать, сходится ли конкретный алгоритм к N цифрам: для этого необходимо знать поведение алгоритма сходимости. Серия Тейлора ArcTan(1)логарифмически сходится. Так что вам нужно экспоненциально большое количество терминов, чтобы сходиться - короче, не используйте его.
Мистик
21
Да, формула Чудновского сходится с устойчивыми 14,18 цифрами в семестр. Таким образом, вы можете разделить общее количество цифр на это, чтобы получить, сколько терминов вам нужно. (Точное значение: Log(151931373056000)/Log(10) = 14.181647462725477655...)
Mysticial
7
@ erikb85 Kinda. Формула BBP (в некоторой степени) считается вторым алгоритмом. Но само по себе этого недостаточно, поскольку он не проверяет преобразование в базу 10. Идея использования проверки преобразования BBP + для устранения необходимости во втором вычислении была не моей. Впервые это было сделано Фабрисом Беллардом в его мировом рекорде 2009 года. Это была такая хорошая идея, что мы сделали то же самое и улучшили ее.
Мистика
83
@FunsukWangadu Я могу говорить только за себя, но здесь это так: я никогда не заботился о самом Пи. Для меня это просто еще один номер. Значение не в самом числе или 10 терабайтах бесполезных цифр, это методы , которые используются для его достижения. Века математики и десятилетия компьютерных / программных исследований, которые способствовали этому подвигу, применимы ко многим другим областям и поэтому НАМНОГО более ценны, чем жесткий диск цифр. Проще говоря: вычисление цифр числа Пи - это больше спорт.
Мистика
8
@ Мистический, только что наткнулся на ваш сайт расчета Пи из другого вопроса stackoverflow и не мог не поглазеть и посмеяться над тем, что вы, ребята, сделали. Любил сбои жесткого диска / землетрясения в журналах :) чисто удивительно!
Джо
48

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

И как мы узнаем, что эти значения верны? Ну, я мог бы сказать, что есть компьютерные способы доказать, что реализация алгоритма верна.

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

Исторически в 1873 году Уильям Шенкс опубликовал число до 707 десятичных знаков. Бедный парень, он допустил ошибку, начав с 528-го знака после запятой.

Очень интересно, что в 1995 году был опубликован алгоритм, который имел свойство, которое напрямую вычисляло бы n-ю цифру (основание 16) числа pi без необходимости вычисления всех предыдущих цифр !

Наконец, я надеюсь, что ваш первоначальный алгоритм не был таким, pi/4 = 1 - 1/3 + 1/5 - 1/7 + ...который может быть самым простым в программировании, но это также один из самых медленных способов сделать это. Проверьте пи-статью в Википедии для более быстрых подходов.

Ларри Смит
источник
7
Эта последняя формула (формула Лейбница, iirc) фактически чередует сложение и вычитание.
Томас
21

Вы можете использовать несколько подходов и посмотреть, сходятся ли они к одному и тому же ответу. Или возьмите немного из сети. Алгоритм Чудновского обычно используется как очень быстрый метод вычисления числа Пи. http://www.craig-wood.com/nick/articles/pi-chudnovsky/

argentage
источник
Снижает шансы, но я все еще не могу быть уверен с решением с несколькими подходами, что если оба не правы. Проверка в сети не имеет силы, тогда почему бы не взять значения из самой сети. Я думаю о bbp, какой из них больше подходит?
Ишан Шарма
7
@IshanSharma Если два алгоритма независимы, то вероятность того, что оба вычисления неверны с одинаковыми результатами, почти равна нулю. Если в любом из вычислений что-то пойдет не так, окончательные результаты не будут совпадать - поэтому вы знаете, что хотя бы один из них неверен.
Мистик
15

Ряд Тейлора - один из способов приблизиться к пи. Как уже отмечалось, он сходится медленно.

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

Другие способы аппроксимации пи имеют аналогичные способы вычисления максимальной ошибки.

Мы знаем это, потому что мы можем доказать это математически.

Якк - Адам Невраумонт
источник
Откомандирован. Я думаю, что большинство ответов здесь просто не придают достаточного значения концепции математического доказательства . Какова бы ни была ваша программа для вычисления цифр числа пи, это никогда не будет более убедительным, чем самое убедительное математическое доказательство того, что метод вашей программы действительно рассчитывает число пи. Что предполагает другое ограничение для программ, которые вычисляют число пи: что они должны стремиться к понятности так же, как к производительности и правильности.
Луис Касильяс
5

Вы можете попробовать вычислить sin(pi/2)(или cos(pi/2)в этом отношении), используя (довольно) быстро сходящиеся степенные ряды для sin и cos. (Еще лучше: используйте различные формулы удвоения для вычисления ближе x=0для более быстрой сходимости.)

Кстати, лучше, чем использовать ряды для tan(x), с вычислением, скажем, cos(x)как черный ящик (например, вы можете использовать ряды Тейлора, как указано выше), чтобы делать поиск корней через Ньютон. Конечно, есть лучшие алгоритмы, но если вы не хотите проверять тонны цифр, этого должно быть достаточно (и это не так сложно реализовать, и вам нужно только немного исчисления, чтобы понять, почему это работает.)

user1974703
источник
6
Я не совсем понимаю, как это помогло бы определить, что 1000-я цифра выключена на 1. Вам нужны очень точные значения sin(pi/2), не так ли?
Матье М.
Я не уверен, что сказать о предыдущем ответе, если это не шутка или что-то. sin (pi / 2) = 1 cos (pi / 2) = 0 Итак, я бы сказал, что те, кто уверен, сходятся быстро.
БентФранклин,
15
Полагаю, не всем очевидно, что оценить sin(x)и cos(x)с высокой точностью на самом деле гораздо сложнее, чем вычислить сам Пи.
Мистика
2
По понятным причинам, вы не должны использовать sin (pi / 2) для этого. Лучше вместо этого использовать sin (pi / 6) и убедиться, что он получился ровно 1/2.
Роберт Лозиняк