метод FEE

В математике метод FEE , или метод быстрого вычисления Е-функции , — это метод быстрого суммирования рядов специального вида. Его построила в 1990 году Екатерина Карацуба. и назван так потому, что делает возможным быстрое вычисление Зигеля E -функций , в частности $e^{x}$.

Классу функций, «похожих на показательную функцию», Карл Людвиг Зигель дал название «Е-функции» . Среди этих функций есть такие специальные функции , как гипергеометрическая функция , цилиндр , сферические функции и так далее.

Используя ФЭЭ, можно доказать следующую теорему:

Теорема : Пусть $y=f(x)$ быть элементарной трансцендентной функцией , то есть показательной функцией , или тригонометрическая функция , или элементарная алгебраическая функция , или их суперпозиция, или их обратная , или суперпозиция обратных. Затем

$s_{f}(n)=O(M(n)\log ^{2}n).\,$

Здесь $s_{f}(n)$ – сложность вычисления (бит) функции $f(x)$ с точностью до $n$ цифры, $M(n)$ это сложность умножения двух $n$-цифровые целые числа.

К алгоритмам, основанным на методе FEE, относятся алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого значения аргумента, классических констант e , $\pi ,$ Эйлера постоянная $\gamma ,$ Каталана , и константы Апери такие высшие трансцендентные функции, как гамма-функция Эйлера и ее производные, гипергеометрическая , сферический , цилиндр (в том числе Бесселя ) функции и некоторые другие функции для алгебраические значения аргумента и параметров, дзета-функция Римана для целых значений аргумента и дзета-функция Гурвица для целочисленного аргумента и алгебраических значений параметра, а также такие специальные интегралы, как интеграл вероятности , интегралы Френеля , интегральная показательная функция , тригонометрические интегралы и некоторые другие интегралы. для алгебраических значений аргумента с оценкой сложности, близкой к оптимальной, а именно

$s_{f}(n)=O(M(n)\log ^{2}n).\,$

ФЭЭ позволяет быстро вычислять значения функций из класса высших трансцендентных функций, некоторые специальные интегралы математической физики и такие классические константы, как константы Эйлера, Каталана. и константы Апери. Дополнительным преимуществом метода FEE является возможность распараллеливания алгоритмов на основе FEE.

FEE вычисление классических констант

Для быстрой оценкипостоянный $\pi ,$ можно использовать формулу Эйлера ${\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},$и примените FEE для суммирования ряда Тейлора для

$\arctan {\frac {1}{2}}={\frac {1}{1\cdot 2}}-{\frac {1}{3\cdot 2^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)2^{2r-1}}}+R_{1},$

$\arctan {\frac {1}{3}}={\frac {1}{1\cdot 3}}-{\frac {1}{3\cdot 3^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)3^{2r-1}}}+R_{2},$

с остальными условиями $R_{1},$ $R_{2},$ которые удовлетворяют границам

$|R_{1}|\leq {\frac {4}{5}}{\frac {1}{2r+1}}{\frac {1}{2^{2r+1}}};$

$|R_{2}|\leq {\frac {9}{10}}{\frac {1}{2r+1}}{\frac {1}{3^{2r+1}}};$

и для

$r=n,\,$

$4(|R_{1}|+|R_{2}|)\ <\ 2^{-n}.$

Чтобы рассчитать $\pi$ поFEE можно использовать и другие приближения Во всех случаях сложность

$s_{\pi }=O(M(n)\log ^{2}n).\,$

Вычислить константу Эйлера-гамма с точностью до $n$цифр, необходимо просуммировать КОМИССИЮ двух рядов. А именно, для

$m=6n,\quad k=n,\quad k\geq 1,\,$

$\gamma =-\log n\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!}}+\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!(r+1)}}+O(2^{-n}).$

Сложность

$s_{\gamma }=O(M(n)\log ^{2}n).\,$

Чтобы быстро оценить константу $\gamma$ можно применитьПЛАТА для других приближений.

Вычисление FEE определенных степенных рядов

По FEE быстро рассчитываются две следующие серии:

$f_{1}=f_{1}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}z^{j},$

$f_{2}=f_{2}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}{\frac {z^{j}}{j!}},$

