Από τα σχολικά χρόνια, ο πολλαπλασιασμός μεγάλων αριθμών αποτελούσε πονοκέφαλο. Όμως ένας επίκουρος καθηγητής από το Πανεπιστήμιο της Νέας Νότιας Ουαλίας στο Σίδνεϊ της Αυστραλίας ανέπτυξε μια μέθοδο για τον πολλαπλασιασμό μεγάλων αριθμών, που είναι πιο αποδοτική από τον «παραδοσιακό» πολλαπλασιασμό που διδασκόμαστε οι περισσότεροι σε μικρή ηλικία.
«Πιο τεχνικά, αποδείξαμε μια υπόθεση του 1971 των Schönhage και Strassen σχετικά με την πολυπλοκότητα του πολλαπλασιασμού ακεραίων αριθμών», λέει ο επίκουρος καθηγητής David Harvey.
Η μέθοδος Schönhage-Strassen
Ο αλγόριθμος Schönhage–Strassen, που δημιουργήθηκε από τους δύο Γερμανούς μαθηματικούς, ήταν στην πραγματικότητα η ταχύτερη μέθοδος πολλαπλασιασμού από το 1971 έως το 2007. Αν και το 2007 αναπτύχθηκε μια ακόμη πιο γρήγορη μέθοδος, σπάνια χρησιμοποιείται σήμερα.
Οι Schönhage και Strassen προέβλεψαν ότι πρέπει να υπάρξει ένας αλγόριθμος που να πολλαπλασιάζει αριθμούς με n ψηφία χρησιμοποιώντας n * log(n) βασικές πράξεις, εξηγεί ο Harvey.
Η εργασία του αποτελεί την πρώτη γνωστή απόδειξη ότι αυτός ο αλγόριθμος όντως υπάρχει.
Λύνοντας τις δυσκολότερες εξισώσεις του κόσμου
Ο Harvey επιλέγει ως παράδειγμα τον πολλαπλασιασμό 314 επί 159 – μια σχετικά δύσκολη πράξη, αν και στην πραγματική ζωή χρησιμοποιούνται πολύ πιο σύνθετες εξισώσεις καθημερινά. Για να λυθεί το πρόβλημα, οι περισσότεροι μαθαίνουν να πολλαπλασιάζουν κάθε ψηφίο τους ενός αριθμού με το αντίστοιχο του άλλου και στη συνέχεια να προσθέτουν τα μερικά γινόμενα: το 9 πολλαπλασιάζεται με το 4, το 1 και το 3, έπειτα το 5 με το 4, το 1 και το 3, και ούτω καθεξής. Το αποτέλεσμα προκύπτει από 9 γινόμενα, ψηφίο προς ψηφίο. Δηλαδή, συνολικά γίνονται 9 μικροί πολλαπλασιασμοί.
Αυτή η μέθοδος ονομάζεται n² (n στο τετράγωνο), επειδή πρέπει να πολλαπλασιάσουμε n φορές το n. Δίνει μεν το σωστό αποτέλεσμα, αλλά οι Schönhage και Strassen σχεδίασαν μια πιο γρήγορη μέθοδο. Αυτή κατάφερε να ξεπεράσει το n² και να φτάσει σε κάτι μικρότερο, όμως η πρόκληση εμφανίστηκε με τη μορφή του n * log(n).
Για κάποιους, η εμφάνιση μιας λέξης στη μέση ενός μαθηματικού προβλήματος αρκεί για να τους τους κάνει να απορήσουν, όπως συνέβαινε στο μάθημα της άλγεβρας. Για να το θυμηθούμε: το “log” είναι συντομογραφία για τον λογάριθμο, ο οποίος βοηθά στον υπολογισμό εκθετών που υψώνουν αριθμούς στο τετράγωνο, στον κύβο ή ακόμα και κάτι μεγαλύτερο. Για παράδειγμα, 2⁵ = 32, αλλά λογαριθμικά γράφεται log₂(32) = 5. Αν και μπορεί να ακούγεται περίπλοκο, οι λογάριθμοι είναι κρίσιμοι όταν οι αριθμοί γίνονται πολύ μεγάλοι.
Η μέθοδος Schönhage-Strassen, είναι πολύ γρήγορη, εξηγεί ο Harvey. Αν ένας υπολογιστής χρησιμοποιούσε τη μέθοδο του τετραγώνου που διδάσκεται στο σχολείο για ένα πρόβλημα όπου δύο αριθμοί είχαν από ένα δισεκατομμύριο ψηφία ο καθένας, θα έπαιρνε μήνες. Ένας υπολογιστής με την μέθοδο Schönhage-Strassen, μπορεί να το κάνει σε 30 δευτερόλεπτα.
Αν ωστόσο, οι αριθμοί γίνουν τεράστιοι, φτάνοντας σε τρισεκατομμύρια και παραπάνω, ο αλγόριθμος που ανέπτυξαν ο Harvey και ο συνεργάτης του Joris van der Hoeven, στην πολυτεχνική σχολή στη Γαλλία, θα μπορούσε να προσφέρει λύσεις πιο γρήγορα από τον αλγόριθμο του Schönhage-Strassen του 1971.
«Σημαίνει ότι μπορείτε να κάνετε διάφορους υπολογισμούς πιο αποτελεσματικά, για παράδειγμα διαίρεση και τετραγωνικές ρίζες» λέει. «Μπορείτε επίσης να υπολογίσετε τα ψηφία του π με πιο αποτελεσματικό τρόπο από πριν. Έχει ακόμα εφαρμογές σε προβλήματα που αφορούν τεράστιους πρώτους αριθμούς».
«Οι άνθρωποι αναζητούσαν έναν τέτοιο αλγόριθμο για σχεδόν 50 χρόνια», συμπληρώνει. Δεν ήταν δεδομένο ότι κάποιος τελικά, θα κατάφερνε να τον βρει. Μπορεί άλλωστε, οι Schönhage και Strassen να είχαν κάνει λάθος και να μην ήταν δυνατός ένας τέτοιος αλγόριθμος. «Αλλά τώρα γνωρίζουμε καλύτερα», λέει.
