Метод БВЕ

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

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

ТеоремаПравить

С помощью БВЕ можно доказать следующую теорему

Теорема.

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

$s_f(n)=O(M(n){\log }^2<!--\; \; -->n).$$s_{f}(n)=O(M(n)\log ^{2}n).$ 

Здесь $s_f(n)$$s_f(n)$  есть сложность вычисления (битовая) функции $f(x)$$f(x)$  с точностью до $n$$n$  знаков, $M(n)$$M(n)$  — сложность умножения двух $n$$n$ -значных чисел.

Алгоритмы, основанные на БВЕ, включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант $e$$e$ , $\mathrm{\pi <!--\; \pi \; -->}$$\pi$ , постоянной Эйлера $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$ , постоянных Апери и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций, сферических функций, цилиндрических функций и так далее для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента, дзета-функции Гурвица для целого аргумента и алгебраических значений параметра, а также таких специальных интегралов, как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и так далее при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно $s_f(n)=O(M(n){\log }^2<!--\; \; -->n).$$s_{f}(n)=O(M(n)\log ^{2}n).$ 

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

БВЕ-вычисление классических константПравить

Для быстрого вычисления константы $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  можно воспользоваться формулой Эйлера $\frac{\mathrm{\pi <!--\; \pi \; -->}}{4}=\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{1}{2}+\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{1}{3},$${\frac {\pi }{4}}=\mathrm {arctg} {\frac {1}{2}}+\mathrm {arctg} {\frac {1}{3}},$  и применить БВЕ к суммированию рядов Тейлора для

$\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{1}{2}=\frac{1}{1\cdot <!--\; \cdot \; -->2}-<!--\; -\; -->\frac{1}{3\cdot <!--\; \cdot \; -->2^3}+\dots <!--\; \dots \; -->+\frac{(-<!--\; -\; -->1{)}^{r-<!--\; -\; -->1}}{(2r-<!--\; -\; -->1)2^{2r-<!--\; -\; -->1}}+R_1,$$\mathrm {arctg} {\frac {1}{2}}={\frac {1}{1\cdot 2}}-{\frac {1}{3\cdot 2^{3}}}+\ldots +{\frac {(-1)^{r-1}}{(2r-1)2^{2r-1}}}+R_{1},$ 

$\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{g}\frac{1}{3}=\frac{1}{1\cdot <!--\; \cdot \; -->3}-<!--\; -\; -->\frac{1}{3\cdot <!--\; \cdot \; -->3^3}+\dots <!--\; \dots \; -->+\frac{(-<!--\; -\; -->1{)}^{r-<!--\; -\; -->1}}{(2r-<!--\; -\; -->1)3^{2r-<!--\; -\; -->1}}+R_2,$$\mathrm {arctg} {\frac {1}{3}}={\frac {1}{1\cdot 3}}-{\frac {1}{3\cdot 3^{3}}}+\ldots +{\frac {(-1)^{r-1}}{(2r-1)3^{2r-1}}}+R_{2},$ 

с остаточными членами $R_1,R_2,$$R_{1},\ R_{2},$  для которых справедливы оценки

$|R_1|⩽<!--\; ⩽\; -->\frac{4}{5}\frac{1}{2r+1}\frac{1}{2^{2r+1}};$$|R_{1}|\leqslant {\frac {4}{5}}{\frac {1}{2r+1}}{\frac {1}{2^{2r+1}}};$ 

$|R_2|⩽<!--\; ⩽\; -->\frac{9}{10}\frac{1}{2r+1}\frac{1}{3^{2r+1}};$$|R_{2}|\leqslant {\frac {9}{10}}{\frac {1}{2r+1}}{\frac {1}{3^{2r+1}}};$ 

и при

$r=n,$$r=n,$ 

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

Чтобы вычислить $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  посредством БВЕ, можно использовать также другие приближения. Во всех случаях сложность

$s_{\mathrm{\pi <!--\; \pi \; -->}}=O(M(n){\log }^2<!--\; \; -->n).$$s_{\pi }=O(M(n)\log ^{2}n).$ 

Чтобы вычислить постоянную Эйлера $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$  с точностью до $n$$n$  знаков, нужно просуммировать с помощью БВЕ два ряда. А именно, при $m=6n,k=n,k⩾<!--\; ⩾\; -->1,$$m=6n,\ k=n,\ k\geqslant 1,$ 

$\mathrm{\gamma <!--\; \gamma \; -->}=-<!--\; -\; -->\log <!--\; \; -->n\underset{r=0}{\overset{12n}{\sum <!--\; \sum \; -->}}\frac{(-<!--\; -\; -->1{)}^r{n}^{r+1}}{(r+1)!}+\underset{r=0}{\overset{12n}{\sum <!--\; \sum \; -->}}\frac{(-<!--\; -\; -->1{)}^r{n}^{r+1}}{(r+1)!(r+1)}+O(2^{-<!--\; -\; -->n}).$$\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_{\mathrm{\gamma <!--\; \gamma \; -->}}=O(M(n){\log }^2<!--\; \; -->n).$$s_{\gamma }=O(M(n)\log ^{2}n).$ 

Для быстрого вычисления константы $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$  можно также применить метод БВЕ к другому приближению

БВЕ-вычисление некоторых степенных рядовПравить

С помощью БВЕ можно вычислить быстро следующие два вида рядов:

$f_1=f_1(z)=\underset{j=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{a(j)}{b(j)}{z}^j,$$f_{1}=f_{1}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}z^{j},$ 

$f_2=f_2(z)=\underset{j=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{a(j)}{b(j)}\frac{z^j}{j!},$$f_{2}=f_{2}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}{\frac {z^{j}}{j!}},$ 

при условии, что $a(j),b(j)$$a(j),\ b(j)$  — целые числа, $|a(j)|+|b(j)|\leqslant (Cj)^{K};\ |z|<1;\ K$  и $C$$C$  есть константы, и $z$$z$  есть алгебраическое число.

Сложность вычисления этих рядов

$s_{f_1}(n)=O\left(M(n){\log }^2<!--\; \; -->n\right),$$s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),$ 

$s_{f_2}(n)=O\left(M(n)\log <!--\; \; -->n\right).$$s_{f_{2}}(n)=O\left(M(n)\log n\right).$ 

Детали БВЕ на примере быстрого вычисления константы $e$$e$Править

Для вычисления константы $e$$e$  возьмём $m=2^k,k⩾<!--\; ⩾\; -->1$$m=2^{k},\quad k\geqslant 1$ , членов ряда Тейлора для $e,$$e,$ 

$e=1+\frac{1}{1!}+\frac{1}{2!}+\dots <!--\; \dots \; -->+\frac{1}{(m-<!--\; -\; -->1)!}+R_m.$$e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\ldots +{\frac {1}{(m-1)!}}+R_{m}.$ 

При этом выбираем $m$$m$  так, чтобы для остатка $R_m$$R_m$  выполнялось неравенство $R_m⩽<!--\; ⩽\; -->2^{-<!--\; -\; -->n-<!--\; -\; -->1}$$R_{m}\leqslant 2^{-n-1}$ . Это будет, например, когда $m⩾<!--\; ⩾\; -->\frac{4n}{\log <!--\; \; -->n}$$m\geqslant {\frac {4n}{\log n}}$ . Таким образом, возьмем $m=2^k$$m=2^{k}$  таким, что натуральное число $k$$k$  определяется неравенствами:

$2^k⩾<!--\; ⩾\; -->\frac{4n}{\log <!--\; \; -->n}>2^{k-<!--\; -\; -->1}.$$2^{k}\geqslant {\frac {4n}{\log n}}>2^{k-1}.$ 

