Теоретический материал: алгоритм Карацубы и быстрое преобразование Фурье (А.Климовский)

Литература

  1. Г. И. Архипов. Лекции по математическому анализу: Учеб. для вузов / Г. И. Архипов, В. А. Садовничий, В. Н. Чубариков; Под ред. В. А. Садовничего – 3-е изд., перераб. и доп. - М.: Дрофа, 2003 – 640 с. – (Высшее образование: современный учебник). Глава 5, Лекция 27, Теорема 34 (стр. 152-153)

  2. Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. – М. : Издательский дом «Вильямс», 2005. – 1276 с. : ил. – Парал. тит. англ. Часть 7, Глава 30 (стр. 926 – 953)

  3. Daniel N. Rockmore, "The FFT — an algorithm the whole family can use", Comput. Sci. Eng. 2 (1), 60 (2000). Special issue on "top ten" algorithms of the century. (http://www.cs.dartmouth.edu/~Erockmore/cse-fft.pdf)

6