в предположении, что $a(j),\quad b(j)$ являютсяцелые числа,

$|a(j)|+|b(j)|\leq (Cj)^{K};\quad |z|\ <\ 1;\quad K$

и $C$ являются константами, а $z$ является алгебраическим числом. Сложность оценки серии составляет

$s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),\,$

$s_{f_{2}}(n)=O\left(M(n)\log n\right).$

FEE расчет классической константы e

Для оценки константы $e$ брать $m=2^{k},\quad k\geq 1$, члены ряда Тейлора для $e,$

$e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}+R_{m}.$

Здесь мы выбираем $m$, требуя, чтобы оставшаяся часть $R_{m}$ тотнеравенство $R_{m}\leq 2^{-n-1}$ выполняется. Это тот случай, длянапример, когда $m\geq {\frac {4n}{\log n}}.$ Таким образом, мы принимаем $m=2^{k}$такое, что натуральное число $k$ определяетсянеравенства:

$2^{k}\geq {\frac {4n}{\log n}}>2^{k-1}.$

Подсчитываем сумму

$S=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}=\sum _{j=0}^{m-1}{\frac {1}{(m-1-j)!}},$

в $k$ этапы следующего процесса.

Шаг 1. Объединение $S$ слагаемые последовательно попарно мывыносим за скобки «очевидный» общий делитель и получаем

${\begin{aligned}S&=\left({\frac {1}{(m-1)!}}+{\frac {1}{(m-2)!}}\right)+\left({\frac {1}{(m-3)!}}+{\frac {1}{(m-4)!}}\right)+\cdots \\&={\frac {1}{(m-1)!}}(1+m-1)+{\frac {1}{(m-3)!}}(1+m-3)+\cdots .\end{aligned}}$

Мы будем вычислять только целые значения выражений вскобки, это значения

$m,m-2,m-4,\dots .\,$

Таким образом, на первом этапе сумма $S$ увлекается

$S=S(1)=\sum _{j=0}^{m_{1}-1}{\frac {1}{(m-1-2j)!}}\alpha _{m_{1}-j}(1),$

$m_{1}={\frac {m}{2}},m=2^{k},k\geq 1.$

На первом шаге ${\frac {m}{2}}$ целые числа вида

$\alpha _{m_{1}-j}(1)=m-2j,\quad j=0,1,\dots ,m_{1}-1,$

рассчитываются. После этого действуем аналогично: совмещаем покаждый шаг слагаемые суммы $S$ последовательно в парах, мывыносим за скобки «очевидный» общий делитель и вычисляемтолько целые значения выражений в скобках. Предполагатьчто первый $i$ этапы этого процесса завершены.

Шаг $i+1$ ( $i+1\leq k$).

$S=S(i+1)=\sum _{j=0}^{m_{i+1}-1}{\frac {1}{(m-1-2^{i+1}j)!}}\alpha _{m_{i+1}-j}(i+1),$

$m_{i+1}={\frac {m_{i}}{2}}={\frac {m}{2^{i+1}}},$

мы вычисляем только ${\frac {m}{2^{i+1}}}$ целые числа вида

$\alpha _{m_{i+1}-j}(i+1)=\alpha _{m_{i}-2j}(i)+\alpha _{m_{i}-(2j+1)}(i){\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}},$

$j=0,1,\dots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geq i+1.$

Здесь

${\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}}$

является продуктом $2^{i}$ целые числа.

И т. д.

Шаг $k$, последний. Мы вычисляем одно целое значение $\alpha _{1}(k),$ мы вычисляем, используя описанный быстрый алгоритмвыше значения $(m-1)!,$ и сделать одно деление целого числа $\alpha _{1}(k)$ по целому числу $(m-1)!,$ с точностью до $n$цифры. Полученный результат представляет собой сумму $S,$ или константа $e$ вверхк $n$ цифры. Сложность всех вычислений

$O\left(M(m)\log ^{2}m\right)=O\left(M(n)\log n\right).\,$

См. также

• Быстрые алгоритмы
• метод общего собрания акционеров
• Вычислительная сложность

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

• http://www.ccas.ru/personal/karatsuba/divcen.htm
• http://www.ccas.ru/personal/karatsuba/algen.htm