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

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

Битовая операция

 → Битовая операция (теория алгоритмов)

Будем считать, что числа записаны в двоичной системе счисления, знаки которой $0$ и $1$ называются битами.

Определение. Запись знаков $0,\;1,\;+,\;-,\;(,)$, сложение, вычитание и умножение двух битов назовём одной элементарной или битовой операцией.

Сложность вычисления (битовая)

 → Сложность вычисления (битовая)

Для оценки качества быстрого метода или алгоритма используется функция битовая сложность вычисления которая обозначается через

$s_{f}(n)=s_{f,\;x_{0}}(n)$.

Функция сложности умножения имеет специальное обозначение

$M(n)$.

Оценка сложности наилучшего (в асимптотике) из известных в настоящее время алгоритмов умножения (и по всей видимости, асимптотически более быстрого метода не существует):

$O\left(n\cdot \log n\right)$.

Быстрый алгоритм вычисления функции

Назовём алгоритм вычисления функции $f=f(x)$ быстрым, если, предполагая наилучшую оценку для $M(n)$, для этого алгоритма битовая сложность вычисления имеет вид:

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

где $c$ есть константа.

История вопроса

Первые задачи по битовой сложности вычисления были поставлены А.Н. Колмогоровым, который при этом ссылался на работы Клода Шеннона и Норберта Винера, возбудившие его интерес к информатике.

Область быстрые алгоритмы появилась в 1960 году, когда был найден первый быстрый метод — метод умножения Карацубы. Впоследствии метод Карацубы был обобщён до парадигмы «Разделяй и властвуй», другими важными примерами которой являются метод двоичного разбиения^[en], двоичный поиск, метод бисекции и др.

После метода Карацубы было построено много других быстрых методов, включая алгоритм Штрассена для быстрого умножения матриц Шаблон:Source-ref (обобщение идеи Карацубы на матрицы), метод умножения Шёнхаге — Штрассена, метод БВЕ для вычисления простейших и высших трансцендентных функций. и т. д. Некоторые старые методы становятся быстрыми вычислительными методами, если использовать в них один из быстрых алгоритмов умножения, например, метод Ньютона для вычисления элементарных алгебраических функций и АГС метод Гаусса для вычисления простейших трансцендентных функций.

См. также

• Сложность вычисления (битовая)
• Быстрое умножение
• Алгоритм быстрого возведения в степень
• АГС метод Гаусса
• Метод БВЕ
• Длинная арифметика
• Быстрое преобразование Фурье

Ссылки

• Карацуба Е. А. Быстрые алгоритмы и метод БВЕ