Будем вычислять сумму $S=1+\frac{1}{1!}+\frac{1}{2!}+\dots <!--\; \dots \; -->+\frac{1}{(m-<!--\; -\; -->1)!}=\underset{j=0}{\overset{m-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\frac{1}{(m-<!--\; -\; -->1-<!--\; -\; -->j)!},$$S=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\ldots +{\frac {1}{(m-1)!}}=\sum _{j=0}^{m-1}{\frac {1}{(m-1-j)!}},$ 

за $k$$k$  шагов следующего процесса.

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

$S=\left(\frac{1}{(m-<!--\; -\; -->1)!}+\frac{1}{(m-<!--\; -\; -->2)!}\right)+\left(\frac{1}{(m-<!--\; -\; -->3)!}+\frac{1}{(m-<!--\; -\; -->4)!}\right)+\dots <!--\; \dots \; -->=$$S=\left({\frac {1}{(m-1)!}}+{\frac {1}{(m-2)!}}\right)+\left({\frac {1}{(m-3)!}}+{\frac {1}{(m-4)!}}\right)+\ldots =$ 

$=\frac{1}{(m-<!--\; -\; -->1)!}(1+m-<!--\; -\; -->1)+\frac{1}{(m-<!--\; -\; -->3)!}(1+m-<!--\; -\; -->3)+\dots <!--\; \dots \; -->$$={\frac {1}{(m-1)!}}(1+m-1)+{\frac {1}{(m-3)!}}(1+m-3)+\ldots$ 

Будем вычислять только целые значения выражений, стоящих в скобках, то есть значения $m,m-<!--\; -\; -->2,m-<!--\; -\; -->4,\dots <!--\; \dots \; -->$$m,\ m-2,\ m-4,\ \ldots$ 

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

$S=S(1)=\underset{j=0}{\overset{m_1-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\frac{1}{(m-<!--\; -\; -->1-<!--\; -\; -->2j)!}{\mathrm{\alpha <!--\; \alpha \; -->}}_{m_1-<!--\; -\; -->j}(1),$$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⩾<!--\; ⩾\; -->1.$$m_{1}={\frac {m}{2}},\ m=2^{k},\ k\geqslant 1.$ 

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

${\mathrm{\alpha <!--\; \alpha \; -->}}_{m_1-<!--\; -\; -->j}(1)=m-<!--\; -\; -->2j,j=0,1,\dots <!--\; \dots \; -->,m_1-<!--\; -\; -->1,$$\alpha _{m_{1}-j}(1)=m-2j,\quad j=0,\;1,\;\ldots ,\;m_{1}-1,$ 

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

Шаг $i+1$$i+1$  ($i+1⩽<!--\; ⩽\; -->k$$i+1\leqslant k$ ).

$S=S(i+1)=\underset{j=0}{\overset{m_{i+1}-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\frac{1}{(m-<!--\; -\; -->1-<!--\; -\; -->2^{i+1}j)!}{\mathrm{\alpha <!--\; \alpha \; -->}}_{m_{i+1}-<!--\; -\; -->j}(i+1),$$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}},$$m_{i+1}={\frac {m_{i}}{2}}={\frac {m}{2^{i+1}}},$ 

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

${\mathrm{\alpha <!--\; \alpha \; -->}}_{m_{i+1}-<!--\; -\; -->j}(i+1)={\mathrm{\alpha <!--\; \alpha \; -->}}_{m_i-<!--\; -\; -->2j}(i)+{\mathrm{\alpha <!--\; \alpha \; -->}}_{m_i-<!--\; -\; -->(2j+1)}(i)\frac{(m-<!--\; -\; -->1-<!--\; -\; -->2^{i+1}j)!}{(m-<!--\; -\; -->1-<!--\; -\; -->2^i-<!--\; -\; -->2^{i+1}j)!},$$\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 <!--\; \dots \; -->,m_{i+1}-<!--\; -\; -->1,m=2^k,k⩾<!--\; ⩾\; -->i+1.$$j=0,\;1,\;\ldots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geqslant i+1.$ 

Здесь $\frac{(m-<!--\; -\; -->1-<!--\; -\; -->2^{i+1}j)!}{(m-<!--\; -\; -->1-<!--\; -\; -->2^i-<!--\; -\; -->2^{i+1}j)!}$${\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}}$  есть произведение $2^i$$2^i$  целых чисел.

И так далее.

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

$O\left(M(m){\log }^2<!--\; \; -->m\right)=O\left(M(n)\log <!--\; \; -->n\right).$$O\left(M(m)\log ^{2}m\right)=O\left(M(n)\log n\right).$ 

СсылкиПравить

• http://www.ccas.ru/personal/karatsuba/alg.htm