שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2019 - התמרת פורייה מהירה

נתונים מקדמיו השלמים $a_0,\dots,a_{n-1}$ של פולינום $p(x)$ מדרגה $n-1$. הניתוח הסטנדרטי של FFT מחשב את ערכי הפולינום ב-$n$ שורשי היחידה המרוכבים כאשר $n=2^k$. נסחו מחדש את אלגוריתם ה-FFT (רדיקס-3) עבור $n=3^k$.

רמז: במקום פיצול זוגי/אי-זוגי, פצלו את המקדמים לשלושה תת-פולינומים לפי שארית האינדקס מודולו 3, הריצו רקורסיבית ב-$\omega^3$, ושלבו לפי $p(\omega^k)=f_0(\omega^{3k})+\omega^k f_1(\omega^{3k})+\omega^{2k} f_2(\omega^{3k})$.

פתרון: במקום לפצל את הפולינום לשני גורמים (זוגי/אי-זוגי), נפצל אותו ל**שלושה** גורמים לפי שארית האינדקס מודולו 3, נריץ FFT (מסדר $n/3$, עם $\omega^3$) על כל אחד, ונשלב. ``` FFT((a_0,...,a_{n-1}), ω): if n == 1: return (a_0) f0 = FFT((a_0, a_3, a_6, ..., a_{n-3}), ω^3) # אינדקסים ≡ 0 (mod 3) f1 = FFT((a_1, a_4, a_7, ..., a_{n-2}), ω^3) # אינדקסים ≡ 1 (mod 3) f2 = FFT((a_2, a_5, a_8, ..., a_{n-1}), ω^3) # אינדקסים ≡ 2 (mod 3) for k = 0 .. n-1: f(ω^k) = f0(ω^{3k}) + ω^k · f1(ω^{3k}) + ω^{2k} · f2(ω^{3k}) return (f(ω^0), f(ω^1), ..., f(ω^{n-1})) ``` **הסבר.** $p(x)=p_0(x^3)+x\,p_1(x^3)+x^2\,p_2(x^3)$, כאשר $p_r$ מורכב מהמקדמים בעלי אינדקס $\equiv r\pmod 3$. הרצה רקורסיבית על $p_0,p_1,p_2$ ב-$\omega^3$ נותנת את ערכיהם בשורשי היחידה מסדר $n/3$, ומהם מרכיבים את $p(\omega^k)$ לפי הנוסחה. **זמן ריצה.** $T(n)=3\,T(n/3)+O(n)$, ולפי משפט האב $T(n)=\Theta(n\log_3 n)=\Theta(n\log n)$. $\blacksquare$