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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Формула типа машины»  -  новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2011 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

который он использовал для вычисления числа π до 100 знаков после запятой. ^[1]

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

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

( 1 )

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

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

${\ displaystyle \ 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}} + ...}$

( 2 )

Вывод [ править ]

Следующие уравнения были выведены в формуле сложения углов :

${\ Displaystyle \ грех (\ альфа + \ бета) = \ грех \ альфа \ соз \ бета + \ соз \ альфа \ грех \ бета}$

${\ Displaystyle \ соз (\ альфа + \ бета) = \ соз \ альфа \ соз \ бета - \ грех \ альфа \ грех \ бета}$

Алгебраическая обработка этих уравнений дает следующее:

${\ displaystyle \ 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 )

если

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

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

${\displaystyle 2\arctan {\frac {1}{5}}}$

${\displaystyle =\arctan {\frac {1}{5}}+\arctan {\frac {1}{5}}}$

${\displaystyle =\arctan {\frac {1*5+1*5}{5*5-1*1}}}$

${\displaystyle =\arctan {\frac {10}{24}}}$

${\displaystyle =\arctan {\frac {5}{12}}}$

${\displaystyle 4\arctan {\frac {1}{5}}}$

${\displaystyle =2\arctan {\frac {1}{5}}+2\arctan {\frac {1}{5}}}$

${\displaystyle =\arctan {\frac {5}{12}}+\arctan {\frac {5}{12}}}$

${\displaystyle =\arctan {\frac {5*12+5*12}{12*12-5*5}}}$

${\displaystyle =\arctan {\frac {120}{119}}}$

${\displaystyle 4\arctan {\frac {1}{5}}-{\frac {\pi }{4}}}$

${\displaystyle =4\arctan {\frac {1}{5}}-\arctan {\frac {1}{1}}}$

${\displaystyle =4\arctan {\frac {1}{5}}+\arctan {\frac {-1}{1}}}$

${\displaystyle =\arctan {\frac {120}{119}}+\arctan {\frac {-1}{1}}}$

${\displaystyle =\arctan {\frac {120*1+(-1)*119}{119*1-120*(-1)}}}$

${\displaystyle =\arctan {\frac {1}{239}}}$

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

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

${\displaystyle (b_{1}+a_{1}i)*(b_{2}+a_{2}i)}$

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

${\displaystyle =(b_{1}b_{2}-a_{1}a_{2})+(a_{1}b_{2}+a_{2}b_{1})*i}$

( 4 )

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

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

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

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

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

Выражение:

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

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

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

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

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

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

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

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

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

Мера Лемера [ править ]

Одним из наиболее важных параметров, характеризующих вычислительную эффективность формулы Мачина, является мера Лемера, определяемая как ^{[2] [3]}

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

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

Двухчленные формулы [ править ]

В частном случае, когда есть ровно четыре решения, состоящие только из двух членов. ^[5] Это${\displaystyle a_{n}=1}$

Эйлера :

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

Германа:

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

Хаттона (или Веги ^[5] ):

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

и Мачина:

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

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

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

( 5 )

Пример [ править ]

На соседней диаграмме показана взаимосвязь между арктангенсами и их площадями. Из диаграммы имеем следующее:

${\displaystyle {\begin{aligned}{\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{aligned}}}$

Дополнительные условия [ править ]

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

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

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

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

FCM Störmer (1896 г.).

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

Формулы типа Мачина для pi могут быть построены путем нахождения набора чисел, в котором при разложении на простые множители n ^ 2 + 1 вместе используются не более различных простых чисел, чем количество элементов в наборе, а затем с использованием либо линейной алгебры, либо базиса LLL -средуцирующий алгоритм построения линейных комбинаций . Например, для формулы Стёрмера, приведенной выше, мы имеем${\displaystyle \arctan {\frac {1}{n_{i}}}}$

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

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

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

${\displaystyle 12943^{2}+1=2*5^{4}*13*61}$

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

Наиболее эффективная в настоящее время известная пара формул типа Мачина, открытая Хвангом Чиен-Ли (黃 見 利) (2004) для вычисления π :

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

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

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

${\displaystyle {\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}

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

${\displaystyle {\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 появляется в n ^ 2 + 1 для обоих последних двух индексов

${\displaystyle {\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}}}$

(М. Уэтерфилд, 2004 г.)

Эффективность [ править ]

Для больших вычислений числа пи алгоритм двоичного разбиения можно использовать для вычисления арктангенсов намного, намного быстрее, чем путем простого добавления членов в ряд Тейлора по одному. В практических реализациях, таких как y-cruncher, существуют относительно большие постоянные накладные расходы на член плюс время, пропорциональное 1 / log (b_n), и точка убывающей отдачи появляется за пределами трех или четырех членов арктангенса в сумме; поэтому в приведенном выше вычислении суперкомпьютера использовалась только четырехчленная версия.

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

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

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

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

Ряд Тейлора сойдется, когда:

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

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

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

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

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

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

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

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

${\displaystyle time={\frac {u_{n}{N_{d}}^{2}\ln 10}{4\ln {\frac {b_{n}}{a_{n}}}}}={\frac {ku_{n}}{\ln {\frac {b_{n}}{a_{n}}}}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

( 6 )

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

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

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. "Формулы типа Машина" . MathWorld .
• Постоянная π
• Заслуга Мачина в MathPages