Машиноподобная формула

В математике формулы , подобные машинам, — популярный метод вычисления π (отношения длины окружности к диаметру круга ) с большим количеством цифр . Они являются обобщением формулы Джона Мэчина 1706 года:

${\frac {\pi }{4}}=4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}$

который он использовал для вычисления числа π с точностью до 100 десятичных знаков.

Машиноподобные формулы имеют вид

$c_{0}{\frac {\pi }{4}}=\sum _{n=1}^{N}c_{n}\arctan {\frac {a_{n}}{b_{n}}}$ ( 1 )

где $c_{0}$ является положительным целым числом, $c_{n}$ являются знаковыми ненулевыми целыми числами , а $a_{n}$ и $b_{n}$ являются целыми положительными числами такими, что $a_{n}<b_{n}$.

Эти формулы используются вместе с рядом Грегори , в ряд Тейлора разложением арктангенса :

$\arctan x=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}x^{2n+1}=x-{\frac {x^{3}}{3}}+{\frac {x^{5}}{5}}-{\frac {x^{7}}{7}}+\cdots$ ( 2 )

Вывод

Формула сложения углов для арктангенса утверждает, что

$\arctan {\frac {a_{1}}{b_{1}}}+\arctan {\frac {a_{2}}{b_{2}}}=\arctan {\frac {a_{1}b_{2}+a_{2}b_{1}}{b_{1}b_{2}-a_{1}a_{2}}},$ ( 3 )

если

$$-{\frac {\pi }{2}}<\arctan {\frac {a_{1}}{b_{1}}}+\arctan {\frac {a_{2}}{b_{2}}}<{\frac {\pi }{2}}.$$

Все формулы типа Машины могут быть получены путем многократного применения уравнения 3 . В качестве примера мы покажем вывод исходной формулы Мачина:

$${\begin{aligned}2\arctan {\frac {1}{5}}&=\arctan {\frac {1}{5}}+\arctan {\frac {1}{5}}\\&=\arctan {\frac {1\cdot 5+1\cdot 5}{5\cdot 5-1\cdot 1}}\\&=\arctan {\frac {10}{24}}\\&=\arctan {\frac {5}{12}},\end{aligned}}$$

и, следовательно,

$${\begin{aligned}4\arctan {\frac {1}{5}}&=2\arctan {\frac {1}{5}}+2\arctan {\frac {1}{5}}\\&=\arctan {\frac {5}{12}}+\arctan {\frac {5}{12}}\\&=\arctan {\frac {5\cdot 12+5\cdot 12}{12\cdot 12-5\cdot 5}}\\&=\arctan {\frac {120}{119}}.\end{aligned}}$$

Поэтому также

$${\begin{aligned}4\arctan {\frac {1}{5}}-{\frac {\pi }{4}}&=4\arctan {\frac {1}{5}}-\arctan {\frac {1}{1}}\\&=4\arctan {\frac {1}{5}}+\arctan {\frac {-1}{1}}\\&=\arctan {\frac {120}{119}}+\arctan {\frac {-1}{1}}\\&=\arctan {\frac {120\cdot 1+(-1)\cdot 119}{119\cdot 1-120\cdot (-1)}}\\&=\arctan {\frac {1}{239}},\end{aligned}}$$

и так наконец

$${\frac {\pi }{4}}=4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}.$$

Проницательный способ визуализировать уравнение 3 — это представить, что происходит, когда два комплексных числа умножаются:

$(b_{1}+a_{1}\mathrm {i} )\cdot (b_{2}+a_{2}\mathrm {i} )$

$=b_{1}b_{2}+a_{2}b_{1}\mathrm {i} +a_{1}b_{2}\mathrm {i} -a_{1}a_{2}$

$=(b_{1}b_{2}-a_{1}a_{2})+(a_{1}b_{2}+a_{2}b_{1})\cdot \mathrm {i}$ ( 4 )

Угол, связанный с комплексным числом $(b_{n}+a_{n}\mathrm {i} )$ дается:

