Γρήγορος Πολυωνυμικός Πολλαπλασιασμός

Ο αλγόριθμος 22#22 παρέχει ακόμα και μία γρήγορη μέθοδο για κάποιους υπολογισμούς που μπορεί με την πρώτη ματιά να μη φαίνεται να έχει σχέση. Θεωρείστε, για παράδειγμα, το πρόβλημα του πολλαπλασιασμού δύο πολυωνύμων 1726#1726 και 1727#1727, των οποίων η πολυπλοκότητα με άμεσο πολλαπλασιασμό, χρησιμοποιώντας τους συντελεστές των πολυωνύμων, είναι ανάλογη με το γινόμενο των βαθμών τους. Υποθέστε ότι το πολυώνυμο γινομένου του οποίου τους συντελεστές θέλουμε να καθορίσουμε είναι βαθμού 1728#1728. Ένα πολυώνυμο βαθμού 1728#1728 καθορίζεται ακριβώς από τις τιμές του σε 366#366 ξεχωριστά σημεία. Επιπλέον, η τιμή του πολυωνύμου γινομένου σε ένα συγκεκριμένο σημείο 49#49 είναι ίση με το γινόμενο των πολυωνύμων-παραγόντων σε εκείνο το σημείο, δηλ., 1729#1729. Το πολυώνυμο γινομένου είναι επομένως καθορισμένο επ' ακριβώς από τις τιμές του 1720#1720 γινομένου των 603#603 και 1730#1730 σε 366#366 ξεχωριστά σημεία.

’ρα, ένας τρόπος να υπολογίσουμε το πολυώνυμο γινομένου είναι να εκτιμήσουμε τα 603#603 και 1730#1730 σε 366#366 ξεχωριστά σημεία, να υπολογίσουμε το 1720#1720 γινόμενό τους, και στη συνέχεια να πάρουμε το πολυώνυμο γινομένου με παρεμβολή από αυτές τις τιμές. Αφού το 1720#1720 γινόμενο απαιτεί μόνο 1673#1673 αριθμητικές διεργασίες, η συνολική αποδοτικότητα αυτής της μεθόδου θα εξαρτάται από το πόσο αποδοτικά μπορούμε να εκτιμήσουμε τα δοσμένα πολυώνυμα και στη συνέχεια να εφαρμόσουμε την παρεμβολή για να πάρουμε το πολυώνυμο γινομένου.

Θυμηθείτε ότι το να εκτιμήσουμε ένα πολυώνυμο σε ένα σύνολο από σημεία είναι ισοδύναμο με το να πολλαπλασιάσουμε το διάνυσμα των συντελεστών του με έναν πίνακα 1672#1672, και η παρεμβολή είναι ισοδύναμη με τον πολλαπλασιασμό με τον αντίστροφο ενόν πίνακα 1672#1672. Αυτά τα βήματα θα παρουσιάζονταν να απαιτούν τουλάχιστον 1673#1673 αριθμητικές διαδικασίες το καθένα, αλλά μπορούν να γίνουν πολύ πιο αποδοτικά αν επιλέξουμε προσεκτικά τα σημεία εκτίμησης. Συγκεκριμένα, αν επιλέξουμε τις 366#366-οστές ρίζες ενότητας, τότε οι απαραίτητες πολυωνυμικές εκτιμήσεις και παρεμβολές γίνονται απλά ο 23#23 και η αντίστροφή της. Για παράδειγμα, αν

τότε

Άρα, αν ο αριθμός των σημείων 366#366 είναι δύναμη του δύο και ο αλγόριθμος 22#22 χρησιμοποιείται κατά αυτόν τον τρόπο, τότε η πολυπλοκότητα του πολλαπλασιασμού πολυωνύμων μπορεί να μειωθεί σε 1710#1710. Το να περιορίσουμε το 366#366 να είναι δύναμη του δύο δεν είναι σοβαρός περιορισμός, αφού μπορούμε πάντα να θεωρήσουμε οποιοδήποτε πολυώνυμο που να έχει ένα βαθμό μικρότερο από την επόμενη μεγαλύτερη δύναμη του δύο παίρνοντας τους συντελεστές που απομένουν να είναι μηδέν. Αυτό το αποτέλεσμα μπορεί να δείχνει να είναι σε μεγάλο βαθμό θεωρητικού ενδιαφέροντος επειδή το κέρδος μπορεί να είναι ασήμαντο για βαθμούς πολυωνύμου που είναι πιθανόν να προκύψουν στην πράξη, αλλά καταλήγει να είναι χρήσιμο σε κάποιες εφαρμογές, όπως η επεξεργασία σημάτων, και επεξηγεί το πώς μπορεί η 22#22 να αναφύεται με απροσδόκητους τρόπους.