Research Article
An Empirical Comparison of Implementation Efficiency of Iterative and Recursive Algorithms of Fast Fourier Transform
@INPROCEEDINGS{10.1007/978-3-030-66785-6_9, author={Lin Lin and Zeng Xu and He Huan and Zhao Jian and Liang Li-Xin}, title={An Empirical Comparison of Implementation Efficiency of Iterative and Recursive Algorithms of Fast Fourier Transform}, proceedings={Machine Learning and Intelligent Communications. 5th International Conference, MLICOM 2020, Shenzhen, China, September 26-27, 2020, Proceedings}, proceedings_a={MLICOM}, year={2021}, month={1}, keywords={Fast Fourier Transform Recursive algorithm Iterative algorithm Runtime efficiency}, doi={10.1007/978-3-030-66785-6_9} }- Lin Lin
Zeng Xu
He Huan
Zhao Jian
Liang Li-Xin
Year: 2021
An Empirical Comparison of Implementation Efficiency of Iterative and Recursive Algorithms of Fast Fourier Transform
MLICOM
Springer
DOI: 10.1007/978-3-030-66785-6_9
Abstract
Fourier Transform is the basis of modern signal processing technology, and Fast Fourier Transform reduces the time complexity of Fourier Transform. Iterative algorithm and recursive algorithm are two basic methods to implement Fast Fourier Transform on the computer. This paper uses Java, C#, C++, and Python to implement iterative algorithm and recursive algorithms of Fast Fourier Transform, and tests the runtime of these two algorithms on Windows, Mac, and Linux platforms. The experimental results show that program written in Python has the longest runtime no matter iterative or recursive algorithm, and iterative algorithm written in C++ runs most efficiently; iterative program written in C++, C# and Python is more efficient than recursive algorithm, and Java’s recursive algorithm is more efficient than iterative algorithm.
