טרנספורמציה מהירה של פורייה (FFT)

להכפיל שני פולינומים בזמן O (nlogn)
.

במאמר זה אני מתאר את הכפל של שני פולינומים בזמן O (nlogn)
. זה משתמש באלגוריתם טרנספורמציה מהירה של פורייה (FFT).

ריבסט מתאר

הספר "מבוא לאלגוריתמים" מאת קורמן, לייזרסון וריבסט מתאר את הכפל של שני פולינומים בזמן O (nlogn). כאן, אתאר גרסה של השיטה בה השתמשו.

ראשית, צחצוח על כמה יסודות:

1. A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +..... + a_ (n-1) (x ^ (n-1)) הוא פולינום של דרגה n-1.

2. כפל הפולינומים A (x) ו- B (x) כלומר C (x) = A (x) B (x) לוקח זמן O (n ^ 2).

3. מציאת A (p) היא באמצעות החלפת p במקום x בפולינום:
A (p) = a_0 + a_1 (p ^ 2) +..... + a_ (n-1) (p ^ (n -1)).
זה לפי הכלל של הורנר הוא:
A (p) = a_0 + p (a_1 + p (a_2 +..... + p (a_ (n-1))...). זה לוקח
O (n).

4. ישנם שני סוגים של ייצוגים לפולינומים:

צורת מקדם: (a_0, a_1, a_2,....., a_ (n-1)).
צורת נקודת ערך: {(x_0, y_0), (x_1, y_1),... (x_n-1,
y_n-1)}, כאשר y (x_i) = A (x_i).

טפסים לוקחים

5. המרה מצורות מקדם לנקודת ערך נקבעת ל- O (n ^ 2) אפילו בשימוש ב"כלל הורנר "מכיוון שצריך למצוא את הערך A (x) בנקודות n.

6. שורש nth מורכב של אחדות הוא מספר מורכב w * כזה ש w * ^ n = 1.

השורש ה-עיקרי

7. שורשי האחדות n הם: w ^ 0, w ^ 1, w ^ 2,...., w ^ n-1.
w = e ^ (2 * pi * i / n) נקרא השורש העיקרי של האחדות וכל שורשי n הם כוחות של w זה.

8. מחזוריות: w ^ (k + n) = w ^ k.

עם רקע אנחנו יכולים להתחיל.

גב סמוי

להכפלת שני הפולינומים A (x) ו- B (x) הניתנים בצורות שיתופיות, אנו ממירים אותם תחילה לצורות ערך נקודתיות. הכפל בצורה נקודתית לוקח O (n).
ואז אנו מסתירים בחזרה לצורה השיתופית.
עם זאת, המרה מ- Co-יעיל לנקודת ערך לוקח O (n ^ 2) כאמור ב 5. אבל בבחירת הנקודות x_0, x_1,..... x_ (n-1) בזהירות, אנו יכולים להשיג זאת. ב- O (nlogn).

נקודות אלה אשר אנו עומדים לבחור יהוו את שורשי האחדות התשיעית. זה מה שהוא Transform Fourier Fourier (DFT).

תנאים מוזרים

כעת, A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +..... + a_ (n-1) (x ^ (n-1)).
ניתן לפצל את זה לשני פולינומים: הראשון שמכיל את המונחים הראשונים n / 2 והשני שמכיל את המונחים השני / השני. הספר "מבוא לאלגוריתמים" מתאר את הפיצול כמונחים אחידים ומשונים. כאן אנו יכולים להגיע לאותה תוצאה, אך באופן שונה במקצת.

אז ניקח A_0 (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +...... + a_ (n / 2-1) (x ^ (n / 2-1))

ו- A_1 (x) = a_ (n / 2) + a_ (n / 2 + 1) (x) + a_ (n / 2 + 2) (x ^ 2) +...... + a_ (n- 1) (x ^ (n / 2-1)).

לפיכך, אנו יכולים לכתוב A (x) כ-

A (x) = A_0 (x) + x ^ (n / 2) A_1 (x) - - - - - -> (1).

כעת, בהחלפת w במקום x, אנו רואים כי x ^ (n / 2) במשוואה (1) הופך ל-
(x ^ (n / 2)) = (w ^ (n / 2)) = +1, -1 כלומר שני שורשי האחדות.

אנו יכולים להקטין את הדגימות לשתי דגימות של מונחים שווים ומשונים.
כל ה- DFT של נקודת ה- n הפך כעת לשתי DFT של n / 2 נקודות.

ניתן לחלק את שני DFTs נקודתיים N / 2 אלה לשני DFT נקודתיים N / 4 וכן הלאה. לפיכך, המורכבות של האלגוריתם המתקבל היא O (nlogn).

הושג כיום

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

ניתן לתת את האלגוריתם הרקורסיבי כ:

לחזור

Recursive_FFT (a) {
n <- length (a)
if (n = 1) return a

w <- e ^ (2 * pi * i / n)
a [0] <- (a_0, a_1,......, a_ (n / 2-1))
a [1] <- (a_n / 2, a_ (n / 2 + 1),........, a_ (n-1))

y [0] <- Recursive_FFT (a [o])
y [1] <- Recursive_FFT (a [1])

עבור k <- 0 עד n / 2 -1
התחל
y_2k <- y_k [0] + y_k [1]
y_2k + 1 <- y_k [0] - y_k [1]
סוף
החזרה y
}

המשוואה החוזרת היא: T (n) = 2T (n / 2) + O (n), אם ניקח O (n) לכל שיחה רקורסיבית.
לפיכך, T (n) = O (nlogn).

בצע כפל

ברגע שנקבל את הצורה הנקודתית-נקודתית, נוכל לבצע הכפל בזמן O (n).

המרת ערך נקודה לצורה שיתופית יכולה להיעשות באופן דומה ב- O (nlogn). זה
הוא נקרא אינטרפולציה.

כל תהליך הכפל לוקח אם כן O (nlogn).