Preview

Чебышевский сборник

Расширенный поиск

Умножение

https://doi.org/10.22405/2226-8383-2020-21-1-101-134

Полный текст:

Аннотация

В работе предпринимается обзор современного состояния теории быстрых алгоритмов умножения чисел и многочленов. Рассматривается процесс эволюции методов умножения от первых блочных алгоритмов Карацубы и Тоома 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

Просмотров: 186


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)