Умножение
Аннотация
В работе предпринимается обзор современного состояния теории быстрых алгоритмов умножения чисел и многочленов. Рассматривается процесс эволюции методов умножения от первых блочных алгоритмов Карацубы и Тоома 1960-х гг. к методам 1970-х гг., опирающимся на дискретное преобразование Фурье (ДПФ), и далее к новейшим методам, разработанным в 2007–2019 гг. Современные методы умножения сочетают использование специальных алгебраических структур, переход к приближенным вычислениям, особые формы преобразований Фурье: многомерное ДПФ, аддитивный аналог ДПФ. Эти и другие существенные для быстрых методов умножения концепции подробно рассматриваются в настоящем обзоре. Отдельно предусмотрено введение в теорию ДПФ с извлечением необходимых для изложения материала фактов. В заключительной части обзора приводятся краткие сведения о результатах в области параллельных алгоритмов умножения, аккуратных оценок сложности базовых методов умножения, алгоритмов умножения в реальном времени, мультипликативной сложности умножения многочленов над конечными полями. Отмечены модели вычислений, в которых умножение имеет линейную или квадратичную сложность.
Об авторах
Сергей Борисович ГашковРоссия
доктор физико-математических наук, профессор
Игорь Сергеевич Сергеев
Россия
кандидат физико-математических наук; начальник лаборатории
Для цитирования:
Гашков С.Б., Сергеев И.С. Умножение. Чебышевский сборник. 2020;21(1):101-134. https://doi.org/10.22405/2226-8383-2020-21-1-101-134
For citation:
Gashkov S.B., Sergeev I.S. Multiplication. Chebyshevskii Sbornik. 2020;21(1):101-134. (In Russ.) https://doi.org/10.22405/2226-8383-2020-21-1-101-134