$\arctan {\frac {a_{n}}{b_{n}}}$

Таким образом, в уравнении 4 угол, связанный с произведением, равен:

$\arctan {\frac {a_{1}b_{2}+a_{2}b_{1}}{b_{1}b_{2}-a_{1}a_{2}}}$

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

Выражение:

$c_{n}\arctan {\frac {a_{n}}{b_{n}}}$

угол, связанный с:

$(b_{n}+a_{n}\mathrm {i} )^{c_{n}}$

Уравнение 1 можно переписать так:

$k\cdot (1+\mathrm {i} )^{c_{0}}=\prod _{n=1}^{N}(b_{n}+a_{n}\mathrm {i} )^{c_{n}}$

Здесь $k$ — произвольная константа, которая учитывает разницу в величине между векторами в двух частях уравнения. Величинами можно пренебречь, важны только углы.

Использование комплексных чисел

Другие формулы могут быть созданы с использованием комплексных чисел. Например, угол комплексного числа ${\textstyle (a+b\mathrm {i} )}$ дается ${\textstyle \arctan {\frac {b}{a}}}$ и когда кто-то умножает комплексные числа, он складывает их углы. Если ${\textstyle a=b}$ затем ${\textstyle \arctan {\frac {b}{a}}}$ составляет 45 градусов или ${\textstyle {\frac {\pi }{4}}}$ радианы. Это означает, что если действительная часть и комплексная часть равны, то арктангенс будет равен ${\textstyle {\frac {\pi }{4}}}$. Поскольку арктангенс единицы имеет очень медленную скорость сходимости, если мы найдем два комплексных числа, которые при умножении приведут к одной и той же действительной и мнимой части, мы получим формулу, подобную Машину. Примером является ${\textstyle (2+\mathrm {i} )}$ и ${\textstyle (3+\mathrm {i} )}$. Если мы умножим это, мы получим ${\textstyle (5+5\mathrm {i} )}$. Поэтому, ${\textstyle \arctan {\frac {1}{2}}+\arctan {\frac {1}{3}}={\frac {\pi }{4}}}$.

Если вы хотите использовать комплексные числа, чтобы показать это ${\textstyle {\frac {\pi }{4}}=4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}}$ Прежде всего вы должны знать, что при умножении углов вы возводите комплексное число в степень числа, на которое умножаете. Так ${\textstyle (5+\mathrm {i} )^{4}(239-\mathrm {i} )=(1+\mathrm {i} )\cdot 2^{2}\cdot 13^{4}}$ и поскольку действительная часть и мнимая часть равны, то ${\textstyle 4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}={\frac {\pi }{4}}~.}$

Мера Лемера

Одним из наиболее важных параметров, характеризующих вычислительную эффективность формулы типа Машины, является мера Лемера, определяемая как

${\it {\lambda }}=\sum _{n=1}^{N}{\frac {1}{\log _{10}(b_{n}/a_{n})}}$.

Чтобы получить как можно меньшую меру Лемера, необходимо уменьшить отношение целых положительных чисел $a_{n}/b_{n}$ в аргументах арктангенса и минимизировать количество членов в формуле, подобной Машину. В настоящее время в $a_{n}=1$ наименьшая известная мера Лемера равна $\lambda \approx 1.51244$ благодаря Х. Чиен-Ли (1997), чья машиноподобная формула показана ниже . В формулах, подобных Машину, очень часто встречаются случаи, когда все числители $a_{n}=1~.$

Двухчленные формулы

В частном случае, когда числитель $a_{n}=1$, существует ровно четыре решения, имеющих только два члена. Все четыре были найдены Джоном Мачином в 1705–1706 годах, но только один из них стал широко известен, когда был опубликован в Уильяма Джонса книге Synopsis Palmariorum Matheseos , поэтому остальные три часто приписывают другим математикам. Это

1737 г. Эйлера (известен Машину в 1706 г.):

