#algorithms #computer_science

פולינומים, FFT

פולינום

פולינום מעל שדה $F$ עם משתנה $x$ מויצג באופן הבא:

A (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i}

קבוצת הערכים ${a_{i} | i \in [0, n - 1]}$ נקראים מקדמי הפולינום.
דרגת הפולינום $d e g (A)$ תהיה $k$ אם המקדם הגדול ביותר ששונה מ 0 הוא $a_{k}$ .
כל מספר שגדול מ $d e g (A)$ ייקרא דרכה חסומה של הפולינום. למשל, פולינום מדרגה חסומה $n$ דרגתו יכולה להיות $k \in [0, n - 1]$ .

פעולות על פולינומים

הצבה - בהינתן $x_{0}$ כלשהו נרצה לחשב את $A (x_{0})$
חיבור- עבור שתי פולינום $A (x), B (x)$ כאשר שניהם מדרגה חסומה $n$ נרצה לחשב את $C (x) = A (x) + B (x)$ . יתקיים ש

C (x) = \sum_{i = 0}^{n - 1} (a_{i} + b_{i}) x^{i}

כפל-

C (x) = A (x) \cdot B (x)

זה פולינום מדרגה חסומה $2 n - 1$ .
נוכל לבטא את $C (x)$ באופן הבא:

C (x) = \sum_{i = 0}^{2 n - 2} c_{i} x_{i}

מה זה $c_{i}$ ? זה תהליך של קונבולוצייה

c_{i} = \sum_{k = 0}^{i} a_{k} \cdot b_{i - k}

(בעצם זה כפל של כל הגורמים שהחזקות שלהם יביאו לחזקה $i$ ) .

ייצוג פולינומים

ייצוג מקדמים

נגדיר $\overset{―}{a}$ כוקטור המקדמים $\overset{―}{a} = (a_{0}, a_{1}, a_{2}, a_{3}, \dots, a_{n - 1})$ .
על ייצוג זה מאוד נוח לבצע את פעולת ההצבה והחיבור בזמן ליניארי למספר המקדמים $O (n)$ . כמו כן נשים לב שאכן יש פונקצייה חח״ע ועל בין פולינום $A (x)$ למערך כזה.
ההוכחה לזה פשוטה :
נגיד $f : F^{n} \to F [n]$ על ידי :

f (\overset{―}{a}) = \sum_{i = 0}^{n - 1} a_{i} x^{i}

זאת פונקצייה על כי לכל פולינום שנבחר מדרגה חסומה $n$ נוכל לבנות וקטור מקדמים כזה (פשוט לשים $0$ אם יש חזקות שלא נמצאות).
זאת פונקצייה חח״ע כי פולינום מדרגה חסומה $n$ יהיו שווים רק אם המקדמים שלהם שווים משמע הקלטים של הפונקצייה (הוקטורים עצמם) שווים גם כן.

נשים לב שהכפלת שני פולינומים שמיוצגים על ידי המקדמים ייקח $O (n^{2})$ זמן. (כל מקדם יופל בכל המקדמים של הוקטור השני ולבסוף נסכום הכל).

ייצוג דגימת הנקודות

נוכל לייצג את הפולינום $A (x)$ מדרגה חסומה $n$ על ידי קבוצה של $n$ זוגות סדורים שכל זוג מייצג נקודה ואת ערך הפולינום בהצבת הנקודה.

{(x_{i}, y_{i}) | i \in [0, n - 1] \land y_{i} = A (x_{i})}

ברור מאליו ש $\forall_{k, j \in [0, n - 1]} : x_{k} \neq x_{j}$ .

נוכיח שגם כאן יש התאמה חח״ע ועל בין הייצוג לבין הפולינום. כדי להוכיח זאת נשים שבעת הצבת ערך $x_{i}$ כלשהו ב $A (x)$ המקדמים יישארו אותו דבר ולכן נוכל לייצג כל הצבה כזאת כשורה מטריציונית:

V = [\begin{matrix} (x_{0})^{0} & (x_{0})^{1} & \dots & (x_{0})^{n - 1} \\ (x_{1})^{0} & \dots & \dots & \dots \\ ⋮ & \dots \dots \dots & \dots \dots \dots \\ (x_{n - 1})^{0} & \dots & \dots & (x_{n - 1})^{n - 1} \end{matrix}]

כעת , נסמן את וקטור המקדמים כ $\overset{―}{a}$ ויתקיים :

V \cdot \overset{―}{a} = \overset{―}{y}

כאשר $\overset{―}{y}$ זה וקטור הפתרונות.

מטריצה זו ידועה בשם Vandermonde matrix.
כעת, אם נוכיח שהיא הפיכה נוכל להגיע לוקטור המקדמים על ידי

V^{- 1} \cdot \overset{―}{y}

וזאת אכן תהיה פונקצייה חח״ע ועל כיוון שאם המטריצה הפיכה משמעות הדבר שיש פתרון יחיד למערכת. (באופן דומה יכלנו להגדיר את הפונקצייה שלנו להיות ההעתקה ליניארית שמייצגת את המטריצה הזאת וזאת תהיה העתקה הפיכה).

נוכל להפוך את מטריצת ונדרמונה למטריצה הפיכה בשלבים הבאים :

\forall_{j > 1} : R_{j} - R_{1} \to R_{j}

כלומר להפחית את השורה הראשונה מכל האחרות , זה יגרום לעמודה הראשונה להתאפס חוץ מהאיבר הראשון. כעת :

\forall_{j > 1} : (x_{j} - x_{0}) \cdot R_{j} \to R_{j}

נשים לב שהסקלר שמוציאים נכנס בחישוב של הדטרמיננטה
וכעת נוכל לעשות זאת עבור כל שורה ועמודה , באופן כללי הפעולות שנעשה יהיו באופן הבא :

\forall_{i, j > i} : R_{j} - R_{i} \to R_{j}, (x_{j} - x_{i}) \cdot R_{j} \to R_{j}

סך הכל נקבל מטריצה משולשית תחתונה עם איברי $1$ כל הסקלרים שהוצאנו נקבל שהדטרמיננטה היא מכפלת איברי האלכסון שזה $1$ במקרה זה ועם כל הסקלרים זה יצא

