- Быстрые алгоритмы
-
Значимость предмета статьи поставлена под сомнение. Пожалуйста, покажите в статье значимость её предмета, добавив в неё доказательства значимости по частным критериям значимости или, в случае если частные критерии значимости для предмета статьи отсутствуют, по общему критерию значимости. Подробности могут быть на странице обсуждения.- Дата постановки шаблона: 30 июня 2012
Быстрые алгоритмы — это область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью с использованием как можно меньшего числа битовых операций.
Содержание
Битовая операция
Будем считать, что числа записаны в двоичной системе счисления, знаки которой и называются битами.
Определение. Запись знаков , сложение, вычитание и умножение двух битов назовём одной элементарной или битовой операцией.
Сложность вычисления (битовая)
Для оценки качества быстрого метода или алгоритма используется функция битовая сложность вычисления которая обозначается через
Функция сложности умножения имеет специальное обозначение
Наилучшая известная в настоящее время оценка сложности умножения есть
Быстрый алгоритм вычисления функции
Назовём алгоритм вычисления функции быстрым, если, предполагая наилучшую оценку для , для этого алгоритма битовая сложность вычисления имеет вид:
где есть константа.
История вопроса
Первые задачи по битовой сложности вычисления были поставлены А.Н. Колмогоровым[1], который при этом ссылался на работы Клода Шеннона и Норберта Винера, возбудившие его интерес к информатике.
Область быстрые алгоритмы появилась в 1960 году[2], когда был найден первый быстрый метод — метод умножения Карацубы. Впоследствии метод Карацубы был обобщён до парадигмы «Разделяй и властвуй», другими важными примерами которой являются метод двоичного разбиения (англ. binary splitting), двоичный поиск, метод бисекции и др.
После метода Карацубы было построено много других быстрых методов, включая алгоритм Штрассена для быстрого умножения матриц[3] (обобщение идеи Карацубы на матрицы), метод умножения Шёнхаге — Штрассена[4][5], метод БВЕ[6] для вычисления простейших и высших трансцендентных функций. и т. д. Некоторые старые методы становятся быстрыми вычислительными методами, если использовать в них один из быстрых алгоритмов умножения, например, метод Ньютона для вычисления элементарных алгебраических функций и АГС метод Гаусса для вычисления простейших трансцендентных функций.
См. также
- Сложность вычисления (битовая)
- Быстрое умножение
- Алгоритм быстрого возведения в степень
- АГС метод Гаусса
- Метод БВЕ
Примечания
- ↑ А. Н. Колмогоров, {{{заглавие}}} // Теория информации и теория алгоритмов.. — Москва: Наука, 1987.
- ↑ Карацуба А. А. Сложность вычислений // Труды Математического института им. Стеклова. — 1995. — Т. 211.
- ↑ Strassen V. Gaussian elimination is not optimal // Journal of Numerical Mathematics. — 1969. — № 13.
- ↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. — 1971. — № 7. — P. 281—292.
- ↑ Schönhage A., Grotefeld A. F. W., Vetter E. Fast algorithms: A multitape Turing machine implementation. — Zürich: B. I. Wissenschaftsverlag, 1994. — ISBN 3411168919.
- ↑ Карацуба Е. А. Быстрое вычисление трансцендентных функций // Проблемы передачи информации. — 1991. — Т. 27. — № 4.
Ссылки
- Карацуба Е. А. Быстрые алгоритмы и метод БВЕ
Категории:- Вычислительная математика
- Длинная арифметика
Wikimedia Foundation. 2010.