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

**(א)** מהו הפלט של $\text{DFT}_n$ מסדר $n$ כאשר הקלט הוא $(1,1,\dots,1)$ (מקדמי $p(x)=1+x+\cdots+x^{n-1}$)? **(ב)** נתונים שני מספרים מרוכבים $x=a+bi$ ו-$y=c+di$ ($a,b,c,d$ ממשיים). חישוב ישיר של $x\cdot y=(ac-bd)+(ad+bc)i$ דורש 4 כפלים של ממשיים. הסבירו כיצד לחשב את $x\cdot y$ תוך ביצוע **3 כפלים בלבד** של ממשיים.

רמז: לחלק (ב): חשבו $(a+b)(c+d)$, $ac$ ו-$bd$. שלושת אלו מספיקים לשחזר את $ac-bd$ ואת $ad+bc$ באמצעות חיבורים וחיסורים בלבד.

פתרון: **(א)** $(n,0,\dots,0)$: עבור $x=1$ מתקבל $p(1)=n$, ולכל שורש יחידה $\omega\neq 1$ הסכום ההנדסי $\frac{\omega^n-1}{\omega-1}=0$. **(ב)** נבצע שלושה כפלים בלבד (טריק גאוס): 1. $P_1=(a+b)\cdot(c+d)$ 2. $P_2=a\cdot c$ 3. $P_3=b\cdot d$ אזי: - **החלק הממשי:** $ac-bd=P_2-P_3$. - **החלק המדומה:** $ad+bc=P_1-P_2-P_3$ (שכן $P_1=ac+ad+bc+bd$, ובחיסור $P_2$ ו-$P_3$ נותר $ad+bc$). חיבור וחיסור הם פעולות ליניאריות שאינן נספרות ככפלים, ולכן סה"כ **3 כפלים** של ממשיים. $\blacksquare$