Π_{1 \leq j \leq i \leq n} (x_{j} - x_{i})

ובגלל שאמרנו שכל האיברים בייצוג נקודות שונים אחד מהשני אז הדטרמיננטה שונה מ $0$ ולכן המטריצה הפיכה.

מעבר בין ייצוג מקדמים לנקודות

נבחר $n$ ערכים שונים ונציב אותם ב $A$ . כיוון שכל הצבה דורשת סכימה של $n$ מקדמים כפול הערך שהצבנו ואנחנו מבצעים זאת עבור כל ערך שבחרנו. זמן הריצה של פעולת המעבר תהיה $O (n^{2})$ .

מעבר בין ייצוג נקודות למקדמים

תהליך זה נקרא אינטרפולציה. ובזכות מטריצת ונדרמונדה שדיברנו עליה תהליך זה מוגדר היטב על הפולינום המיוצג בנקודות. הראנו שיש פונקצייה חח״ע ועל בין הנקודות לבין פולינום מדרגה חסומה $n$ כי המטריצה $V$ הפיכה. לכן המעבר יסתמך על המטריצה ההופכית והמשוואה

V^{- 1} \cdot \overset{―}{y} = \overset{―}{a}

כדי להגיע למקדמים .

האלגוריתם שבו השתמשנו למציאה ההופכית (גאוס ז׳ורדן) + בניית המשוואה ייקח והפתרון $O (n^{3})$ , לא בעיה להראות זאת אבל ניתן להכנס לקישור להסבר מעמיק.

ניתן לייעל את האלגוריתם בבאמצעות משפט לגראנז :

A (x) = \sum_{k = 0}^{n - 1} y_{k} \frac{Π_{j \neq k} (x - x_{j})}{Π_{j \neq k} (x_{k} - x_{j})}

אלגוריתם המעבר במקרה הזה ייקח $O (n^{2})$ .
הסיבה שזה $O (n^{2})$ היא כי גם למונה וגם למכנה מבצעים $O (n)$ פעולות כל פעם. ופעולת הסכימה גם היא חסומה ב $O (n)$ כלומר סך הכל חסום ב $O (n^{2})$ .

פעולות בתצוגת נקודות
חיבור : במצב שבוא שני פולינומים מיוצגים על ידי אותם ערכי ${x_{i} | i \in [0, n - 1]}$ אז החיבור לוקח $O (n)$

\begin{matrix} {(x_{i}, A (x_{i})) | i \in [0, n - 1]} \land {(x_{i}, B (x_{i})) | i \in [0, n - 1]} \\ ↓ \\ C = A + B \to {(x_{i}, C (x_{i})) | i \in [0, n - 1] \land C (x_{i}) = A (x_{i}) + B (x_{i})} \end{matrix}

זה נובע ישירות מהגדרת חיבור פולינומים.

כפל : באופן דומה אם קיבלנו מצב כמו הנ״ל אז

\forall_{i \in [0, n - 1]} : C (x_{i}) = A (x_{i}) B (x_{i})

זה גם נכון מהגדרת הכפל אבל ההבדל הוא שכאן נצטרך לבחור $2 n - 1$ נקודות זהות ל $A$ ו $B$ כדי לייצג את $C$ . הזמן עדיין ליניארי אבל התנאי נהיה ״כבד״ יותר.

הצבה : אם הנקודה שנרצה להציב היא אחת מהנקודות שיש לנו אז נצטרך רק לבצע חיפוש שבמקרה הטוב הוא $O (\log n)$ תלוי איך שמרנו את הנקודות. במידה ולא, עדיף לעשות אינטרפולצייה.

נשים לב: בשלושת הפעולות אם התנאים שציינתי לא מתקיימים נרצה לעשות אינטרפולציה כלומר מעבר למקדמים ב $O (n^{2})$ .

כרגע התהליכים שאנחנו מכירים הם כאלה:
Pasted image 20221029175405.png
כלומר על פניו נראה שכדאי לנו להשאר עם מקדמים וזהו. נראה שיש שיטות לייעל את התהליכים הרשומים למילה.

כפל מהיר של פולינמום בייצוג מקדמים.

נניח ש $n$ הוא חזקה של $2$ (נוכל להניח זאת כי במצב שהוא לא פשוט נשלים אותו להיות חזקה של $2$ עם מקדמי $0$ ) .
נגדיר

A (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i}, B (x) = \sum_{i = 0}^{n - 1} b_{i} x^{i}

כעת נחלק את הפולינומים באופן הבא

A (x) = Q (x) + x^{\frac{n}{2}} P (x), B (x) = R (x) + x^{\frac{n}{2}} S (x)

כאשר-

Q (x) = \sum_{i = 0}^{\frac{n}{2} - 1} a_{i} x^{i}, R (x) = \sum_{i = 0}^{\frac{n}{2} - 1} b_{i} x^{i}

P (x) = \sum_{i = \frac{n}{2}}^{n - 1} a_{i} x^{i - \frac{n}{2}}, S (x) = \sum_{i = \frac{n}{2}}^{n - 1} b_{i} x^{i - \frac{n}{2}}

נגדיר את מכפלתם להיות

\begin{matrix} A (x) B (x) = (Q (x) + x^{\frac{n}{2}} P (x)) \cdot (R (x) + x^{\frac{n}{2}} S (x)) = \\ Q (x) R (x) + x^{\frac{n}{2}} (Q (x) S (x) + P (x) R (x)) + x^{n} (P (x) S (x)) \end{matrix}

כעת נוכל לחשב את ארבעת המכפלות שיצרנו שהם בעצם פולינומים מדרגה חסומה $\frac{n}{2}$ באופן ריקורסיבי. החיבור של הכל הוא ליניארי וחסום ב $O (n)$ והנוסחה הריקורסיבית תיראה כך :