${\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}}$

1706 г. Германа (известен Машину 1706 г.):

${\frac {\pi }{4}}=2\arctan {\frac {1}{2}}-\arctan {\frac {1}{7}}$

Хаттона или Веги (известных Мачину в 1706 г.):

${\frac {\pi }{4}}=2\arctan {\frac {1}{3}}+\arctan {\frac {1}{7}}$

и Мэчина 1706 г.:

${\frac {\pi }{4}}=4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}$ .

В общем случае, когда значение числителя $a_{n}$ не ограничено, существует бесконечно много других решений. Например:

${\frac {\pi }{4}}=22\arctan {\frac {1}{28}}+\arctan {\frac {1744507482180328366854565127}{98646395734210062276153190241239}}$

или

${\frac {\pi }{4}}=22\arctan {\frac {24478}{873121}}+17\arctan {\frac {685601}{69049993}}$ ( 5 )

Пример

Прилегающая диаграмма демонстрирует взаимосвязь между арктангенсами и их площадями. Судя по схеме, имеем следующее:

${\begin{array}{ll}{\rm {area}}(PON)&={\rm {area}}(MOF)=\pi \times {\frac {\angle MOF}{2\pi }}=\angle MEF=\arctan {1 \over 2}\\{\rm {area}}(POM)&={\rm {area}}(NOF)=\arctan {1 \over 3}\\{\rm {area}}(POF)&={\pi \over 4}=\arctan {1 \over 2}+\arctan {1 \over 3}\\{\rm {area}}(MON)&=\arctan {1 \over 7}\\\arctan {1 \over 2}&=\arctan {1 \over 3}+\arctan {1 \over 7},\end{array}}$

отношение, которое также можно найти с помощью
следующий расчет внутри комплексных чисел

$(3+\mathrm {i} )(7+\mathrm {i} )=21-1+(3+7)\mathrm {i} =10\cdot (2+\mathrm {i} ).$

Дополнительные термины

Рекорд 2002 года по количеству цифр π , 1 241 100 000 000, был получен Ясумасой Канадой из Токийского университета . Расчет проводился на 64-узловом Hitachi суперкомпьютере с 1 терабайтом оперативной памяти, выполняющем 2 триллиона операций в секунду. Использовались следующие два уравнения:

${\frac {\pi }{4}}=12\arctan {\frac {1}{49}}+32\arctan {\frac {1}{57}}-5\arctan {\frac {1}{239}}+12\arctan {\frac {1}{110443}}$

Кикуо Такано (1982).

${\frac {\pi }{4}}=44\arctan {\frac {1}{57}}+7\arctan {\frac {1}{239}}-12\arctan {\frac {1}{682}}+24\arctan {\frac {1}{12943}}$

FCM Стёрмер (1896 г.).

Два уравнения используются для того, чтобы можно было проверить, что они оба дают одинаковый результат; полезно, если в уравнениях повторно используются некоторые, но не все арктангенсы, поскольку их нужно вычислить только один раз - обратите внимание на повторное использование 57 и 239 выше.

Машинные формулы для π можно построить, найдя набор чисел, в котором простые факторизации $b^{2}+1$ вместе используют не больше различных простых чисел, чем число элементов в наборе, а затем используют линейную алгебру или алгоритм уменьшения базиса LLL для построения линейных комбинаций арктангенсов. $\arctan {\tfrac {1}{b_{n}}}$ обратных целых знаменателей $b_{n}$. Например, для приведенной выше формулы Стёрмера мы имеем

$57^{2}+1=2\cdot 5^{3}\cdot 13$

$239^{2}+1=2\cdot 13^{4}$

$682^{2}+1=5^{3}\cdot 61^{2}$

$12943^{2}+1=2\cdot 5^{4}\cdot 13^{3}\cdot 61$

таким образом, четыре термина, в которых между собой используются только простые числа 2, 5, 13 и 61.

В 1993 году Йорг Уве Арндт нашел формулу из 11 членов:

