Ντόναλντ Κνουθ είναι ένας επιστήμονας υπολογιστών που ενδιαφέρεται τόσο πολύ για την ακρίβεια των βιβλίων του που προτείνει ένα εξάγωνο δολάριο (2,56 $, 0x1,00 $) για οποιοδήποτε "σφάλμα" που βρέθηκε, όπου ως σφάλμα ορίζεται οτιδήποτε είναι "τεχνικά, ιστορικά, τυπογραφικά ή πολιτικά εσφαλμένο". Ήθελα πολύ να πάρω μια επιταγή από τον Knuth, οπότε αποφάσισα να ψάξω για σφάλματα στο magnum opus του «Η Τέχνη του Προγραμματισμού» (TAOCP). Καταφέραμε να βρούμε τρεις. Πιστός στο λόγο του, ο Knut έστειλε μια επιταγή για 0x3,00$.

Όπως μπορείτε να δείτε, δεν πρόκειται για πραγματικό έλεγχο. Ο Knuth συνήθιζε να στέλνει πραγματικές επιταγές, αλλά σταμάτησε το 2008 λόγω αχαλίνωτη απάτη. Τώρα στέλνει «προσωπικά πιστοποιητικά κατάθεσης» σε Bank of San Serriff (Αφεντικό). Λέει ότι είναι πρόθυμος να στείλει πραγματικά χρήματα αν χρειαστεί, αλλά φαίνεται ότι είναι πολύ ταλαιπωρία.

Βρήκα δύο τυπογραφικά και ένα ιστορικό λάθος. Θα τα απαριθμήσω κατά σειρά φθίνουσας επιπολαιότητας.

Τυπογραφικό λάθος #1

Το πρώτο τυπογραφικό λάθος βρίσκεται στη σελίδα 392 του τρίτου τόμου του «Ταξινόμηση και Αναζήτηση», όγδοη γραμμή από κάτω: «Μετά από μια ανεπιτυχή αναζήτηση, μερικές φορές (μερικές φορές) είναι επιθυμητό να εισάγετε μια νέα εγγραφή στον πίνακα που περιέχει K; η μέθοδος που το κάνει αυτό ονομάζεται αλγόριθμος αναζήτησης και εισαγωγής. Το λάθος είναι ότι αντί κάποια στιγμή πρέπει να είναι μερικές φορές.

Φυσικά, ένα τέτοιο λάθος δεν προκαλεί έκπληξη. Είναι βέβαιο ότι θα υπάρχουν μερικά τυπογραφικά λάθη μόνο σε αυτό το άρθρο (δεν υπάρχει ανταμοιβή για την εύρεση τους). Αυτό που πραγματικά προκαλεί έκπληξη είναι ότι πέρασε απαρατήρητο για τόσο καιρό. Η σελίδα 392 δεν είναι θαμμένη βαθιά στο τμήμα των μαθηματικών, είναι την πρώτη κιόλας σελίδα Κεφάλαιο XNUMX «Αναζήτηση»! Ίσως ένα από τα πιο διαβασμένα τμήματα του βιβλίου. Θεωρητικά, θα έπρεπε να υπάρχουν τα λιγότερα τυπογραφικά λάθη, αλλά όχι.

Παρεμπιπτόντως, αν έχετε σκεφτεί ποτέ να διαβάσετε το TAOCP, δοκιμάστε το. Πολλοί θα πουν ότι αυτό είναι καταλόγου, δεν προορίζεται για άμεση ανάγνωση, αλλά αυτό δεν είναι αλήθεια. Ο συγγραφέας έχει ξεκάθαρη άποψη και ξεχωριστό ύφος. Το μόνο πράγμα που εμποδίζει την αναγνωσιμότητα είναι η πολυπλοκότητα των μαθηματικών. Ωστόσο, υπάρχει μια απλή λύση: διαβάστε μέχρι να καταλήξετε στα μαθηματικά που δεν καταλαβαίνετε, παραλείψτε τα και μεταβείτε στην επόμενη ενότητα που μπορείτε να καταλάβετε. Διαβάζοντας έτσι, μου λείπει τουλάχιστον το 80% του βιβλίου, αλλά το άλλο 20% είναι υπέροχο!

