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

Ответ 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостаток:

• Необходима реализация формулы

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

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

  ---

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

Ответ 2

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

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

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

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

Ответ 5

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

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