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




срок окупаемости формула (4)

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

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


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


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

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


Поскольку я являюсь держателем мирового рекордсмена для большинства цифр 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 триллионов цифр .


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

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

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

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







pi