T (n) = {\begin{cases} Θ (1) & n = 1 \\ 4 T (\frac{n}{2}) + O (n) & n \geq 2 \end{cases}

לפי משפט המאסטר האלגוריתם חסום ב $O (n^{2})$ .
נוכל לייעל את האלגוריתם אם נשים לב ש:

\begin{matrix} p_{1} (x) = Q (x) \cdot R (x) \\ p_{2} (x) = P (x) \cdot S (x) \\ p_{3} (x) = (Q (x) + P (x)) \cdot (R (x) + S (x)) \end{matrix}

ויתקיים :

p_{3} (x) - p_{1} (x) - p_{2} (x) = P (x) R (x) + Q (x) S (x)

ובהצבת בביטוי למעלה נקבל

p_{1} + x^{\frac{n}{2}} (p_{3} - p_{1} - p_{2}) + x^{n} p_{2}

כלומר נוכל לחשב את שלושת הפילונים בצורה ריקורסיבית במקום ארבעה, (החיבור פולינומים וכל זה נעשה בזמן ליניארי $O (n)$ ) וכן מבצעים פחות פעולות ריקורסיביות :

T (n) = {\begin{cases} Θ (1) & n = 1 \\ 3 T (\frac{n}{2}) + O (n) & n \geq 2 \end{cases}

כעת זמן הריצה הינו $O (n^{\log_{2} 3}) = O (n^{1.543})$ .

אז מה יש לנו עכשיו?

Pasted image 20221029182918.png

אומנם צמצמנו את הכפל בתצוגת מקדמים אבל לא הגענו למקרה הטוב שאנחנו מקבלים במקרה שבו מבצעים כפל בתצוגת נקודות.
על פניו נראה שפעולת ההמרה ממקדמים לדגימה ואז כפל לא יעזור לגם במצב שבו ערכים הנקודות שרוצים להציב בשתי הפולינומים הם זהים בגלל שאינטרפולציה זה החסום ב $O (n^{2})$ . עם זאת נראה שאכן ישנו אלגוריתם שמייעל את התהליך הזה לזמן ריצה החסום ב $O (n \log n)$ .

FFT

עבור פולינום $A (x)$ מדרגה חסומה $n$ . נרצה לעבור מתצוגת המקדמים לנקודות על ידי דגימת ${x_{i} | i \in [0, n - 1]}$ ערכים שונים והצבת ב $A (x)$ .
נחלק את הפולינום ל $2$

A_{e v e n} (x) = \sum_{i = 0}^{\frac{n}{2} - 1} a_{2 i} x^{i}

A_{o d d} (x) = \sum_{i = 0}^{\frac{n}{2} - 1} a_{2 i + 1} x^{i}

כעת יתקיים :

A_{e v e n} (x^{2}) + x \cdot A_{o d d} (x^{2}) = \sum_{i = 0}^{\frac{n}{2} - 1} a_{2 i} x^{2 i} + \sum_{i = 0}^{\frac{n}{2} - 1} a_{2 i + 1} x^{2 i + 1} = A (x)

נשים לב גם ש $A (- x) = A_{e v e n} (x^{2}) - x \cdot A_{o d d} (x^{2})$

יש לנו שני פולינום עם דרגה חסומה $x^{\frac{n}{2}}$ .
נראה כי נוכל לחשב ריקורסיבית את הפולינומים שבנינו ואז לבצע פעולות כפל וחיבור בזמן ליניארי כך שבסך הכל נקבל נוסחת נסיגה

T (n) = 2 T (\frac{n}{2}) + O (n) \in O (n \log n)

הקריאות האלו יוצרות 2 בעיות עיקריות

לא מובטח ש $\forall_{i, j \in [n]} : (x_{i})^{2} \neq (x_{j})^{2}$ למרות שבלי העלאה בריבוע הם היו שונים.
הקטנו את דרגת הפולינום החסומה בריקורסיה אבל מספר האיקסים נשאר אותו דבר $n$ ולכן הבעיה הריקורסיבית לא פותרת את המקרה שהדרגה החסומה של הפולינום ומספר ה $x$ שווה אלא מצב בו הם שונים. כלומר אנחנו עדיין נצטרך לחשב $n$ ערכים בסופו של דבר.

כדי לפתור את הבעיה הנ״ל נגדיר ונוכיח מספר טענות :

תכונת הנגדיות החלשה

יהי $n$ חזקה של 2, נאמר שוקטור של נקודות $(x_{0}, x_{1}, x_{2}, \dots, x_{n - 1})$ יקיים את תכונת הנגדיות החלשה אם:

$n = 1$
$\forall_{j \in [0, \frac{n}{2} - 1]} : x_{\frac{n}{2} + j} = - x_{j}$
כלומר מעין תמונה מראה עם סימן הפוך למשל : $(5, - 1, 3, 2, - 5, 1, - 3, - 2)$ מקיים את תכונת הנגדיות החלשה.

איך זה מקדם אותנו?
אכן אנחנו נרצה להציב $n$ ערכי $x$ שונים אבל בגלל קיום תכונת הנגדיות החלשה אנחנו יכולים לצמצם את המערך בחצי ו גם את מספר ההצבות שנצטרך לעשות כי בהעלה בריבוע נקבל מערך סימטרי לחלוטין גם בסימן.

(x_{\frac{n}{2} + j})^{2} = (- x_{j})^{2} = x_{j}

עם זאת , תכונת הנגדיות החלשה עבור וקטור $\overset{―}{x}$ לא מבטיח שכשנפעיל את הריקורסייה פעם נוספת נקבל שוב וקטור שיקיים תכונה זו. למשל בוקטור הנ״ל שנתנו בחציתו לשתיים והעלאה בריבוע נקבל $$(25,1,9,4)$$ וקטור זה כבר לא מקיים את התכונה שרצינו. לכן הבעיה לא נפתרה לגמרי.

תכונת הנגדיות החזקה

יהי $n$ חזקה של 2, נאמר שוקטור של נקודות $(x_{0}, x_{1}, x_{2}, \dots, x_{n - 1})$ יקיים את תכונת הנגדיות החזקה אם:

$n = 1$
הוקטור מקיים את תכונת הנגדיות החלשה וגם הוקטור $(x_{0}, x_{1}, \dots, x_{\frac{n}{2} - 1})^{2}$ כלומר העלאת חציו השמאלי של הוקטור בריבוע, מקיים את תכונת הנגדיות החזקה.

ההגדרות שלנו אכן פותרות את הבעיות שהצגנו למעלה, אבל עכשיו צריך למצוא סדרה מספרים שתקיים את הנ״ל

מספרים מרוכבים וFFT

בוא ננסה לעשות reverse engineering לבעיה שלנו.
נניח והיינו עם איבר אחד בפולינום מדרגה חסומה $1$ וערך ה $x$ שנרצה לחשב הוא $1$ .
קריאה אחת לפני היינו צריכים לחשב פולינום מדרגה חסומה $2$ בשתי נקודות $\pm \sqrt{1}$ כי לקחנו את חצי המערך השמאלי והעלנו אותו בריבוע. במצב זה יתקיים $(- 1, 1)$ הוא הוקטור של הערכים במציבים. מה שזה אומר שקריאה אחת לפני הוקטור מייצג פולינום מדרגה חסומה $4$ עם הערכים $(\sqrt{1}, - \sqrt{1}, \sqrt{- 1}, - \sqrt{- 1})$ כלומר $(1, - 1, i, - i)$ .

אנחנו מתקדמים, עוד קצת הגדרות :

שורשי היחידה

שורש יחידה מסדר $n$ הוא מספר מרוכב $ω$ כאשר $w^{n} = 1$ . ובאופן כללי

w_{n} = e^{i \cdot \frac{2 π}{n}}

כאשר $r = 1$ כלומר על מעגל היחידה

תזכורת: מספר מרוכב ניתן להציג בשלוש צורות

z = a + i b = r c i s (Θ) = r \cdot e^{i Θ}

טענה :

w_{n}^{\frac{n}{2}} = (e^{i \cdot \frac{2 π}{n}})^{\frac{n}{2}} = e^{i π} = - 1

נוסחה זאת נקראת נוסחת אוילר.

טענה :

\forall_{k \in [0, n - 1]} : (w_{n}^{k})^{n} = 1

במילים, לכל $k$ מתקיים שהעלאת $w_{n}$ בחזקת $k$ גם הוא יהיה שורש יחידה מסדר $n$ .
הוכחה פשוטה-

(e^{i \frac{2 k π}{n}})^{n} = e^{i \cdot 2 k π} = 1

על מעגל היחידה .

אנקדוטה : שורשי היחידה מהווים חבורה חילופית ביחס לפעולת הכפל.

w_{n}^{j} w_{n}^{k} = w_{n}^{(j + k) m o d n}

וגם

w_{n}^{- 1} = w_{n}^{n - 1}

ובאופן כללי

(w_{n}^{i})^{- 1} = w_{n}^{n - i}

כלומר יש מעין מחזוריות כזאת על מעגל היחידה בהתאם ל $n$ .

Pasted image 20221029230822.png|600

טענה : וקטור שורשי היחידה מסדר $n$ מקיים את תכונת הנגדיות החזקה .
הוכחה -
שלב א נוכיח קודם שהוא מקיים את תכונת הנגדיות החלשה.

w_{n}^{(\frac{n}{2} + k)} = w_{n}^{\frac{n}{2}} \cdot w_{n}^{k} = w_{n}^{k} \cdot (- 1) = - w_{n}^{k}

שלב ב נסתכל על הוקטור:

(w_{n}^{k} | k \in [0, \frac{n}{2} - 1])^{2}

צריך להוכיח שוקטור זה מייצג את $\frac{n}{2}$ שורשי היחידה מסדר $\frac{n}{2}$ . (כלומר העלאה בריבוע של החצי הראשון של שורשי היחידה מסדר $n$ ) .

\forall_{k \in [0, \frac{n}{2} - 1]} : w_{n}^{2 k} = e^{2 π \frac{i 2 k}{n}} = e^{2 π \frac{i k}{\frac{n}{2}}} = (e^{\frac{i 2 π}{\frac{n}{2}}})^{k} = w_{\frac{n}{2}}^{k}

שזה שורש יחידה מסדר $\frac{n}{2}$ .

שלב ג נוכיח את תכונת הנגדיות החזקה באינדוקצייה על $n$ באשר הוא חזקה מדויקת של $2$ .
בסיס : $n = 1$ מקיים מהגדרה.
צעד : נניח שהטענה נכונה לכל $k \in [0, n - 1]$ ונוכיח עבור $k = n$ .
הוקטור של שורשי היחידה מסדר $n$ מקיים את תכונת הנגדיות החלשה כפי שהראנו, כעת ניקח את חציו השמאלי ונעלה בריבוע וזה לפי מה שהוכחנו מייצג את $\frac{n}{2}$ שורשי היחידה מסדר $\frac{n}{2}$ ולפיכך הם בעצמם מקיימים את תכונת הנגדיות החזקה לפי הנחת האינדוקצייה.

נשים לב שקיבלנו במתנה את העובדה ש $n$ שורשי היחידה מסדר $n$ הם ערכים שונים .

האלגוריתם FFT

כעת משמצאנו סדרת מספרים שתקיים את התנאים שלנו נוכל לכתוב אלגוריתם פסודו לבעיה שלנו

FFT((A = [a0,a1,a2,...,a_n-1]))
	if n=1 
		return a0
	let A_even = (a0,a2,a4,..., a_n-2)
	let A_odd = (a1,a3,a5,...,a_n-1)
	P_even = FFT(A_even)
	P_odd = FFT(A_odd)

	for j=0 to (n/2 -1) :
		y_j = P_even[j]+ pow(w_n , j) * P_odd[j]
		y_(n/2 +j) = P_even[j] - pow(w_n, j) * P_odd[j]

	return (y_0, y_1 ,y_2 , ... ,y_n-1)

הסבר :
נרצה לחשב את ערכי הפולינום $A (x) = \sum_{i = 0}^{n - 1} a_{i} x^{i}$ על ידי הצבת $n$ שורשי היחידה מסדר $n$ . האלגוריתם יחזיר וקטור

\overset{―}{y} = (y_{0}, y_{1}, \dots, y_{n - 1})

כאשר

y_{k} = A (x_{k}) = A (w_{n}^{k}) = A (e^{\frac{2 π k}{n}})

מקרה בסיס לריקורסיה- וקטור בגודל $1$ , במקרה זה מחזירים את המקדם היחיד בוקטור $a_{0}$ כיוון שאין מה להציב עבורו זה פולינום קבוע.
בכל מצב אחר נפעיל את האלגוריתם על $A_{e v e n}$ על מנת לחשב את הפולינום בהצבת $\frac{n}{2}$ שורשי היחידה מסדר $\frac{n}{2}$ . כלומר הקריאה הריקורסיבית מחזירה:

P_{e v e n} = [A_{e v e n} (w_{\frac{n}{2}}^{0}), A_{e v e n} (w_{\frac{n}{2}}^{1}), \dots, A_{e v e n} (w_{\frac{n}{2}}^{\frac{n}{2} - 1})]

באופן דומה :

P_{o d d} = [A_{o d d} (w_{\frac{n}{2}}^{0}), A_{o d d} (w_{\frac{n}{2}}^{1}), \dots, A_{o d d} (w_{\frac{n}{2}}^{\frac{n}{2} - 1})]

עכשיו ניתן לחשב את הערכים

(A (w_{n}^{k}) | k \in [0, n - 1])

לפי הנוסחא שבנינו ונוסחת הנגדיות החלשה.
בגלל התכונות הנ״ל ניצחנו את הבעיות שהיו לנו כשחשבנו על האגוריתם הזה מלכתחילה . על כל תת וקטור שמאלי נצטרך להציב רק חצי מהערכים כדי לקבל את החצי השני.

זמן ריצה:
באופן הזה זמן הריצה אכן תואם את הנוסחה הריקורסיבית ונקבל

T (n) = 2 T (\frac{n}{2}) + O (n) = O (n \log n)

inverse FFT

נניח שהעברנו שני פולינומים מייצוג מקדמים לייצוג דגימה על ידי $F F T$ , והכפלנו את שניהם בזמן ליניארי (כי משתמשים בשורשי היחידה שזה אותם נקודות). כעת קיבלנו פולינום $C (x) = A (x) B (x)$ בתצוגת נקודות. כעת נרצה להעביר את $C (x)$ לייצוג מקדמים:

יש לנו

\overset{―}{y} = (y_{0}, y_{1}, \dots, y_{n - 1}) where: y_{k} = C (w_{n}^{k})

ואם אנחנו זוכרים מתקיים

V \cdot \overset{―}{c} = \overset{―}{y}

כאשר $\overset{―}{c}$ הוא וקטור המקדמים.

[\begin{matrix} (w_{n}^{0})^{0} & (w_{n}^{0})^{1} & (w_{n}^{0})^{2} & \dots & (w_{n}^{0})^{n - 1} \\ (w_{n}^{1})^{0} & (w_{n}^{1})^{1} & (w_{n}^{1})^{2} & \dots & (w_{n}^{1})^{n - 1} \\ ⋮ \\ (w_{n}^{0})^{0} & (w_{n}^{n - 1})^{1} & (w_{n}^{n - 1})^{2} & \dots & (w_{n}^{n - 1})^{n - 1} \end{matrix}] \cdot \overset{―}{c} = \overset{―}{y}

נשים לב שזה בעצם עמודה ושורה שכולם $1$ .
כדי למצוא את וקטור המקדמים נשאלת השאלה מהי הפונקצייה ההופכית יתקיים כי :

D F T = F F T^{- 1} = \frac{1}{n} \cdot [\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ 1 & (w_{n}^{- 1})^{1} & (w_{n}^{- 1})^{2} & \dots & (w_{n}^{- 1})^{n - 1} \\ ⋮ \\ 1 & (w_{n}^{1 - n})^{1} & (w_{n}^{1 - n})^{2} & \dots & (w_{n}^{1 - n})^{n - 1} \end{matrix}]

נשים לב שבגלל שמדובר בחבורה אז קיים ההופכי ואמרנו כבר מהו למעלה זה בעצם פשוט $(w^{- 1})^{k} = w^{n - k}$ כלומר עדיין מדובר בשורש יחידה מסדר $n$ .

גם זאת מטריצה ונדרמונדה ולכן תהליך ההמרה לכיוון השני הוא גם $O (n \log n)$ .

נוכיח שזאת אכן המטריצה ההופכית -
ראשית ארצה להוכיח טענת עזר :
נסמן את מטריצה ונדרמונדה עם שורשי היחידה מסדר $n$ כ $M_{n} (w_{n})$ ונרצה להוכיח שכאשר מציבים במקום $w_{n}$ את $w_{n}^{- 1}$ נקבל

M_{n} (w) \cdot M_{n} (w^{- 1}) = n \cdot I

האלמנט ה $m_{i, j}$ של המטריצה יהיה לפי כפל מטריצות :

\sum_{k = 0}^{n - 1} w^{(i - 1) \cdot k} w^{- (j - 1) \cdot k} = \sum_{k = 0}^{n - 1} w^{(i - j) k}

כעת יתקיים שבכל נקודה שבה $i = j$ נקבל $n$ כיוון שאנחנו סוכמים $1$ סך הכל $n$ פעמים.
אפשר להסתכל על זה גם כסדרה חשבונית ונקבל

s_{n} = \frac{1 - w^{n (i - j)}}{w^{(i - j)}} = \frac{1 - 1}{w^{i - j}} = 0

אחרת, אנחנו יודעים שלכל איבר בשורשי יחידה יש אחד שיבטל אותו בסכום ולכן נקבל $0$ . כלומר קיבלנו את $n \cdot I$ .
מה שאומר ש

F F T = M_{n} (w), F F T^{- 1} = \frac{1}{n} \cdot M_{n} (w^{- 1})

שזה בידיוק מה שרשמנו למעלה.

כעת רק נרצה לתאר בהליך פסודו קוד את האלגוריתם $I F F T$ שמטרתו תהיה לבצע אינטרפולצייה הפוכה, ממצב של תצוגה לפי נקודות למצב של תצוגה לפי מקדמים :

IFFT([A(w^0), A(w^1),....,A(w^n-1)]):
	return FFT(A(w^n),A(w^n-1),...., A(w))) / n

הרעיון הוא שהדרך להגיע לוקטור המקדמים באמצעות ההופכית שהראנו שגם היא מטריצת ונדרמונדה עם שורשי יחידה מסדר $n$ ולכן נוכל לנצל את התכונה הזאת כדי להפעיל את אלגוריתם $F F T$ כאשר מתייחסים למקדמים בסדר הפוך (כפי שהם מסודרים במטריצה $F F T^{- 1}$ ).

שימוש ב FFT

כעת משלמדנו על איך האלגוריתם עובד נרצה להסתכל עליו כמעין קופסה שחורה כדי לפתור בעיות אחרות.

בעיית פולינום המכפלה מדרגות שונות

קלט : $A (x) = \sum_{i = 1}^{n - 1} a_{i} x^{i}, B (x) = \sum_{i = 1}^{m - 1} b_{i} x^{i}$ (בלי הגבלת הכלליות נניח $m \leq n$ ).
פלט: פולינום המכפלה $C (x) = (A B) (x)$ .

דרך א : נוסיף מקדמי $0$ לפולינום $B (x)$ כדי להשוות בדרגות ולאחר מכן נריץ fft.
דרך ב: כפל פולינומים בשיטה הנאיבית $O (m \cdot n)$
דרך ג : נבדוק $min (m \cdot n, n \log n)$ ובהתאם לזה נריץ את האלגוריתם הטוב.

נרצה פתרון ב $O (n \log m)$ . במבנה נתונים היינו נעזרים בחלוקת המבנה כדי לעשות אלגוריתם כלשהו בזמנים שכאלה. נעשה את אותו דבר על הפולינום.

נניח כי $m | n$ אחרת, פשוט נשלים את $n$ עם מקדמי $0$ עד שהתנאי יתקיים (השלמה של לכל היותר $m - 1$ איברים).
כעת הפולינום $A (x)$ ייראה כך:

\begin{matrix} A (x) = \sum_{i = 0}^{m - 1} a_{i} x^{i} + \sum_{i = m}^{2 m - 1} a_{i} x^{i} \dots + \sum_{i = \frac{m (n - m)}{m}}^{n - 1} a_{i} x^{i} = \\ \sum_{i = 0}^{m - 1} a_{i} x^{i} + x^{m} (a_{m} x^{0} + \dots a_{2 m - 1} x^{m - 1}) + x^{2 m} (a_{2 m} x^{0} + \dots + a_{3 m - 1} x^{m - 1}) + \\ \dots + x^{m (\frac{n}{m} - 1)} (a_{m (\frac{n}{m} - 1)} x^{0} + \dots + a_{n - 1} x^{m - 1}) \end{matrix}

כעת , נגדיר

\forall_{k \in [0, \frac{n}{m} - 1]} : A_{k} (x) = \sum_{i = 0}^{m - 1} a_{k m + i} x^{i}

זאת חלוקה שמכסה את הפולינום $A (x)$ ונוכל לסמנו ככה:

A (x) = \sum_{k = 0}^{\frac{n}{m} - 1} x^{k m} \cdot A_{k} (x)

כעת חילקנו את הפולינום מדרגה חסומה $n$ ל $\frac{n}{m}$ פולינומים מדרגה חסומה $m$ ונוכל להכפיל כל אחד מהם ב $B$ באמצעות $F F T$ .

C (x) = \sum_{k = 0}^{\frac{n}{m} - 1} x^{k m} (B \cdot A_{k}) (x)

זמן ריצה : האלגוריתם מבצע $\frac{n}{m}$ פעולות כפל של פולינומים שדרגתפ חסומה ב $m$ סך הכל זמן הריצה

O (\frac{n}{m} \cdot m \log m) = O (n \log m)

בנוסף נדרשת סכימה של התוצאות ב $C (x)$ שהוא פולינום מדרגה $2 m - 1$ ויש $\frac{n}{m}$ תתי פולינומים לסכום כלומר הסכום הוא בזמן ליניארי $O (n)$ .

שימו לב: פעולת כפל של פולינום $P (x)$ בפולינום $x^{t}$ היא בסה"כ הזזה של כל מקדם $p_{i}$ בפולינום $P$ להיות המקדם $p_{i + t}$ בםולינום המכפלה. לכן, זמן חישוב המכפלה הוא לינארי במספר המקדמים השונים מ־0 של P.

בעיית חישוב מרחקי האמינג בין טקסט לתבנית

הגדרה : בעית התאמת המחזורות Pattern Matching -
קלט - מחרוזת $T$ באורך $n$ ומחרוזת $P$ באורך $m \leq n$ שמייצגת תבנית.
פלט- כל המקומות ב $T$ ש $P$ מופיע בהם.

הגדרה : Hamming Distance - לשתי מחרוזות $A, B$ באורך זהה $n$ מרחק ההאמינג של $A, B$ הוא מספר האינדקסים בהם $A, B$ שונים כלומר:

H a m (A, B) = | {i | A [i] \neq B [i]} |

לדוגמה :
Pasted image 20221030175254.png

הגדרה : בעיית חישוב מרחקי האמינג בין טקסט לתבנית
קלט - מחרוזת $T [1. . n]$ באורך $n$ ומחרוזת $P$ באורך $m \leq n$
פלט - $$\forall_{i\in [0, n-m]} : Ham(P, T[i+1\dots i+m])$$
כאשר $Σ = {1, 0}$ כלומר הא״ב הבינארי.

אלגוריתם Fischer Paterson
נסמן את הטקסט באופן הבא $T = a_{0} a_{1} \dots a_{n - 1}$ ואת התבנית $P = b_{0} b_{1} \dots b_{m - 1}$
$F F T$ מאפשר לבצע כפל של פולינומים בזמן ליניארי. ננסה להסתכל על על כפל בצורה מופשטת המתארת פעולה בינארית בין שתי אובייקטים ומחזירה מספר. כפל פולינומים דומה לכפל של מספרים מרובה הספרות. אפשר להסתכל על ספרה כמקדם של הבסיס בחזקת $i$ למשל עבור המספר $245$ הספרה $2$ היא המקדם של $10^{2}$ כמו בפולינום $2 x^{2} + 4 x + 5$ . נשים לב שהייצוג של חישוב מספרים בכפל ארוך גם הוא יעבוד במקרה של פולינומים. זה לא משנה ש FFT מחשב את התוצאה באמצעי שאינו כפל ארוך מה שחשוב זה רק עניין הייצוג. מה שיקרה בפועל באלגוריתם שלנו זה שנבין אין זה נראה בייצוג של כפל ארוך ולאחר מכן נשתמש ב FFT אחרי שנעביר את המספר הבינארי לייצוג פולינומי בשיטת מקדמים.

נסתכל על כפל ארוך בין שני מספרים/פולינומים המייצגים את הטקסט והתבנית.
נכפול את $T$ ב $P^{r}$ כשהסימון הזה מייצג את היפוך סדר האותיות. למשל אם $n = 5, m = 3$ נסתכל על הפולינומים $(a_{0} a_{1} a_{2} a_{3} a_{4}), (b_{2} b_{1} b_{0})$ ונכפול אותם.
הסיבה שכופלים בסדר הפוך היא בגלל איך שעובד חישוב המקדם ה $i$ בפולינום המכפילה. כפי שנאמר למעלה המקדם $c_{i}$ זה $\sum_{k = 0}^{i} a_{k} b_{i - k}$ וההתקדמות הזאת אחורה אינה טובה לנו כדי לתאר התאמת מחרוזת כפולינום. נרצה שההיסט תמיד יהיה ממוקם כמו שצריך ובreverse זה מה שקורה.

Pasted image 20221030181341.png
נשים לב שבכל אחת משלוש העמודות האמצעיות אנו נקבל סכום של מכפלת אותיות מקבילות בתבנית ובטקסט, כאשר שמים את התבנית מול הטקסט בהיסטים שונים. אלה יתנו את המקדם במיקום מסויים. הסכום לכאורה אמור לתאר את מספר ההתאמות בטקסט בהיסט מסויים.
נרצה שהסכימה הזו תהיה משמעותית אנחנו נדאג לכך שהסכום יהיה בדיוק מספר המקומות בהם התבנית מתאימה לטקסט.
לצורך כך, נרצה שה"כפל" בין שני תווים יקיים $a b = 1$ אם $a = b$ ו $a b = 0$ אם $a \neq b$ .
בטבלה זה ייראה כך
Pasted image 20221030182019.png
היינו יכולים לעשות כפל בצורה הטריוויאלית ולחשב את הפעולה הנ״ל שרצינו בזמן $O (n m)$ ואז את הבדיקה הנ״ל בזמן $O (1)$ . אבל אנחנו רוצים זמן יותר טוב מזה באמצעות אלגוריתם $F F T$ . הבעיה היא שהאלגוריתם הזה תומך בכפל פולינומים כאשר הכפל מוגדר ככפל רגיל בשדה המרוכבים ולא באופן שתיארנו אותו עכשיו (כלומר יהיה לנו בעיות עם מחרוזות שנראות ככה $001001010$ למשל).
כדי להתגבר על הבעיה הזאת נפריד את החישוב לשני חישובים.
רצינו לספור את כל המקומות בהם תו התבנית זהה לתו בטקסט בהיסט המתאים. כל מקום כזה עונה בידיוק על אפשרות אחת מתוך השניים

$a = b = 1$
$a = b = 0$
בשביל הראשון נוכל להשתמש בפועל הכפל הרגילה בין שני מקדמים

בגלל שזאת פעולת הכפל הרגילה, נוכל להשתמש באלגוריתם $F F T$ באופן מיידי.
למקרה השני נזדקק לפעולה הבאה :

כדי לקבל פעולה כזאת באמצעות הכפל הרגיל פשוט נהפוך את הביטים בטקסט ואת הביטים בתבנית ובמצב זה נקבל בידיוק את מה שרצינו

סך הכל נצטרך לעשות שתי פעולות $F F T$ וסכימה של תוצאותיהן, נדע כמה התאמות יש בין התבנית לטקסט בכל היסט. נשים לב שאת ההתאמות נבדוק במקדמים $m$ עד $n - m - 1$ בגלל שרק במצבים האלה אין ״זליגה״ של היסט של $P$ מאורך המחרוזת $T$ .
המקדם ה $i$ בפולינום התוצאה, ייתן לנו את מספר ההתאמות כאשר ההיסט התחיל באינדקס $i$ .
לבסוף כל מה שצריך זה לקחת את המספר ההתאמות ולחסר אותו מאורך התבנית $m$ כדי לקבל את מספר אי ההתאמות, שזה בידיוק מרחק האמינג. כעת צריך לבדוק האם באחד האינדקסים מספר אי ההתאמות הוא 0 ואז אכן מצאנו התאמה.
סך הכל זמן הריצה $O (n \log m)$ עם האלגוריתם מהתרגיל הקודם.

מרחק האמינג על א״ב גדול יותר

נראה גם כיצד ניתן לחשב את מרחק האמינג על א״ב מהצורה ${0, 1, 2}$
בדומה לבעיית המרחק הרגילה, נגדיר את הטקסט כפולינום $T = a_{0} a_{1} \dots a_{n - 1}$ וגם את התבנית $P = b_{0} b_{1} \dots b_{m - 1}$ . המשמעות היא שלכל $i, j$ בגבולות של אורכי הטקסט והתבנית בהתאמה יתקיים ש $a_{i}$ הוא המקדם של הפולינום $x^{i}$ ב $T$ ו $b_{j}$ יהיה $x^{j}$ ב $P$ . כלומר ייצוג לפי מקדמים.

נשים לב שטבלת הכפל הרגילה תיתן לנו

T/P	1	2
0	0	0
1	1	2
2	2	4

זה לא ממש עוזר לנו להבין האם יש התאמה בדומה לכפל הרגיל כאשר הא״ב היה רק ${1, 0}$ .

באלגוריתם המקורי מה שעשינו היה להחליף בין 1 ל 0 על ידי פעולת $n o t$ . כעת מה שנעשה הוא פשוט 3 החלפות ל0 כדי שכל החלפה נקבל התאמה לספרה אחרת, כלומר אם באלגוריתם המקורי עשינו פעמיים $F F T$ לכל ספרה. כעת נעשה 3 פעמים.

בכפל הראשון נגדיר את $2 = 0$ ואז נקבל התאמה עבור הספרה 1.
בפעם השנייה נגדיר את $0 = 1$ ו $2, 1 = 0$ ואז נקבל התאמה עבור הספרה $0$
לבסוף נגדיר $2 = 1$ ואת $1 = 0$ כדי לקבל התאמה עבור הספרה 2.

נזכיר שכופלים $P^{R}$ כל פעם ונשים לב שאת ההחלפות הנ״ל עושים גם על $T$ וגם על $P$ למעשה אפשר לבטא את כפל הפולינומים שנעשה באופן כללי על ידי:

\forall_{σ \in Σ} : F F T (T_{σ}, P_{σ}^{R})

כאשר $P_{σ}, T_{σ}$ הם המחרוזות לאחר ההחלפה של כל התווים ל $0$ פרט ל $σ$ .

כעת קיבלנו 3 פולינום והאלגוריתם נשאר אותו דבר, מכאן, מבצעים סכימה באינדקסים בהם אין גלישה של התבנית $m$ עד $n - m - 1$ ונקבל את מספר ההתאמות,
כל אינדקס נחסר מ $m$ כדי לקבל את מספר אי ההתאמות.

זמן הריצה זהה לזמן ריצה המקורי שהוא $O (n \log m + n + m)$ . הסיבה שזה $n \log m$ הוא בגלל שהכפלנו פולינומים מדרגות שונות.

3sum

קלט: מערך $A [1 \dots n]$ של מספרים שלמים.
פלט: flag האם קיימים שלושה מספרים $x, y, z \in A$ כך ש $x + y = z$ .

א. בזמן ריצה $O (n^{2})$ - נשתמש באלגוריתם $2 S U M$ שכולל מיון של המערך ולאחר מכן נרוץ על איברי המערך ולכל איבר $A [i]$ נבדוק האם קיימים זוג איברים שהסכום שלהם ייתן את $A [i]$ . זה יקרה על ידי החזקת מצביע בתחילת המערך וסופו (נזכיר שהוא ממויין בשלב זה) ואם הסכום גדול מידי נזיז אחורה את המצביע לסוף המערך אחרת נזיז ימינה את הפוינטר שבתחילת המערך.

ב. על ידי שימוש ב $F F T$ : (זה יעבוד בהינתן שמספר האיברים חסום בגודל מאוד גדול למשל $10 n^{1.5}$ )
נייצר מערך $B$ באורך $10 n^{1.5}$ שכולו אפסים. כעת, לכל $x \in A$ נכניס $B [x] = 1$ . נוכל להתייחס למערך הזה כפולינום בצורת מקדמים למשל עבור המערך $A = [1, 2, 4]$ הפולינום יהיה $x + x^{2} + x^{4}$ .
כעת נסמן $C = B^{2}$ שהגענו אליו באמצעות כפל של $B$ בעצמו עם $F F T$ . זמן הריצה הזה ייקח $O (n^{1.5} \log n^{1.5}) = O (n^{1.5} \log n)$ .
כעת נוכל פשוט לרוץ על איברי המערך $A$ ולבדוק האם $C [A] \geq 1$ . במצב זה המשמעות היא שהיו שתי חזקות שסכומם יצא $x \in A$ . כלומר בצורה כללית יותר אם קיימים $s, t$ שסכומם ייתן $z$ משמעות הדבר שקיים בפולינום $C$ איבר מהצורה $k x^{s + t}$ ששניהם שייכים ל $A$ . אם זה לא מתקיים נחזיר false.

שאלת הקורדינטות

בהינתן שתי קבוצות $A, B$ שכל אחת מהן מכילה נקודה דו מימדית מ $Z \times {- 1, 1}$ וגם בקבוצה $A$ זה תמיד יהיה $- 1$ ובקבוצה $B$ זה תמיד יהיה $1$ .
Pasted image 20221114215437.png|400
נגדיר $\forall_{a, b \in A, B} : δ_{a, b}$ שזה הקטע המחבר את $a, b$ . כמו כן, נגדיר את הקבוצה

L_{A, B} = {δ_{a, b} | a \in A \land b \in B}

כמו כן בדומה לסעיף הקודם נניח שערכי $x$ חסומים מלמעלה על ידי $10 n^{1.5}$ . נרצה למצוא אלגוריתם שמחשב את מספר נקודות החיתוך השונות ב $L$ עם ציר ה $x$ .

כדי לפתור את זה נשתמש בשיטה מהתרגיל הקודם כלומר נייצג את $A$ על ידי פולינום באמצעות השמה של $1$ באינדקס $(a, - 1) \in A$ . באופן פורמלי :

P_{A} = \sum_{(a, - 1) \in A} : x^{a}

נגדיר בידיוק אותו דבר על $B$ וכעת נבנה פולינום חדש $P_{C} = P_{A} \cdot P_{B}$ . את זה נעשה בעזרת האלגוריתם $F F T$ . התשובה תהיה מספר המקדמים השונים מ 0 ב $P_{C}$

למה זה נכון?
נשים לב שבגלל הנתון של החסמים בציר ה $y$ אנחנו מקבלים שלכל 2 נקודות כאשר אחת מ $A$ והשנייה מ $B$ יתקיים שהחיתוך עם ציר ה $x$ היא בידיוק באמצע הישר הזה. כלומר, שיעור ה $x$ של נקודת המפגש תהיה $\frac{a + b}{2}$ . המשמעות היא שהפתרון טמון בעובדה שאנחנו מחפשים בעצם את בעיית $3 s u m$ על $a, b$ כלומר אנחנו מחפשים ערכי $c$ שקיימים $a, b$ שיתנו את הסכום הנ״ל. זה יהיה שקול ללחפש ישירות $c$ ו $a, b$ כך ש $a + b = c$ כיוון שאלו מספרים שלמים חסומים ולכן אם מצאנו מספר $c^{'}$ שסכומו ייתן $\frac{a + b}{2}$ אז בהכרח $2 c^{'} = c$ יהיה בתחום $[0, 20 n^{1.5}]$ והוא יתאים לנו.

נוכל לטעון אם כן, שקיים $c$ בתחום שציינו שיקיים את זה אמ״מ במקדם של $x^{c}$ בפולינום $P_{C}$ שציינו יהיה שונה מ0.
זה נובע מהוכחת הנכונות של בעיית $3 s u m$ . אם קיים סכום כזה אז המקדמים של $B [b], A [a]$ יהיו $1$ . ובכפל פולינומים נקבל $x^{a + b}$ כלומר בפולינום $P_{C}$ בייצוג מקדמים יהיה באינדקס $a + b = c$ את הערך $1$ . זמן הריצה הוא $O (n^{1.5} \log n)$ .