Επισκόπηση
Υπολογισμός της σταθεράς Euler e σε όσο το δυνατόν περισσότερα ψηφία, όσο το δυνατόν γρηγορότερα. Έντεκα εξελισσόμενες υλοποιήσεις τεκμηριώνουν ένα μακρύ ταξίδι επιδόσεων: από μια αφελή βάση σε πλήρως παράλληλη μηχανή GMP.
Τι έφτιαξα
Τα μαθηματικά: το e είναι άθροισμα αντίστροφων παραγοντικών, υπολογιζόμενο με ακέραιους αυθαίρετης ακρίβειας GMP ώστε να χρειάζονται μόνο πολλαπλασιασμοί/προσθέσεις. Ο αλγόριθμος: binary splitting — διαίρει και βασίλευε στο παραγοντικό γινόμενο (Q_F(a,b)) που σπάει τη σειρά σε παραλληλοποιήσιμα κομμάτια, με μήκη διαχωρισμού ρυθμισμένα μεταξύ 2^15 και 2^18.
Ο παραλληλισμός εξελίχθηκε μέσα από τέσσερα σχέδια — πολυνηματικό, ημι-πολυνηματικό, SM+ (v9) και πλήρες πολυνηματικό (v10+): αρχιτεκτονική ουρών εργασιών (numQueue, bsfQueue, resQueue) με δυναμικά ρυθμισμένο αριθμό νημάτων, πάνω από αναμεταγλωττισμένο GCC με βελτιστοποιημένο GMP για τη μηχανή.
Η επαλήθευση δεν είναι εκ των υστέρων σκέψη: ένας ελεγκτής ψηφίων σε JavaScript συγκρίνει την έξοδο με τα ψηφία αναφοράς από το numberworld.org, και στην πορεία διερευνήθηκε και ένα πειραματικό JS FFT module (TypeScript + Jest).
Τεχνικά highlights
- Binary splitting με ρυθμισμένα μεγέθη κομματιών για σχεδόν γραμμική κλιμάκωση
- Προοδευτικός πολυνηματισμός μέσα από τέσσερα σχέδια, καταλήγοντας σε ουρές εργασιών
- Τιμημένα, εκδόσιμα benchmarks: 1 εκατ. ψηφία σε 484 ms, 10 εκατ. σε 6 δευτ., 100 εκατ. σε 3 λεπτά 20 δευτ. — 1 δισεκατομμύριο σε ~168 λεπτά σε laptop Ryzen 3500U
Αποτέλεσμα
Ένα δισεκατομμύριο ψηφία του e, υπολογισμένα σε φορητό υπολογιστή, με ολόκληρο το μονοπάτι μηχανικής δεσμευμένο στο αποθετήριο.