Λέγεται επίσης ότι το TAOCP άσχετος, είναι ξεπερασμένο ή με άλλο τρόπο δεν ισχύει για "πραγματικό προγραμματισμό". Αυτό επίσης δεν είναι αλήθεια. Για παράδειγμα, η πρώτη ενότητα μετά την εισαγωγή εξετάζει την εύρεση ενός στοιχείου σε έναν μη ταξινομημένο πίνακα. Ο απλούστερος αλγόριθμος είναι γνωστός σε όλους τους προγραμματιστές. Ξεκινήστε τον δείκτη στην αρχή του πίνακα και, στη συνέχεια, κάντε τα εξής σε βρόχο:

1. Ελέγξτε εάν το τρέχον στοιχείο είναι το επιθυμητό. Αν ναι, το επιστρέφουμε. σε διαφορετική περίπτωση
2. Ελέγξτε εάν ο δείκτης βρίσκεται εκτός των ορίων του πίνακα. Εάν ναι, επιστρέψτε ένα σφάλμα. σε διαφορετική περίπτωση
3. Κάντε μεγέθυνση και συνεχίστε.

Τώρα σκεφτείτε: πόσους ελέγχους ορίων απαιτεί, κατά μέσο όρο, αυτός ο αλγόριθμος; Στη χειρότερη περίπτωση, όπου ο πίνακας δεν περιέχει ένα στοιχείο, κάθε στοιχείο στη λίστα θα απαιτεί έναν έλεγχο και κατά μέσο όρο θα είναι κάτι σαν . Ένας πιο έξυπνος αλγόριθμος αναζήτησης θα μπορούσε να ξεφύγει με έναν μόνο έλεγχο ορίων. Συνδέστε το επιθυμητό στοιχείο στο τέλος του πίνακα, ξεκινήστε τον δείκτη στην αρχή του πίνακα και κάντε τα εξής σε βρόχο:

1. Ελέγξτε εάν το τρέχον στοιχείο είναι το επιθυμητό. Εάν ναι, επιστρέφουμε μια απάντηση εάν ο δείκτης βρίσκεται εντός του πίνακα ή ένα σφάλμα εάν δεν είναι. Σε διαφορετική περίπτωση
2. Κάντε μεγέθυνση και συνεχίστε.

Με τον ένα ή τον άλλο τρόπο, το στοιχείο είναι εγγυημένο ότι θα βρεθεί και ο έλεγχος ορίων εκτελείται μόνο μία φορά όταν συμβεί αυτό. Αυτή είναι μια βαθιά ιδέα, αλλά είναι αρκετά απλή ακόμα και για έναν αρχάριο προγραμματιστή. Μάλλον δεν μπορώ να μιλήσω για τη συνάφεια της δουλειάς με άλλους, αλλά μπόρεσα αμέσως να εφαρμόσω αυτή τη σοφία τόσο στον προσωπικό όσο και στον επαγγελματικό κώδικα. Το βιβλίο TAOCP είναι γεμάτο από τέτοια πετράδια (για να είμαστε δίκαιοι, υπάρχουν και πολλά περίεργα πράγματα εκεί μέσα, όπως π.χ. είδος φούσκας).

«Αναζήτηση, αναζήτηση
Τόσο καιρό
Αναζήτηση, αναζήτηση
Ήθελα απλώς να χορέψω"
— Luther Vandross, «The Search» (1980)

Τυπογραφικό λάθος #2

Το δεύτερο τυπογραφικό λάθος βρίσκεται στον τόμο 4Α, ​​Συνδυαστικοί Αλγόριθμοι, Μέρος 1. Σελίδα 60 περιγράφει ένα πρόβλημα που αφορά τον προγραμματισμό κωμικών για να παίξουν σε διάφορα καζίνο. Αρκετοί κωμικοί της πραγματικής ζωής αναφέρονται ως παραδείγματα, συμπεριλαμβανομένων των Lily Tomlin, Weird Al Yankovic και Robin Williams, ο οποίος ήταν ακόμη ζωντανός όταν κυκλοφόρησε το βιβλίο. Ο Knuth αναφέρει πάντα τα πλήρη ονόματα στο ευρετήριο, επομένως ο Williams αναφέρεται στη σελίδα 882 ως "Williams, Robin McLorim". Αλλά το μεσαίο όνομά του τελειώνει με «n» και όχι με «m», δηλαδή McLaurin.

