Метод БВЕ

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

Теорема.

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

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

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

Алгоритмы, основанные на БВЕ, включают алгоритмы быстрого вычисления любой элементарной трансцендентной функции для любого аргумента, классических констант ${\displaystyle e}$ , ${\displaystyle \pi }$ , постоянной Эйлера ${\displaystyle \gamma }$ , постоянных Апери^[3] и Каталана, таких высших трансцендентных функций, как гамма-функции Эйлера и её производных, гипергеометрических функций^[4], сферических функций, цилиндрических функций^[5] и так далее для алгебраических значений аргумента и параметров, дзета-функции Римана для целых значений аргумента^[6][7], дзета-функции Гурвица для целого аргумента и алгебраических значений параметра^[8], а также таких специальных интегралов^[9], как интеграл вероятности, интегралы Френеля, интегральная экспоненциальная функция, интегральные синус и косинус и так далее при алгебраических значениях аргумента с оценкой сложности вычисления, близкой к оптимальной, а именно ${\displaystyle s_{f}(n)=O(M(n)\log ^{2}n).}$ 

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

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

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

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

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

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

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

и при

${\displaystyle r=n,}$ 

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

Чтобы вычислить ${\displaystyle \pi }$  посредством БВЕ, можно использовать также другие приближения^[12]. Во всех случаях сложность

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

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

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

При этом

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

Для быстрого вычисления константы ${\displaystyle \gamma }$  можно также применить метод БВЕ к другому приближению^[13]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle ={\frac {1}{(m-1)!}}(1+m-1)+{\frac {1}{(m-3)!}}(1+m-3)+\ldots }$ 

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

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

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

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

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

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

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

Шаг ${\displaystyle i+1}$  (${\displaystyle i+1\leqslant k}$ ).

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

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

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

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

${\displaystyle j=0,\;1,\;\ldots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geqslant i+1.}$ 

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

И так далее.

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

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

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