אלגוריתם ה-FFT של קולי-טוקי
ויקיפדיה האנציקלופדיה encyclopedia
אלגוריתם קולי-טוקי, על שמם של ג'יימס קולי (אנ') וג'ון טוקי, הוא אלגוריתם התמרת פורייה מהירה (FFT) הנפוץ ביותר. הוא מבטא מחדש, באופן רקורסיבי, את התמרת פורייה הבדידה (DFT) בגודל פריק שרירותי במונחים של N1 התמרות DFT קטנות יותר, כל אחת בגודל N2, וזאת על מנת להפחית את זמן החישוב ל-O(N log N) עבור N פריק מאוד.
מכיוון שאלגוריתם קולי-טוקי מפרק את ה-DFT להתמרות DFT קטנות יותר, ניתן לשלבו עם כל אלגוריתם DFT אחר. לדוגמה, ניתן להשתמש באלגוריתמים של Rader או Bluestein לטיפול בגורמים ראשוניים גדולים שלא ניתן לפרק על ידי קולי-טוקי, או שאפשר להשתמש באלגוריתם FFT של גורם ראשוני ליעילות רבה יותר בהפרדת גורמי מספרים זרים .
האלגוריתם, כולל יישומו הרקורסיבי, הומצא בידי קרל פרידריך גאוס. 160 שנה מאוחר יותר, קולי וטוקי פיתחו אותו מחדש והפכו אותו לפופולרי .