Метод БВЕ - Детали БВЕ на примере быстрого вычисления константы e

Интернет магазин китайских планшетных компьютеров

Компьютеры - Метод БВЕ - Детали БВЕ на примере быстрого вычисления константы e

23 января 2011

Оглавление:
1. Метод БВЕ
2. БВЕ-вычисление классических констант
3. Детали БВЕ на примере быстрого вычисления константы e

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

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

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

Будем вычислять сумму

$S = 1 + \frac{1}{1!} + \frac{1}{2!} + \dots + \frac{1}{!} = \sum_{j=0}^{m-1}\frac{1}{!} ,$

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

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

$S = \left!} + \frac{1}{!}\right) + \left!} + \frac{1}{!}\right) + \dots$

$= \frac{1}{!} + \frac{1}{!} + \dots .$

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

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

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

$S = S = \sum_{j=0}^{m_1-1}\frac{1}{!}\alpha_{m_1-j} ,$

$m_1 = \frac m2 , m = 2^k , k \geq 1 .$

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

$\alpha_{m_1-j} = m-2j , \quad j = 0 , 1 , \dots , m_1 - 1 ,$

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

Шаг i + 1.

$S = S = \sum_{j=0}^{m_{i+1}-1}\frac{1}{!} \alpha_{m_{i+1}-j} ,$

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

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

$\alpha_{m_{i+1}-j} = \alpha_{m_i-2j} + \alpha_{m_i-}\frac{!}{!} ,$

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

Здесь $\frac{!}{!}$ есть произведение 2 целых чисел.

И т.д.

Последний, k -й шаг. Вычисляем одно целое значение α₁, вычисляем, пользуясь вышеописанным быстрым алгоритмом, значение !, и производим одно деление целого числа α₁ на число ! с точностью до n знаков. Получившийся результат и есть сумма S, или константа e с точностью до 2 . Сложность всех вычислений есть

$O\left\log^2 m\right) = O\left\log n\right) .$

<<< Быстрые алгоритмы

Метод умножения Шёнхаге Штрассена >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие