Умножениестатья

Статья опубликована в журнале из списка RSCI Web of Science

Информация о цитировании статьи получена из Scopus
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 16 сентября 2020 г.

Работа с статьей

Прикрепленные файлы


Имя Описание Имя файла Размер Добавлен
1. Полный текст chebsbornik2020.pdf 766,2 КБ 11 апреля 2020 [isserg]

[1] Гашков С. Б., Сергеев И. С. Умножение // Чебышевский сборник. — 2020. — Т. 21, № 1. — С. 101–134. В работе предпринимается обзор современного состояния теории быстрых алгоритмов умножения чисел и многочленов. Рассматривается процесс эволюции методов умножения от первых блочных алгоритмов Карацубы и Тоома 1960-х гг. к методам 1970-х гг., опирающимся на дискретное преобразование Фурье (ДПФ), и далее к новейшим методам, разработанным в 2007–2019 гг. Современные методы умножения сочетают использование специальных алгебраических структур, переход к приближенным вычислениям, особые формы преобразований Фурье: многомерное ДПФ, аддитивный аналог ДПФ. Эти и другие существенные для быстрых методов умножения концепции подробно рассматриваются в настоящем обзоре. Отдельно предусмотрено введение в теорию ДПФ с извлечением необходимых для изложения материала фактов. В заключительной части обзора приводятся краткие сведения о результатах в области параллельных алгоритмов умножения, аккуратных оценок сложности базовых методов умножения, алгоритмов умножения в реальном времени, мультипликативной сложности умножения многочленов над конечными полями. Отмечены модели вычислений, в которых умножение имеет линейную или квадратичную сложность. [ DOI ]

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