Khác biệt giữa các bản “Biến đổi Fourier nhanh”

|pages=297–301
}}</ref>. Đây là một [[thuật toán chia để trị]] dùng [[đệ quy]] để chia bài toán tính DFT có kích thước [[hợp số]] ''N=N<sub>1</sub>N<sub>2</sub>'', thành nhiều bài toán tính DFT nhỏ hơn có kích thước ''N<sub>1</sub>'' và ''N<sub>2</sub>'', cùng với O(''N'') phép nhân với [[căn của đơn vị]], thường được gọi là [[thừa số xoay]] (theo Gentleman và Sande, 1966)<ref>{{cite conference|author=W. M. Gentleman, G. Sande|year=1966|title=Fast Fourier Transforms: for fun and profit|booktitle=Proceedings of the November 7-10, 1966, fall joint computer conference (AFIPS '66 (Fall))|publisher=ACM, New York, NY, USA|pages=563-578|doi=10.1145/1464291.1464352|url=http://doi.acm.org/10.1145/1464291.1464352}}</ref>.
 
Phương pháp này (cùng với ý tưởng chung về một FFT) được phổ biến rộng rãi bởi bài báo của [[J. W. Cooley]] và [[J. W. Tukey]] năm 1965 nhưng sau đó người ta nhận ra rằng hai tác giả đó đã phát hiện lại một cách độc lập thuật toán mà [[Carl Friedrich Gauss]] đã tìm ra khoảng năm 1805 (và sau đó được phát hiện lại nhiều lần trong những trường hợp đặc biệt).
 
Dạng phổ biến nhất của thuật toán Cooley-Tukey là chia biến đổi thành hai nửa kích thước ''N'' / 2 ở mỗi bước (vì vậy chỉ dùng được cho kích thước là lũy thừa của 2) nhưng bất kì cách phân tích ra thừa số nào cũng đều có thể dùng được (điều này cả Gauss và Cooley/Tukey đều nhận ra). Đây là dạng '''cơ số 2''' và dạng '''nhiều cơ số'''. Mặc dù ý tưởng cơ bản là đệ quy, khi lập trình, người ta thường sắp xếp lại thuật toán để tránh đệ quy. Ngoài ra, do thuật toán Cooley-Tukey chia một DFT thành các DFT nhỏ hơn, có thể phối hợp nó với các thuật toán khác cho DFT, chẳng hạn như những thuật toán mô tả dưới đây.
 
==Các vấn đề tính toán==
494

lần sửa đổi