Быстрое преобразование Фурье

Question

Мне нужно умножить два полинома, каждый из которых имеет малые интегральные коэффициенты.Мне нужна быстрая процедура FFT в C / C ++, которая может их свести.Я видел несколько библиотек, но они кажутся слишком большими по нескольким файлам.Важно то, что мне нужен код, который не слишком длинный и может быть очень легко использован и скомпилирован в один файл .c/.cpp.

1. БПФ следует оптимизировать для реальных входных данных, по крайней мере, если не маленькие целые числа.
2. Реализация Radix 4, если она доступна, тоже подойдет.
3. Компиляция не требует специальных флагов компиляции, поскольку компиляция программы должна выполняться во внешней среде, которой я не могу управлять.

Тот, который очень хорошо соответствует моим потребностям:1012 * здесь .Но мне нужно что-то в два раза быстрее.

Answer 1

Для простой и удобной реализации FFT попробуйте KissFFT .Если вам нужна абсолютная максимальная производительность, и вы не возражаете против небольшой сложности, тогда она должна быть FFTW .

Answer 2

Я адаптировал функцию smbFft из этого примера на DspDimension к моим потребностям в прошлом.

Answer 3

Я собрал некоторые из моих лучших результатов поиска, которые соответствуют или в основном соответствуют данному вопросу (C / C ++ FFT), и я обычно организовал их от простого к сложному:

• https://www.sanfoundry.com/cpp-program-compute-dft-coefficients-directly/
• https://www.sanfoundry.com/cpp-program-compute-discrete-fourier-transform-using-fast-fourier-transform-approach/
• https://www.safaribooksonline.com/library/view/c-cookbook/0596007612/ch11s18.html
• https://tfetimes.com/c-fast-fourier-transform/
• http://fftwpp.sourceforge.net/
• http://www.fftw.org/
• https://sourceforge.net/projects/kissfft/
• http://www.drdobbs.com/cpp/a-simple-and-efficient-fft-implementatio/199500857
• https://www.programming -techniques.com / 2013/05 / расчет-дискретного-fourier.html
• https://rosettacode.org/wiki/Fast_Fourier_transform#C.2B.2B
• https://github.com/scipr-lab/libfqfft
• http://librow.com/articles/article-10
• http://www.kurims.kyoto -u.ac.jp / ~ ooura / fft.html

Не стесняйтесь добавлять или обновлять список.