Аннотация:В дипломной работе была поставлена задача найти алгоритм быстрого
преобразования Фурье, не использующий рекурсий и на этой основе
построить алгоритм умножения целых чисел, подобный алгоритму
Шёнхаге-Штрассена. Эта задача была успешно решена А. Трегубовой.
Требуемый алгоритм был построен.Такой же алгоритм с заменой первообразного корня может
использоваться и для быстрого вычисления обратного преобразования
Фурье. А.Трегубовой удалось получить короткое и элегантное
доказательство корректности построенного алгоритма. Структурно он
оказался проще, а верхняя оценка его сложности оказалась точнее, чем
в алгоритмах, указанных в литературе.