${\begin{aligned}{\frac {\pi }{4}}=&\;36462\arctan {\frac {1}{390112}}+135908\arctan {\frac {1}{485298}}+274509\arctan {\frac {1}{683982}}\\&-39581\arctan {\frac {1}{1984933}}+178477\arctan {\frac {1}{2478328}}-114569\arctan {\frac {1}{3449051}}\\&-146571\arctan {\frac {1}{18975991}}+61914\arctan {\frac {1}{22709274}}-69044\arctan {\frac {1}{24208144}}\\&-89431\arctan {\frac {1}{201229582}}-43938\arctan {\frac {1}{2189376182}}\\\end{aligned}}$

используя набор из 11 простых чисел $\{2,5,13,17,29,37,53,61,89,97,101\}.$

Другая формула, где 10 из $\arctan$-аргументы такие же, как указано выше, было обнаружено Хван Чиен-Лихом (黃見利) (2004), поэтому легче проверить, что они оба дают одинаковый результат:

${\begin{aligned}{\frac {\pi }{4}}=&\;36462\arctan {\frac {1}{51387}}+26522\arctan {\frac {1}{485298}}+19275\arctan {\frac {1}{683982}}\\&-3119\arctan {\frac {1}{1984933}}-3833\arctan {\frac {1}{2478328}}-5183\arctan {\frac {1}{3449051}}\\&-37185\arctan {\frac {1}{18975991}}-11010\arctan {\frac {1}{22709274}}+3880\arctan {\frac {1}{24208144}}\\&-16507\arctan {\frac {1}{201229582}}-7476\arctan {\frac {1}{2189376182}}\\\end{aligned}}$

Вы заметите, что в этих формулах повторно используются все те же арктангенсы после первой. Они строятся путем поиска чисел, где $b^{2}+1$ делится только на простые числа меньше 102.

Наиболее эффективная известная в настоящее время формула типа Машин для вычисления π :

${\begin{aligned}{\frac {\pi }{4}}=&\;183\arctan {\frac {1}{239}}+32\arctan {\frac {1}{1023}}-68\arctan {\frac {1}{5832}}\\&+12\arctan {\frac {1}{110443}}-12\arctan {\frac {1}{4841182}}-100\arctan {\frac {1}{6826318}}\\\end{aligned}}$

(Хван Чиен-Ли, 1997)

где множество простых чисел $\{2,5,13,229,457,1201\}.$

Дальнейшее усовершенствование заключается в использовании «Процесса Тодда», как описано в; это приводит к таким результатам, как

${\begin{aligned}{\frac {\pi }{4}}=&\;183\arctan {\frac {1}{239}}+32\arctan {\frac {1}{1023}}-68\arctan {\frac {1}{5832}}\\&+12\arctan {\frac {1}{113021}}-100\arctan {\frac {1}{6826318}}\\&-12\arctan {\frac {1}{33366019650}}+12\arctan {\frac {1}{43599522992503626068}}\\\end{aligned}}$

(Хван Чиен Ли, 2003 г.)

где большое простое число 834312889110521 делит $b_{n}^{2}+1$ из двух последних индексов.
М. Уэтерфилд основал 2004 г.

${\begin{aligned}{\frac {\pi }{4}}=&\;83\arctan {\frac {1}{107}}+17\arctan {\frac {1}{1710}}-22\arctan {\frac {1}{103697}}\\&-24\arctan {\frac {1}{2513489}}-44\arctan {\frac {1}{18280007883}}\\&+12\arctan {\frac {1}{7939642926390344818}}\\&+22\arctan {\frac {1}{3054211727257704725384731479018}}.\\\end{aligned}}$

В День числа Пи 2024 года Мэтт Паркер вместе с 400 добровольцами использовал следующую формулу для ручного расчета: $\pi$:

