Открыть главное меню

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

Содержание

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

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

Определение. Запись знаков  , сложение, вычитание и умножение двух битов назовём одной элементарной или битовой операцией.

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

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

 .

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

 .

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

 .

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

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

 

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

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

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

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

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

См. такжеПравить

ПримечанияПравить

  1. David Harvey, Joris Van Der Hoeven Integer multiplication in time O(n log n)
  2. Peyman Afshani, Casper Benjamin Freksen, Lior Kamma, Kasper Green Larsen Lower Bounds for Multiplication via Network Coding
  3. А. Н. Колмогоров,. {{{заглавие}}} // Теория информации и теория алгоритмов.. — Москва: Наука, 1987.
  4. Карацуба А. А. Сложность вычислений // Труды Математического института им. Стеклова. — 1995. — Т. 211.
  5. Strassen V. Gaussian Elimination is not Optimal // Numer. MathSpringer Science+Business Media, 1969. — Vol. 13, Iss. 4. — P. 354–356. — ISSN 0029-599X; 0945-3245doi:10.1007/BF02165411
  6. Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. — 1971. — № 7. — P. 281—292.
  7. Schönhage A., Grotefeld A. F. W., Vetter E. Fast algorithms: A multitape Turing machine implementation. — Zürich: B. I. Wissenschaftsverlag, 1994. — ISBN 3411168919.
  8. Карацуба Е. А. Быстрое вычисление трансцендентных функций // Проблемы передачи информации. — 1991. — Т. 27, № 4.

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