شصت سال پیش در چنین ماهی، الگوریتم تبدیل فوریه سریع (FFT) توسط کولی و توکی (۱۹۶۵) معرفی شد؛ یکی از مهمترین الگوریتمهای پردازش سیگنال و تحلیل داده در تاریخ.
جالب است بدانید در سال ۱۸۰۵، گاوس هنگام مطالعه مدار سیارکهای پالاس و جونو، روشی برای بازسازی مسیر آنها از نمونههای گسسته ارائه کرد. این روش از نظر ریاضی بسیار به FFT مدرن شباهت داشت، اما گاوس آن را منتشر نکرد و پیچیدگی محاسباتیاش را نیز تحلیل نکرد. این کشف حتی پیش از کار مشهور فوریه در زمینه انتشار گرما در سال ۱۸۲۲ انجام شده بود، اما بدون چارچوببندی و تعمیمی که کولی و توکی ۱۶۰ سال بعد ارائه کردند.
در سال ۱۹۶۵، کولی و توکی الگوریتمی را منتشر کردند که هزینه محاسبه تبدیل فوریه گسسته را از مرتبه 𝑂(𝑛²) به 𝑂(𝑛 log𝑛) کاهش داد. این جهش بزرگ، پردازش سیگنال در زمان واقعی و فشردهسازی رسانههای دیجیتال را ممکن ساخت.
از تلسکوپهای رادیویی تا تصاویر JPEG، از کدکهای صوتی تا مکانیک کوانتومی — الگوریتم FFT همه جا حضور دارد. یکی از مهمترین الگوریتمهای قرن بیستم؛ ریشهگرفته از نبوغ گاوس و شکوفا شده در عصر کامپیوتر.
#fft
جالب است بدانید در سال ۱۸۰۵، گاوس هنگام مطالعه مدار سیارکهای پالاس و جونو، روشی برای بازسازی مسیر آنها از نمونههای گسسته ارائه کرد. این روش از نظر ریاضی بسیار به FFT مدرن شباهت داشت، اما گاوس آن را منتشر نکرد و پیچیدگی محاسباتیاش را نیز تحلیل نکرد. این کشف حتی پیش از کار مشهور فوریه در زمینه انتشار گرما در سال ۱۸۲۲ انجام شده بود، اما بدون چارچوببندی و تعمیمی که کولی و توکی ۱۶۰ سال بعد ارائه کردند.
در سال ۱۹۶۵، کولی و توکی الگوریتمی را منتشر کردند که هزینه محاسبه تبدیل فوریه گسسته را از مرتبه 𝑂(𝑛²) به 𝑂(𝑛 log𝑛) کاهش داد. این جهش بزرگ، پردازش سیگنال در زمان واقعی و فشردهسازی رسانههای دیجیتال را ممکن ساخت.
از تلسکوپهای رادیویی تا تصاویر JPEG، از کدکهای صوتی تا مکانیک کوانتومی — الگوریتم FFT همه جا حضور دارد. یکی از مهمترین الگوریتمهای قرن بیستم؛ ریشهگرفته از نبوغ گاوس و شکوفا شده در عصر کامپیوتر.
#fft
👏1