McLaurin ήταν το πατρικό όνομα της μητέρας του. Ήταν η δισέγγονη του Anselm Joseph McLaurin, 34ου Κυβερνήτη του Μισισιπή. Η βασιλεία του, προφανώς, δεν μνημονεύτηκε για τίποτα καλό. Από βιβλίο "Μισισίπι: Ιστορία":

«Το πιο σημαντικό γεγονός κατά τη διάρκεια της διακυβέρνησης McLaurin ήταν η κήρυξη του πολέμου των Ηνωμένων Πολιτειών στην Ισπανία την άνοιξη του 1898... Δυστυχώς, ο πόλεμος μπορεί να έδωσε σε ορισμένους κυβερνητικούς αξιωματούχους την ευκαιρία να εμπλακούν σε δωροδοκία. Ο McLaurin κατηγορήθηκε για διάφορες αμφισβητήσιμες πρακτικές, συμπεριλαμβανομένου του νεποτισμού και της υπερβολικής χρήσης εξουσιών χάρης. Κατά τη διάρκεια του κινήματος της εγκράτειας, οι επικριτές κατηγόρησαν τον κυβερνήτη ότι ήταν μέθυσος, κάτι που παραδέχτηκε δημόσια».

Ιστορικό λάθος

Εξετάστε παραδοσιακός αλγόριθμος πολλαπλασιασμού από το σχολικό πρόγραμμα. Πόσους μονοψήφιους πολλαπλασιασμούς απαιτεί; Ας υποθέσουμε ότι πολλαπλασιάζετε -ψήφιος αριθμός επί -κομμάτι . Πρώτα πολλαπλασιάστε το πρώτο ψηφίο για κάθε ψηφίο ένα ένα. Στη συνέχεια πολλαπλασιάστε το δεύτερο ψηφίο για κάθε ψηφίο ένα προς ένα και ούτω καθεξής μέχρι να περάσετε από όλους τους αριθμούς . Επομένως, ο παραδοσιακός πολλαπλασιασμός απαιτεί πρωτόγονους πολλαπλασιασμούς. Συγκεκριμένα, πολλαπλασιάζοντας δύο αριθμούς με απαιτούνται βαθμοί μονοψήφιοι πολλαπλασιασμοί.

Αυτό είναι κακό, αλλά είναι δυνατό να βελτιστοποιηθεί η διαδικασία χρησιμοποιώντας μια μέθοδο που αναπτύχθηκε από τον Σοβιετικό μαθηματικό Anatoly Alekseevich Karatsuba. Ας το προσποιηθούμε и  - διψήφιοι δεκαδικοί αριθμοί. δηλαδή υπάρχουν αριθμοί , , , τέτοια που и (Η γενίκευση αυτού του αλγορίθμου σε μεγαλύτερους αριθμούς απαιτεί κάποιους χειρισμούς· αν και δεν είναι πολύ δύσκολο, για να μην κάνουμε λάθη στις λεπτομέρειες, θα μείνω καλύτερα σε ένα απλό παράδειγμα). Επειτα , , . Ο πολλαπλασιασμός των διωνύμων δίνει . Αυτή τη στιγμή έχουμε ακόμα μονοψήφιος πολλαπλασιασμός: , , , . Τώρα ας προσθέσουμε και να αφαιρέσουμε . Μετά από μερικές ανακατατάξεις, τις οποίες θα αφήσω ως άσκηση για τον αναγνώστη, αποδεικνύεται  - μόνο τρεις μονοψήφιοι πολλαπλασιασμοί! (Υπάρχουν ορισμένοι σταθεροί συντελεστές, αλλά μπορούν να υπολογιστούν μόνο με την προσθήκη και τη μετατόπιση των ψηφίων).