${\begin{aligned}{\frac {\pi }{4}}=&\;1587\arctan {\frac {1}{2852}}+295\arctan {\frac {1}{4193}}+593\arctan {\frac {1}{4246}}\\&+359\arctan {\frac {1}{39307}}+481\arctan {\frac {1}{55603}}+625\arctan {\frac {1}{211050}}\\&-708\arctan {\frac {1}{390112}}\end{aligned}}$

Это был самый крупный ручной расчет $\pi$ в столетии.

Дополнительные методы

Существуют и другие методы вывода формул типа Машины для $\pi$ с обратными целыми числами. Один из них определяется следующей формулой:

${\frac {\pi }{4}}=2^{k-1}\cdot \arctan {\frac {1}{A_{k}}}+\sum \limits _{m=1}^{M}\arctan {\frac {1}{\left\lfloor B_{k,m}\right\rfloor }}+\arctan {\frac {1}{B_{k,M+1}}},$

где

$a_{0}:=0$

и рекурсивно

$a_{k}:={\sqrt {2+a_{k-1}}},\;A_{k}:=\left\lfloor {\frac {a_{k}}{\sqrt {2-a_{k-1}}}}\right\rfloor$

и

$B_{k,1}:={\frac {2}{\left({\dfrac {A_{k}+\mathrm {i} }{A_{k}-\mathrm {i} }}\right)^{2^{k-1}}-\mathrm {i} }}-\mathrm {i}$

и рекурсивно

$B_{k,m}:={\frac {1+\left\lfloor B_{k,m-1}\right\rfloor B_{k,m-1}}{\left\lfloor B_{k,m-1}\right\rfloor -B_{k,m-1}}}~.$

Например, для $k=4$ и $M=5$ мы получаем:

${\begin{aligned}{\frac {\pi }{4}}=&\;8\arctan {\frac {1}{10}}-\arctan {\frac {1}{84}}-\arctan {\frac {1}{21342}}\\&-\arctan {\frac {1}{991268848}}-\arctan {\frac {1}{193018008592515208050}}\\&-\arctan {\frac {1}{197967899896401851763240424238758988350338}}\\&-\arctan {\frac {1}{117573868168175352930277752844194126767991915008537018836932014293678271636885792397}}\end{aligned}}$

Это подтверждается следующим кодом MuPAD:

z:=(10+I)^8*(84-I)*(21342-I)*(991268848-I)*(193018008592515208050-I)\
  *(197967899896401851763240424238758988350338-I)\
  *(117573868168175352930277752844194126767991915008537018836932014293678271636885792397-I):
Re(z)-Im(z)
0

значение

${\begin{aligned}z:=&\,(10+\mathrm {i} )^{8}\cdot (84-\mathrm {i} )\cdot (21342-\mathrm {i} )\cdot (991268848-\mathrm {i} )\cdot (193018008592515208050-\mathrm {i} )\\&\cdot (197967899896401851763240424238758988350338-\mathrm {i} )\\&\cdot (117573868168175352930277752844194126767991915008537018836932014293678271636885792397-\mathrm {i} )\\\;=&\,(1+\mathrm {i} )\cdot \Re (z)~.\end{aligned}}$

Эффективность

Для больших вычислений $\pi$Алгоритм двоичного расщепления можно использовать для вычисления арктангенсов гораздо быстрее, чем путем простого добавления членов ряда Тейлора по одному. В практических реализациях, таких как y-cruncher, на каждый термин приходится относительно большие постоянные накладные расходы плюс время, пропорциональное $1/\log b_{n}$, и точка убывающей доходности появляется за пределами трех или четырех арктангенсных членов суммы; вот почему в приведенном выше расчете на суперкомпьютере использовалась только четырехчленная версия.

Целью этого раздела не является оценка фактического времени работы того или иного алгоритма. Вместо этого намерение состоит в том, чтобы просто разработать относительную метрику, с помощью которой два алгоритма можно будет сравнивать друг с другом.

Позволять $N_{d}$ быть числом цифр, до которых $\pi$ предстоит рассчитать.

