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

Значимость предмета статьи поставлена под сомнение. Пожалуйста, покажите в статье значимость её предмета, добавив в неё доказательства значимости по частным критериям значимости или, в случае если частные критерии значимости для предмета статьи отсутствуют, по общему критерию значимости. Подробности могут быть на странице обсуждения. Дата постановки шаблона: 30 июня 2012

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

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

Основная статья: Битовая операция (теория алгоритмов)

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

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

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

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

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

$s_f(n)=s_{f,\;x_0}(n).$

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

$M(n).$

Наилучшая известная в настоящее время оценка сложности умножения есть $M(n)=O(n\log n\log\log n).$

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

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

$s_f(n)=O(M(n)\log^cn),$

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

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

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

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

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

См. также

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

Примечания

1. ↑ А. Н. Колмогоров, {{{заглавие}}} // Теория информации и теория алгоритмов.. — Москва: Наука, 1987.
2. ↑ Карацуба А. А. Сложность вычислений // Труды Математического института им. Стеклова. — 1995. — Т. 211.
3. ↑ Strassen V. Gaussian elimination is not optimal // Journal of Numerical Mathematics. — 1969. — № 13.
4. ↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. — 1971. — № 7. — P. 281—292.
5. ↑ Schönhage A., Grotefeld A. F. W., Vetter E. Fast algorithms: A multitape Turing machine implementation. — Zürich: B. I. Wissenschaftsverlag, 1994. — ISBN 3411168919.
6. ↑ Карацуба Е. А. Быстрое вычисление трансцендентных функций // Проблемы передачи информации. — 1991. — Т. 27. — № 4.

Ссылки

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