Μη ζητάς αποδείξεις, αλλά Αλγόριθμος Karatsuba (αναδρομικά γενικευμένη από το παραπάνω παράδειγμα) βελτιώνει την παραδοσιακή μέθοδο πολλαπλασιασμού με επιχειρήσεις πριν . Λάβετε υπόψη ότι αυτή είναι μια πραγματική βελτίωση του αλγόριθμου, όχι μια βελτιστοποίηση για νοητικούς υπολογισμούς. Πράγματι, ο αλγόριθμος δεν είναι κατάλληλος για νοητική αριθμητική, καθώς απαιτεί μεγάλα γενικά έξοδα για αναδρομικές πράξεις. Επιπλέον, το αποτέλεσμα δεν θα εκδηλωθεί πλήρως έως ότου οι αριθμοί γίνουν αρκετά μεγάλοι (ευτυχώς, ο αλγόριθμος του Karatsuba έχει αντικατασταθεί από ακόμη πιο γρήγορες μεθόδους: τον Μάρτιο του 2019 δημοσιεύθηκε ένας αλγόριθμος που απαιτεί μόνο n log n πολλαπλασιασμοί? η επιτάχυνση ισχύει μόνο για αφάνταστα μεγάλους αριθμούς).

Αυτός ο αλγόριθμος περιγράφεται στη σελίδα 295 του Τόμου XNUMX, Ημι-Αριθμητικοί Αλγόριθμοι. Εκεί ο Knuth γράφει: «Είναι περίεργο ότι αυτή η ιδέα ανακαλύφθηκε μόνο στο 1962 έτος», όταν δημοσιεύτηκε ένα άρθρο που περιγράφει τον αλγόριθμο του Karatsuba. Αλλά! Το 1995, ο Karatsuba δημοσίευσε μια εργασία "Υπολογιστική πολυπλοκότητα", η οποία λέει πολλά πράγματα: 1) γύρω στο 1956, ο Kolmogorov πρότεινε ότι ο πολλαπλασιασμός δεν μπορεί να γίνει σε λιγότερο από βήματα? 2) σε 1960 έτος ο Karatsuba παρακολούθησε το σεμινάριο όπου ο Kolmogorov παρουσίασε την υπόθεσή του n². 3) «Σε μία ακριβώς εβδομάδα», ο Karatsuba ανέπτυξε τον αλγόριθμο «διαίρει και βασίλευε». 4) το 1962 ο Κολμογκόροφ έγραψε και δημοσίευσε ένα άρθρο για λογαριασμό της Καρατσούμπα με περιγραφή του αλγορίθμου. "Έμαθα για αυτό το άρθρο μόνο μετά την αναδημοσίευσή του."

Άρα το λάθος είναι ότι αντί για 1962 πρέπει να διευκρινιστεί 1960 έτος. Αυτό είναι όλο.

Ανάλυση

Η εύρεση σφαλμάτων δεν απαιτούσε ιδιαίτερη δεξιότητα.