Позволять $N_{t}$ — количество членов в ряду Тейлора (см. уравнение 2 ).

Позволять $u_{n}$ — количество времени, затраченное на каждую цифру (для каждого члена ряда Тейлора).

Ряд Тейлора сходится, если:

$\left(\left({\frac {b_{n}}{a_{n}}}\right)^{2}\right)^{N_{t}}=10^{N_{d}}$

Таким образом:

$N_{t}=N_{d}\quad {\frac {\ln 10}{2\ln {\frac {b_{n}}{a_{n}}}}}$

Для первого члена ряда Тейлора все $N_{d}$ цифры должны быть обработаны. Однако в последнем члене ряда Тейлора осталось обработать только одну цифру. Во всех промежуточных терминах количество цифр, подлежащих обработке, может быть аппроксимировано линейной интерполяцией. Таким образом, общая сумма определяется следующим образом:

${\frac {N_{d}N_{t}}{2}}$

Время работы определяется:

${\mathit {time}}={\frac {u_{n}N_{d}N_{t}}{2}}$

Объединив уравнения, время выполнения определяется следующим образом:

${\mathit {time}}={\frac {u_{n}{N_{d}}^{2}\ln 10}{4\ln {\frac {b_{n}}{a_{n}}}}}={\frac {k\,u_{n}}{\ln {\frac {b_{n}}{a_{n}}}}}$

Где $k$ — константа, объединяющая все остальные константы. Поскольку это относительный показатель, значение $k$ можно игнорировать.

Общее время для всех членов уравнения 1 определяется выражением:

${\mathit {time}}=\sum _{n=1}^{N}{\frac {u_{n}}{\ln {\frac {b_{n}}{a_{n}}}}}$

$u_{n}$ невозможно точно смоделировать без детального знания конкретного программного обеспечения. Тем не менее, мы представляем одну из возможных моделей.

Программное обеспечение тратит большую часть своего времени на оценку ряда Тейлора по уравнению 2 . Основной цикл можно резюмировать в следующем псевдокоде:

$1:\quad {\mathit {term}}\quad *=\quad {a_{n}}^{2}$

$2:\quad {\mathit {term}}\quad /=\quad -{b_{n}}^{2}$

$3:\quad {\mathit {tmp}}\quad =\quad {\mathit {term}}\quad /\quad (2*n+1)$

$4:\quad {\mathit {sum}}\quad +=\quad {\mathit {tmp}}$

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

Единица времени определяется так, что один шаг псевдокода соответствует одной единице. Для полного выполнения цикла требуется четыре единицы времени. $u_{n}$ определено как четыре.

Однако обратите внимание, что если $a_{n}$ равно единице, то первый шаг можно пропустить. Цикл занимает всего три единицы времени. $u_{n}$ определяется как три.

В качестве примера рассмотрим уравнение:

${\frac {\pi }{4}}=44\arctan {\frac {74684}{14967113}}+139\arctan {\frac {1}{239}}-12\arctan {\frac {20138}{15351991}}$ ( 6 )

В следующей таблице показано расчетное время для каждого из условий:

$a_{n}$	$b_{n}$	${\frac {b_{n}}{a_{n}}}$	$\ln {\frac {b_{n}}{a_{n}}}$	$u_{n}$	${\mathit {time}}$
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 . В следующей таблице показано расчетное время для каждого из условий:

$a_{n}$	$b_{n}$	${\frac {b_{n}}{a_{n}}}$	$\ln {\frac {b_{n}}{a_{n}}}$	$u_{n}$	${\mathit {time}}$
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 содержит больше членов. Этот результат типичен для общей тенденции. Доминирующим фактором является соотношение между $a_{n}$ и $b_{n}$. Чтобы добиться высокого коэффициента, необходимо добавить дополнительные условия. Часто получается чистая экономия времени.

Внешние ссылки

• Вайсштейн, Эрик В. «Машиноподобные формулы» . Математический мир .
• Константа π
• Заслуги Машины на MathPages