Кіріспе
Тез Фурье түрлендіру алгоритмі, J. W. Cooley және John Tukey есімдерімен аталатын, ең көп қолданылатын тез Фурье түрлендіру (FFT) алгоритмі болып табылады. Ол кез келген құрама өлшемдегі дискретті Фурье түрлендірмесін (DFT) N1 кіші DFT-лерге N2 өлшемдері бойынша рекурсивті түрде бөліп, өте құрама N (тегіс сандар) үшін есептеу уақытын O(N log N) дейін азайтады. Алгоритмнің маңыздылығына байланысты, нақты нұсқалары мен іске асыру әдістері өздерінің жеке аттарымен белгілі болды, төменде сипатталғандай. Кули-Туки алгоритмі DFT-ді кіші DFT-лерге бөлгендіктен, оны DFT үшін кез келген басқа алгоритммен еркін үйлестіруге болады. Мысалы, Радер немесе Блюштейн алгоритмдері Кули-Туки арқылы жіктелмейтін үлкен жай сан факторларын өңдеу үшін қолданылуы мүмкін, немесе жай сан факторлары алгоритмі салыстырмалы жай факторларды бөлуде тиімділікке қол жеткізу үшін пайдаланылуы мүмкін. Алгоритмді және оның рекурсивті қолданылуын Карл Фридрих Гаусс ойлап тапқан. Кули мен Туки оны 160 жылдан кейін тәуелсіз түрде қайта ашып, танымал етті.
The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size in terms of N1 smaller DFTs of sizes N2, recursively, to reduce the computation time to O(N log N) for highly composite N (smooth numbers). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below. Because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT. For example, Rader's or Bluestein's algorithm can be used to handle large prime factors that cannot be decomposed by Cooley–Tukey, or the prime factor algorithm can be exploited for greater efficiency in separating out relatively prime factors. The algorithm, along with its recursive application, was invented by Carl Friedrich Gauss. Cooley and Tukey independently rediscovered and popularized it 160 years later.
Тарих
Бұл алгоритмді, оның ішінде рекурсивті қолдануды 1805 жылы Карл Фридрих Гаусс ойлап тапты, ол оны Паллас және Юно астероидтарының траекторияларын интерполяциялау үшін пайдаланды, бірақ оның жұмысы кеңінен танылмады (тек өлімнен кейін және нео-латын тілінде жарияланды). Гаусс асимптотикалық есептеу уақытын талдаған жоқ. XIX ғасыр мен XX ғасырдың басында әртүрлі шектеулі формалары бірнеше рет қайта ашылды. Тюки бұл идеяны президент Кеннедидің ғылыми кеңесшілер комитетінің отырысында, елден тыс орналасқан сейсмометрлерді пайдалану арқылы Кеңес Одағындағы ядролық қару сынақтарын анықтау жолдарын талқылау кезінде ойлап тапқан. Бұл сенсорлар сейсмологиялық уақыт қатарларын жасады. Бірақ, осы деректерді талдау үшін, сенсорлардың саны мен уақыттың ұзақтығына байланысты DFT-ді есептеуге арналған жылдам алгоритмдер қажет болды. Бұл міндет ядролық сынақтарға тыйым салу туралы ұсынысты бекіту үшін маңызды болды, себебі кез келген бұзушылықтарды кеңестік объектілерге барудың қажеті болмайтын еді. Осы отырысқа қатысқан IBM қызметкері Ричард Гарвин бұл әдістің әлеуетін байқап, Тюкині Кулимен байланыстырды. Бірақ Гарвин Кули бастапқы мақсатты білмейтіндігіне көз жеткізді. Оның орнына, Кулиге гелийдің 3D кристалдарындағы спин бағыттарының периодтығын анықтау үшін бұл қажет екенін айтты. Кейін Кули мен Тюки бірлескен мақалаларын жариялады, және аналогты-цифрлық түрлендіргіштердің бір мезгілде 300 кГц-ге дейін үлгі алуға қабілетті болуының арқасында кеңінен қолданысқа енді. Гаусс сол алгоритмді сипаттағаны (бірақ оның асимптотикалық құнын талдамаса да) Кули мен Тюкидің 1965 жылғы мақаласынан кейін бірнеше жыл өткен соң ғана анықталды.