1. Το πρώτο λάθος ήταν όσο το δυνατόν πιο ασήμαντο και βρισκόταν σε σχετικά εμφανές σημείο (αρχή του κεφαλαίου). Κάθε ηλίθιος θα το είχε βρει. Απλώς αποδείχτηκε ότι ήμουν αυτός ο ηλίθιος.
2. Η εύρεση του δεύτερου τυπογραφικού λάθους απαιτούσε τύχη και επιμέλεια, αλλά όχι επιδεξιότητα. Το ευρετήριο για το «Williams» βρίσκεται στην προτελευταία σελίδα του τόμου, ένα αρκετά εμφανές μέρος του βιβλίου. Απλώς ξεφύλλιζα το ευρετήριο (δεν είναι τόσο αξιολύπητο όσο ακούγεται, επειδή υπάρχουν πασχαλινά αυγά κρυμμένα στα ευρετήρια του Knuth. Για παράδειγμα, υπάρχουν καταχωρήσεις στα αραβικά και τα εβραϊκά, και τα δύο δείχνουν προς τη σελίδα 66. Αλλά αυτή η σελίδα δεν αναφέρει οποιαδήποτε γλώσσα· αντίθετα αναφέρεται σε «γλώσσες που διαβάζονται από τα δεξιά προς τα αριστερά»). Και το δεύτερο όνομα τράβηξε την προσοχή μου. Επειδή συνήθως διαβάζω τη Wikipedia, τσέκαρα τον Robin Williams και παρατήρησα μια ασυμφωνία.
3. Θα ήθελα να μπορούσα να πω ότι έκανα σοβαρή έρευνα για να βρω ένα ιστορικό λάθος, αλλά στην πραγματικότητα απλώς έψαξα Σελίδα Wikipedia σχετικά με τον αλγόριθμο του Karatsuba. Οι πρώτες γραμμές λένε: «Ο αλγόριθμος Karatsuba είναι ένας αλγόριθμος γρήγορου πολλαπλασιασμού. Ανακαλύφθηκε από τον Anatoly Karatsuba το 1960 και δημοσιεύτηκε το 1962. Μετά από αυτό το μόνο που έμεινε ήταν να προσθέσουμε δύο και δύο.

Στο μέλλον θα ήθελα να βρω ένα πιο σημαντικό σφάλμα, ειδικά στον κώδικα του Knuth. Θα ήθελα επίσης να βρω ένα σφάλμα στον πρώτο τόμο των Θεμελιωδών Αλγορίθμων. Ίσως θα το είχα βρει, αλλά για κάποιο λόγο η τοπική βιβλιοθήκη έχει μόνο τους τόμους 2, 3 και 4Α.

Οικονομικά στοιχεία:

• Συνολικά, η συνεισφορά μου στο TAOCP αποτελείται μόνο από τρεις χαρακτήρες: μία προσθήκη s, αντικατάσταση m επί n и 2 επί 0. Στα 2,56 $, αυτά είναι μερικά αρκετά προσοδοφόρα σύμβολα. Εάν πληρώνεστε με τέτοια χρήματα, ένα άρθρο 1000 λέξεων (κατά μέσο όρο τεσσάρων χαρακτήρων) θα σας κέρδιζε δέκα ευρώ.
• Με τρία δεκαεξαδικά δολάρια, εγώ, μαζί με άλλους 29 πολίτες, ισοβαθμούμε στην 69η θέση στη λίστα με τους πλουσιότερους καταθέτες της San Serriff Bank (από την 1η Μαΐου 2019).

Άλλες συζητήσεις για επιταγές από τον Knuth

• Πώς να πάρετε μια επιταγή από τον Knuth

  Γενικές συστάσεις για την εύρεση σφαλμάτων στα βιβλία του Knuth. Κυρίως αφορούν τεχνικά λάθη, τα οποία δεν έχω. Υπάρχει μια πρόταση εκεί που πήρα στα σοβαρά:

  Είναι καλύτερο να περιμένετε μέχρι να συλλέξετε ένα σύνολο σφαλμάτων για υποβολή. Συνδυάζοντας πολλά πραγματικά αλλά όχι πολύ σημαντικά λάθη, αυξάνετε την πιθανότητα ένα από αυτά να θεωρηθεί πραγματικά ως λάθος ή συμβουλή. Εάν υποβάλετε σφάλματα ένα κάθε φορά, το καθένα ξεχωριστά μπορεί να απορριφθεί.

  Δεν ήθελα να στείλω απλώς ανόητα τυπογραφικά λάθη, αλλά έλαβα τη συμβουλή και έστειλα την επιστολή μόνο όταν βρήκα ένα ιστορικό λάθος που φαινόταν αρκετά σοβαρό.

• Οι επιταγές του Ashutosh Mehra

  Ο Ashutosh Mehra είναι ο τρίτος πλουσιότερος επενδυτής στο San Serriff με τεράστια καθαρή αξία 0x207,f0 $ στο BoSS.

• Ελέγξτε για ορισμένα μη λειτουργικά σφάλματα στον πραγματικό κώδικα TeX
• Διάφορα: #1 #2 #3 #4 #5 #6

Πηγή: www.habr.com