Οι ερευνητές του Πανεπιστημίου του Paderborn και του KU Leuven βρήκαν τη λύση σε μια μαθηματική πρόκληση που κρατούσε δεκαετίες υπολογίζοντας τον ένατο αριθμό Dedekind ή D(9), έναν απίστευτα τεράστιο αριθμό με 42 ψηφία, με τη βοήθεια ενός υπερυπολογιστή. Οι μαθηματικοί -και όχι μόνο- αναζητούσαν την ακριβή τιμή αυτού του αριθμού από το 1991.
Οι προηγούμενοι αριθμοί της σειράς είχαν βρεθεί από τον ίδιο τον μεγάλο μαθηματικό Richard Dedekind, όταν όρισε το πρόβλημα το 1897, και αργότερα από πρωτοπόρους της επιστήμης των υπολογιστών. Ο προηγούμενος γνωστός αριθμός στην «ακολουθία Dedekind», ο D(8) είχε υπολογιστεί το 1991 χρησιμοποιώντας έναν Cray 2, τον ισχυρότερο υπερυπολογιστή της εποχής. Από τότε και για 32 χρόνια, ο υπολογισμός του επόμενου αριθμού, του D(9), ήταν μια ανοιχτή πρόκληση. Αυτό ήταν το κίνητρο για το φιλόδοξο σχέδιο του Lennart Van Hirtum, τότε φοιτητή πληροφορικής στο KU Leuven και τώρα ερευνητή στο Πανεπιστήμιο του Paderborn, ο οποίος υπολόγισε τον D(9).
Κόκκοι άμμου, σκάκι και υπερυπολογιστές
Το κύριο αντικείμενο των αριθμών Dedekind είναι οι λεγόμενες μονότονες συναρτήσεις Boolean. Mπορείτε να σκεφτείτε μια μονότονη συνάρτηση Boolean σε δύο, τρεις και άπειρες διαστάσεις ως ένα παιχνίδι με έναν κύβο n διαστάσεων. Ισορροπείτε τον κύβο σε μια γωνία και στη συνέχεια χρωματίζετε κάθε μια από τις υπόλοιπες γωνίες είτε με λευκό είτε με κόκκινο χρώμα. Υπάρχει μόνο ένας κανόνας: δεν πρέπει ποτέ να τοποθετήσετε μια λευκή γωνία πάνω από μια κόκκινη. Αυτό δημιουργεί ένα είδος κάθετης διασταύρωσης κόκκινου-λευκού. Σκοπός του παιχνιδιού είναι να μετρήσετε πόσες διαφορετικές διασταυρώσεις υπάρχουν. Ο αριθμός τους ορίζεται ως ο αριθμός Dedekind. Μπορεί να μην το καταλαβαίνετε αμέσως, αλλά το μέγεθος των αριθμών γρήγορα απογειώνεται: ο 8ος αριθμός Dedekind έχει ήδη 23 ψηφία!
Τόσο μεγάλοι αριθμοί είναι γνωστοί από έναν θρύλο σχετικά με την εφεύρεση του παιχνιδιού του σκακιού. Σύμφωνα με αυτόν τον μύθο, ο εφευρέτης του σκακιού ζήτησε από τον βασιλιά μόνο μερικούς κόκκους ρυζιού σε κάθε τετράγωνο της σκακιέρας ως ανταμοιβή: έναν κόκκο στο πρώτο τετράγωνο, δύο κόκκους στο δεύτερο, τέσσερις στο τρίτο και διπλάσιους σε κάθε ένα από τα επόμενα τετράγωνα. Ο βασιλιάς κατάλαβε γρήγορα ότι το αίτημα αυτό ήταν αδύνατο να ικανοποιηθεί, επειδή τόσο πολύ ρύζι δεν υπάρχει σε ολόκληρο τον κόσμο! Ακόμα κι αν μπορούσε ο βασιλιάς να γεμίσει όλη τη σκακιέρα με ρύζι, ο αριθμός των συνολικών κόκκων ρυζιού θα είχε περίπου 20 ψηφία - ένα ασύλληπτο ποσό, αλλά και πάλι μικρότερο από το D(8)! Οπότε, με τέτοιες τάξεις μεγέθους, είναι προφανές ότι για την εύρεση του D(9) θα χρειαζόταν τόσο μια αποτελεσματική υπολογιστική μέθοδος όσο και ένας υπερυπολογιστής.
Ορόσημο: Τα χρόνια γίνονται μήνες
Για τον υπολογισμό του D(9), οι επιστήμονες χρησιμοποίησαν μια τεχνική που ανέπτυξε ο Patrick De Causmaecker, γνωστή ως τύπος του συντελεστή P (P-coefficient formula). Παρέχει έναν τρόπο υπολογισμού των αριθμών Dedekind όχι με μέτρηση, αλλά με ένα πολύ μεγάλο άθροισμα. Αυτό επιτρέπει την αποκωδικοποίηση του D(8) σε μόλις οκτώ λεπτά σε έναν κανονικό φορητό υπολογιστή. Αλλά, αυτό που διαρκεί οκτώ λεπτά για το D(8) γίνεται εκατοντάδες χιλιάδες χρόνια για το D(9). "Ακόμα και αν χρησιμοποιούσατε έναν μεγάλο υπερυπολογιστή αποκλειστικά για αυτό το έργο, θα χρειαζόταν πολλά χρόνια για να ολοκληρωθεί ο υπολογισμός", επισημαίνει ο Van Hirtum.
Το κύριο πρόβλημα είναι ότι ο αριθμός των όρων σε αυτόν τον τύπο αυξάνεται απίστευτα γρήγορα. «Στην περίπτωσή μας, εκμεταλλευόμενοι τις συμμετρίες στον τύπο, καταφέραμε να μειώσουμε τον αριθμό των όρων σε "μόνο" $5.5 \cdot 10^{18}$. Συγκριτικά, ο αριθμός των κόκκων άμμου στη Γη είναι περίπου $ 7.5 \cdot 10^{18}$, αλλά για έναν σύγχρονο υπερυπολογιστή, $5.5 \cdot 10^{18}$ πράξεις είναι διαχειρίσιμες».
Το πρόβλημα: Ο υπολογισμός αυτών των όρων σε κανονικούς επεξεργαστές είναι αργός και ακόμα και η χρήση των GPUs, που είναι σήμερα η ταχύτερη τεχνολογία επιτάχυνσης υλικού για πολλές εφαρμογές τεχνητής νοημοσύνης, δεν είναι αποτελεσματική για αυτόν τον αλγόριθμο.
Η λύση: Υλικό ειδικά σχεδιασμένο για τη συγκεκριμένη εφαρμογή που χρησιμοποιεί εξειδικευμένες και παράλληλες αριθμητικές μονάδες, τις λεγόμενες FPGA (field programmable gate arrays). Ο Van Hirtum ανέπτυξε ένα αρχικό πρωτότυπο για τον επιταχυντή υλικού και άρχισε να αναζητά έναν υπερυπολογιστή που διέθετε τις απαραίτητες κάρτες FPGA. Αυτό ήταν ο Noctua 2 στο "Paderborn Center for Parallel Computing (PC2)" του Πανεπιστημίου του Paderborn, ο οποίος διαθέτει ένα από τα ισχυρότερα συστήματα FPGA στον κόσμο. Μετά από αρκετά χρόνια ανάπτυξης, το πρόγραμμα έτρεξε στον υπερυπολογιστή για περίπου πέντε μήνες. Και επιτέλους ήρθε η ώρα. Στις 8 Μαρτίου, το πρόγραμμα υπολόγισε τον 9ο αριθμό Dedekind, ο οποίος είναι ο
$286386577668298411128469151667598498812366$