אלגוריתם ה-FFT של קולי-טוקי
radix-2 FFT

FFT מסוג Radix-2 הוא הגרסה הפשוטה והנפוצה ביותר של אלגוריתם קולי-טוקי. יישומי קולי-טוקי בעלי אופטימיזציה גבוהה משתמשים לרוב בגרסאות אחרות של האלגוריתם, כפי שיתואר בהמשך. בשיטה זו גודל הקלט N הוא חזקה של שתיים. בכל שלב רקורסיבי, Radix-2 מחלק DFT בגודל N לשני DFT שזורים (interleaved) בגודל N/2.
התמרת פורייה הבדידה (DFT) מוגדרת בידי הנוסחה:
כאשר  k הוא מספר שלם הנע בין 0 ל  N-1 .
אנו מניחים כאן ש-N הוא חזקה של שתיים. Radix-2 מחשב תחילה את ה-DFT של ערכי הקלט בעלי האינדקס הזוגי  (x_{2m}=x_{0},x_{2},\ldots ,x_{N-2}) ושל ערכי הקלט בעלי האינדקס האי-זוגי  (x_{2m+1}=x_{1},x_{3},\ldots ,x_{N-1}), ולאחר מכן משלב את התוצאות הללו כדי לחשב את ה-DFT של הרצף כולו. את התהליך הזה ניתן לבצע באופן רקורסיבי ובכך להוריד את זמן הריצה הכולל ל-O(NlogN). היישום יכול לרוב, הגם שלא תמיד, לבחור את מספר נקודות הדגימה N באופן חופשי (למשל בעזרת שיטות כגון שינוי קצב הדגימה, גודל החלון, או zero-padding). לכן, לעיתים קרובות, הגודל של חזקה של שתיים אינו מגבלה חשובה.
אלגוריתם radix-2 מארגן מחדש את ה-DFT של הפונקציה  x_{n} בשני חלקים: סכום של האינדקסים הזוגיים  n={2m} וסכום של האי-זוגיים  n={2m+1} :
בסכום השני אפשר למצוא מכפיל משותף,  e^{-{\frac {2\pi i}{N}}k}, כמוצג במשוואה למטה. שני הסכומים במשוואה זו הם ה-DFT של המרכיבים הזוגיים  x_{2m} וה-DFT של המרכיבים האי-זוגיים  x_{2m+1} של הפונקציה  x_{n} .
נסמן את ה-DFT של המרכיבים הזוגיים  x_{2m} כ- E_{k}.
נסמן את ה-DFT של המרכיבים האי-זוגיים  x_{2m+1} כ- O_{k}.
ונקבל:
השוויון אמנם מתקיים עבור  k=0,\dots ,N-1, אך הנקודה המכרעת היא שאת הערכים  E_{k} ו  O_{k} יש לחשב רק עבור  k=0,\dots ,{\frac {N}{2}}-1. הודות למחזוריות של המעריך המרוכב,  X_{k+{\frac {N}{2}}} מחושב גם הוא מ  E_{k} ו  O_{k}, כלהלן :
אנחנו יכולים לכתוב מחדש את  X_{k} ו  X_{k+{\frac {N}{2}}} כלהלן:
תוצאה זו, ביטויו הרקורסיבי של DFT באורך N במונחי שני DFT באורך N/2, היא הליבה של התמרת פורייה המהירה radix-2. מקור המהירות של האלגוריתם הוא השימוש החוזר בתוצאות חישובי ביניים כדי לחשב כמה תוצאות DFT. התוצאות הסופיות מתקבלות על ידי שילוב +/− של  E_{k} ו  O_{k}\exp(-2\pi ik/N), שהוא פשוט DFT בגודל 2 (הנקרא לעיתים פרפר בהקשר הזה); כאשר מכלילים לבסיסים גדולים יותר כמתואר להלן, ה-DFT בגודל 2 מוחלף בידי DFT גדול יותר (שבעצמו ניתן לחישוב בעזרת FFT).
תהליך זה מדגים את הטכניקה הכללית של אלגוריתמי הפרד ומשול ; עם זאת, ביישומים רבים, נמנעת הרקורסיה המפורשת, ובמקום זאת עוברים על העץ החישובי באלגוריתם חיפוש לרוחב .
הביטוי-מחדש של DFT בגודל N כשני DFT בגודל N/2, כמפורט לעיל, נקרא לעיתים הלמה של Danielson–Lanczos, מאחר ששני המחברים כתבו על זהות זו ב-1942 (בהשפעת עבודתו של Runge משנת 1903). הם יישמו את הלמה שלהם כרקורסיה "לאחור", כך שגודל ה-DFT הוכפל שוב ושוב עד שספקטרום ההתמרה התכנס (הגם שנראה שהם לא הבינו שהם השיגו את הסיבוכיות האסימפטוטית O(NlogN)). עבודתם קדמה לזמינות נרחבת של מחשבים מכניים או אלקטרוניים והצריכה חישוב ידני (אפשר שעם עזרים מכניים כגון מכונת חיבור); הם דיווחו על זמן חישוב של 140 דקות עבור DFT בגודל 64 הפועל על קלט ממשי בדיוק של 3–5 ספרות. המאמר של קולי-טוקי משנת 1965 דיווח על זמן ריצה של 0.02 דקות עבור DFT מרוכב בגודל 2048 בריצה על IBM 7094 (כנראה תוך שימוש בנקודה צפה של 36 סיביות, כ-8 ספרות). בשינוי קנה המידה של הזמן לפי מספר הפעולות, דיווח זה מתאים להכפלת מהירות בערך פי 800,000. (כדי לתת פרספקטיבה לזמן החישוב הידני, 140 דקות עבור גודל 64 תואמות לממוצע של לא יותר מ-16 שניות לכל פעולת נקודה צפה, כש-20% מהן הן פעולות כפל.)
יישומי FFT בעלי ביצועים גבוהים עורכים שינויים רבים במימוש האלגוריתם בהשוואה למימוש הבסיסי הפשוט. לדוגמה, אפשר להשתמש במקרה בסיס גדול מ-N =1 להפחתת התקורה של הרקורסיה, גורם הסיבוב (twiddle factor)  \exp[-2\pi ik/N] ניתן לחישוב מראש, ולעיתים קרובות נעשה שימוש בבסיסים גדולים יותר משיקולי זיכרון מטמון ; אופטימיזציות אלו ואחרות יכולות ביחד לשפר את הביצועים בסדר גודל או יותר. (במימושים של האלגוריתם בספרי לימוד רבים, הרקורסיה של האלגוריתם חיפוש לעומק נשמטת לטובת הגישה הלא-רקורסיבית של אלגוריתם חיפוש לרוחב, אם כי נטען כי לרקורסיה של חיפוש לעומק ישנה מקומיות זיכרון טובה יותר. )