Алгебраическая обработка этих уравнений дает следующее:
( 3 )
если
Все формулы типа Мачина могут быть получены путем многократного применения уравнения 3 . В качестве примера мы показываем вывод исходной формулы Мачина:
Хороший способ визуализировать уравнение 3 - это представить себе, что происходит, когда два комплексных числа умножаются вместе:
( 4 )
Угол, связанный с комплексным числом дан кем-то:
Таким образом, в уравнении 4 угол, связанный с продуктом, равен:
Обратите внимание, что это то же выражение, что и в уравнении 3 . Таким образом, уравнение 3 можно интерпретировать как утверждение, что действие умножения двух комплексных чисел эквивалентно сложению связанных с ними углов (см. Умножение комплексных чисел ).
Здесь - произвольная константа, которая учитывает разницу в величине между векторами на двух сторонах уравнения. Величинами можно пренебречь, значимы только углы.
Использование комплексных чисел
Другие формулы могут быть созданы с использованием комплексных чисел. Например, угол комплексного числа дан кем-то а при умножении комплексных чисел складываются их углы. Если a = b, то 45 градусов или радианы. Это означает, что если действительная часть и комплексная часть равны, то арктангенс будет равен. Поскольку арктангенс единицы имеет очень медленную скорость сходимости, если мы найдем два комплексных числа, умножение которых даст одну и ту же действительную и мнимую части, мы получим формулу типа Мачина. Примером является а также . Если мы умножим их, мы получим. Следовательно,.
Если вы хотите использовать комплексные числа, чтобы показать, что вы сначала должны знать, что при умножении углов вы кладете комплексное число в степень числа, на которое вы умножаете. Так и поскольку действительная часть и мнимая часть равны, тогда
Мера Лемера
Одним из наиболее важных параметров, характеризующих вычислительную эффективность формулы Мачина, является мера Лемера, определяемая как [2] [3]
.
Чтобы получить как можно меньшую меру Лемера, необходимо уменьшить отношение натуральных чисел в аргументах арктангенса и минимизировать количество членов в формуле типа Мачина. В настоящее время в наименьшая известная мера Лемера благодаря H. Chien-Lih (1997), [4], чья формула типа Мачина показана ниже. В формулах типа Мачина очень часто встречается, когда все целые числа.
Двухчленные формулы
В частном случае, когда , есть ровно четыре решения, состоящие только из двух членов. [5] Это
В общем случае, когда значение не ограничен, существует бесконечно много других решений. Например:
( 5 )
Пример
На соседней диаграмме показана взаимосвязь между арктангенсами и их площадями. Из диаграммы имеем следующее:
соотношение, которое также можно найти с помощью следующего вычисления в комплексных числах
Больше терминов
Рекорд 2002 года для цифр π , 1 241 100 000 000, был получен Ясумасой Канадой из Токийского университета . Расчет производился на 64-узловом суперкомпьютере Hitachi с 1 терабайтом оперативной памяти, выполняющем 2 триллиона операций в секунду. Были использованы следующие два уравнения:
Используются два уравнения, чтобы можно было проверить, что они оба дают одинаковый результат; полезно, если в уравнениях повторно используются некоторые, но не все арктангенсы, поскольку их нужно вычислять только один раз - обратите внимание на повторное использование 57 и 239 выше.
Формулы типа Машина для π могут быть построены путем нахождения набора чисел, в котором при разложении на простые множители n 2 +1 вместе используются не более различных простых чисел, чем количество элементов в наборе, а затем с использованием либо линейной алгебры, либо базиса LLL алгоритм редукции для построения линейных комбинаций. Например, для формулы Стёрмера, приведенной выше, мы имеем
поэтому четыре члена используют между собой только простые числа 2, 5, 13 и 61.
В 1993 году Йорг Уве Арндт [6] нашел 11-членную формулу:
используя набор простых чисел
Другая формула, где 10 из -аргументы те же, что и выше, были обнаружены Hwang Chien-Lih (黃 見 利) (2004), поэтому легче проверить, что оба они дают одинаковый результат:
Вы заметите, что эти формулы повторно используют все те же арктангенсы после первого. Они строятся путем поиска чисел, в которых n 2 +1 делится только на простые числа меньше 102.
Наиболее эффективными в настоящее время известными формулами типа Мачина для вычисления π являются:
(Хван Чиен-Ли, 1997)
где набор простых чисел
Дальнейшее усовершенствование заключается в использовании «Процесса Тодда», как описано в; [7] это приводит к таким результатам, как
(Хван Чиен-Ли, 2003 г.)
где большое простое число 834312889110521 делит n i 2 +1 из двух последних индексов. М. Уэтерфилд обнаружен в 2004 г.
Эффективность
Для больших вычислений , алгоритм двоичного разбиения можно использовать для вычисления арктангенсов намного, намного быстрее, чем путем простого добавления членов в ряд Тейлора по одному. В практических реализациях, таких как y-cruncher, существуют относительно большие постоянные накладные расходы на член плюс время, пропорциональное, и точка убывающей доходности появляется за пределами трех или четырех членов с арктангенсом в сумме; поэтому в приведенном выше вычислении суперкомпьютера использовалась только четырехчленная версия.
Целью этого раздела не является оценка фактического времени выполнения любого заданного алгоритма. Вместо этого цель состоит в том, чтобы просто разработать относительную метрику, с помощью которой можно было бы сравнивать два алгоритма друг с другом.
Позволять быть количеством цифр, до которых подлежит расчету.
Позволять быть количеством членов в ряду Тейлора (см. уравнение 2 ).
Позволять быть количеством времени, потраченного на каждую цифру (для каждого члена в ряду Тейлора).
Ряд Тейлора сойдется, когда:
Таким образом:
Для первого члена в ряду Тейлора все цифры должны быть обработаны. Однако в последнем члене ряда Тейлора остается обработать только одну цифру. Во всех промежуточных терминах количество обрабатываемых цифр может быть аппроксимировано линейной интерполяцией. Таким образом, общая сумма определяется как:
Время работы определяется по формуле:
Комбинируя уравнения, время работы определяется следующим образом:
Где - константа, объединяющая все остальные константы. Поскольку это относительный показатель, значение можно игнорировать.
Общее время по всем условиям уравнения 1 определяется по формуле :
невозможно точно смоделировать без детального знания конкретного программного обеспечения. Тем не менее, мы представляем одну возможную модель.
Программное обеспечение тратит большую часть своего времени на оценку ряда Тейлора по уравнению 2 . Первичный цикл можно резюмировать в следующем псевдокоде:
В этой конкретной модели предполагается, что каждый из этих шагов занимает примерно одинаковое количество времени. В зависимости от используемого программного обеспечения это может быть очень хорошее приближение или плохое.
Единица времени определяется так, что один шаг псевдокода соответствует одной единице. Для полного выполнения цикла требуется четыре единицы времени. определяется как четыре.
Обратите внимание, однако, что если равно единице, то шаг можно пропустить. Цикл занимает всего три единицы времени. определяется как три.
В качестве примера рассмотрим уравнение:
( 6 )
В следующей таблице показано расчетное время для каждого из условий:
74684
14967113
200,41
5,3003
4
0,75467
1
239
239,00
5,4765
3
0,54780
20138
15351991
762,34
6,6364
4
0,60274
Общее время 0,75467 + 0,54780 + 0,60274 = 1,9052
Сравните это с уравнением 5 . В следующей таблице показано расчетное время для каждого из условий:
24478
873121
35,670
3,5743
4
1,1191
685601
69049993
100,71
4,6123
4
0,8672
Общее время 1,1191 + 0,8672 = 1,9863
Вывод, основанный на этой конкретной модели, заключается в том, что уравнение 6 немного быстрее, чем уравнение 5 , независимо от того, что уравнение 6 имеет больше членов. Такой результат типичен для общей тенденции. Доминирующим фактором является соотношение между а также . Чтобы добиться высокого коэффициента, необходимо добавить дополнительные условия. Часто получается чистая экономия времени.
Рекомендации
Перейти ↑ Beckmann, Petr (1971). История Пи . США: The Golem Press. п. 102 . ISBN 0-88029-418-3.
^Лемер, Деррик Генри. «Об отношениях арккотангенса для π». Американский математический ежемесячник . 45 (10). JSTOR 2302434 .
^Уэтерфилд, Майкл. «Улучшение формулы Мачина с помощью процесса Тодда». Математический вестник . 80 (488). JSTOR 3619567 .
^ а бКарл Стёрмер (1899). "Полное решение по номеру вопроса" м арктан 1 Икс + п арктан 1 у знак равно k π 4 {\ displaystyle m \ arctan {\ frac {1} {x}} + n \ arctan {\ frac {1} {y}} = k {\ frac {\ pi} {4}}}
" (PDF) . Бюллетень де ла SMF (на французском языке). 27 : 160-170.
^ Йорг Уве Арндт: "Вопросы Computational" раздел 32.5.2, стр 637.
^Уэтерфилд, Майкл. «Улучшение формулы Мачина с помощью процесса Тодда». Математический вестник . 80 (488). JSTOR 3619567 .
Внешние ссылки
Вайсштейн, Эрик В. "Формулы типа Машина" . MathWorld .