next up previous contents
Next: ΕΦΑΡΜΟΓΕΣ Up: Ο ΑΛΓΟΡΙΘΜΟΣ Previous: Ο ΑΛΓΟΡΙΘΜΟΣ   Contents

Περιορισμοί στη Χρήση του 22#22.

Παρόλο που ο αλγόριθμος 22#22 έχει ανατρέψει πολλές απόψεις αριθμητικού υπολογισμού, δεν είναι πάντα εφαρμόσιμος ή πλήρως αποδοτικός. Στην πράξη, η ακολουθία εισόδου υποθέτουμε ότι είναι:

Οι δύο πρώτες από αυτές τις ιδιότητες προέρχονται από τον ορισμό του 23#23, ενώ η τρίτη απαιτείται για πλήρη απόδοση του αλγορίθμου 22#22. Για παράδειγμα, η παρεμβολή που δίνεται από τον 1682#1682, ως γραμμικός συνδυασμός ημιτόνων και συνημιτόνων, θα είναι υποχρεωτικά περιοδική, που σημαίνει ότι για μία ακολουθία μήκους 366#366, πρέπει να έχουμε 1714#1714 ή, γενικότερα, 1715#1715 για κάθε ακέραιο 432#432 (σημειώστε ότι μόνο τα 1716#1716 ως 1717#1717 είναι καθορισμένα στην πράξη). Άρα, πρέπει να δώσουμε κάποια προσοχή κατά την εφαρμογή του αλγορίθμου 22#22 για την παραγωγή των πιο σημαντικών αποτελεσμάτων με τη μεγαλύτερη δυνατή αποδοτικότητα. Για παράδειγμα, μετατρέποντας μία ακολουθία που δεν είναι πραγματικά περιοδική ή υπερφορτώνοντας μία ακολουθία για να κάνουμε το μήκος της δύναμη του δύο μπορεί να προκαλέσει παράσιτα χωρίς λόγο και να περιπλέξει την παρεμβολή των αποτελεσμάτων.

Είναι δυνατό να ορίσουμε έναν αλγόριθμο 22#22 "μεικτής βάσης" που δεν απαιτεί το πλήθος των σημείων 366#366 να είναι δύναμη του δύο. Ο γενικευμένος αλγόριθμος εξακολουθεί να βασίζεται στην τακτική του διαίρει-και-βασίλευε. Η ακολουθία δε διαχωρίζεται απαραίτητα ακριβώς στη μέση στο κάθε επίπεδο, παρόλα αυτά, αλλά μάλλον στο μικρότερο πρώτο παράγοντα του υπολοίπου μήκους της ακολουθίας. Για παράδειγμα, μία ακολουθία μήκους 45 θα χωριζόταν σε τρεις υπακολουθίες μήκους 15, η καθεμία από τις οποίες με τη σειρά της θα χωριζόταν σε τρεις υπακολουθίες μήκους πέντε. Όταν μία υπακολουθία δε μπορεί να χωριστεί άλλο (δηλ., όταν το μήκος της είναι πρώτος αριθμός), τότε ο μετασχηματισμός της πρέπει να υπολογιστεί με τον τυπικό πολλαπλασιασμό πίνακα-διανύσματος. Η αποδοτικότητα ενός τέτοιου αλγορίθμου εξαρτάται από το αν το 366#366 είναι προϊόν μικρότερων πρώτων αριθμών (στην ιδανική περίπτωση δύναμη του δύο, φυσικά). Αν δεν έχουμε αυτή την περίπτωση, τότε μεγάλο μέρος του υπολογιστικού προτερήματος που μας δίνει ο 22#22 μπορεί να χαθεί. Για παράδειγμα, αν το 366#366 από μόνο του είναι ένας πρώτος αριθμός, τότε η αρχική ακολουθία δε μπορεί να χωριστεί καθόλου, και ο "γρήγορος" αλγόριθμος τότε γίνεται ένας τυπικός 1712#1712 πολλαπλασιασμός πίνακα-διανύσματος.



Manolis Vavalis 2000-03-24