algorithm формула - Как определить, является ли мой расчет pi точным?




срок окупаемости (5)

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

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

Поэтому при написании программы я столкнулся с проблемой, как и со всеми алгоритмами. Откуда я знаю, что n цифр, которые я рассчитал, точны?


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

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

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

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

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

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


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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

Преимуществом этого является:

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

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

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

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

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

Поэтому я снял этот фрагмент из своего блога:

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

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

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

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


Вы должны использовать формулу Бэйли – Боруйна – Плуффа

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

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

Итак, в целом, формула BBP позволит вам вычислять цифры числа Пи отдельно (алгоритм очень крутой) и с процессорами с «низкой точностью»! Прочитайте «алгоритм извлечения цифр BBP для π»

Преимущества алгоритма BBP для вычисления π Этот алгоритм вычисляет π, не требуя пользовательских типов данных, имеющих тысячи или даже миллионы цифр . Метод вычисляет n-ю цифру без вычисления первых n-1 цифр и может использовать небольшие эффективные типы данных . Алгоритм является самым быстрым способом вычисления n-й цифры (или нескольких цифр в окрестности n-й), но алгоритмы π-вычислений, использующие большие типы данных, остаются быстрее, когда цель состоит в том, чтобы вычислить все цифры от 1 до n.





algorithm math language-agnostic pi