Γρήγορος μετασχηματισμός Fourier (FFT)

Για πολλαπλασιασμό δύο πολυωνύμων σε χρόνο O (nlogn)
.

Σε αυτό το άρθρο, θα περιγράψω τον πολλαπλασιασμό δύο πολυωνύμων σε χρόνο O (nlogn)
. Χρησιμοποιεί τον αλγόριθμο Fast Fourier Transform (FFT).

Το Rivest περιγράφει

Το βιβλίο "Εισαγωγή στους Αλγόριθμους" των Cormen, Leiserson και Rivest περιγράφει τον πολλαπλασιασμό δύο πολυωνύμων στον χρόνο 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)).
Αυτό από τον Κανόνα του Horner είναι:
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) ακόμη και όταν χρησιμοποιείτε τον Κανόνα του Horner επειδή η τιμή του A (x) πρέπει να βρεθεί στα n σημεία.

6. Η σύνθετη nth ρίζα της ενότητας είναι ένας πολύπλοκος αριθμός w * έτσι ώστε w * ^ n = 1.

Κύρια nth ρίζα

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).
Στη συνέχεια επιστρέφουμε στη φόρμα συν-αποτελεσματικότητας.
Ωστόσο, η μετατροπή από συντελεστή σε τιμή-σημείου παίρνει O (n ^ 2) όπως αναφέρεται στο 5. Αλλά, όταν επιλέξουμε προσεκτικά τα σημεία x_0, x_1,..... x_ (n-1), μπορούμε να το επιτύχουμε στο O (nlogn).

Αυτά τα σημεία που θα επιλέξουμε θα είναι οι ένατες ρίζες της ενότητας. Αυτό είναι το Discrete Fourier Transform (DFT).

Παράξενοι όροι

Τώρα, A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +..... + a_ (n-1) (x ^ (n-1)).
Αυτό μπορεί να χωριστεί σε δύο πολυώνυμα: το πρώτο περιέχει τον πρώτο όρο n / 2 και το δεύτερο περιέχει τον δεύτερο όρο 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-point έχει πλέον γίνει DFT δύο n / 2-point.

Αυτά τα δύο DFT σημείων n / 2 μπορούν περαιτέρω να χωριστούν σε δύο DFT σημείου n / 4 κ.ο.κ Ως εκ τούτου, η πολυπλοκότητα του προκύπτοντος αλγορίθμου είναι O (nlogn).

Λήφθηκε επί του παρόντος

Στην προσέγγιση που περιγράφεται στο "Εισαγωγή στους αλγόριθμους", τα δείγματα χωρίζονται σε ομοιόμορφα και περίεργα δείγματα για να ληφθούν τα δείγματα του πρώτου και του δεύτερου μισού, ακριβώς αντίθετα από αυτά που έχουμε λάβει σήμερα.

Ο αναδρομικός αλγόριθμος μπορεί να δοθεί ως:

ΕΠΙΣΤΡΟΦΗ

Recursive_FFT (a) {
n <- μήκος (a)
εάν (n = 1) επιστρέψτε 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 (α [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).