Donald Knuth est un informaticien qui se soucie tellement de l'exactitude de ses livres qu'il offre un dollar hexadécimal (2,56 $, 0x 1,00 $) pour toute "erreur" trouvée, où tout ce qui est "techniquement, historiquement, typographiquement, est considéré comme une erreur." ou politiquement mal. " Je voulais vraiment obtenir un chèque de Knut, alors j'ai décidé de chercher des erreurs dans son travail exceptionnel "The Art of Programming" (TAOCP). J'ai réussi à en trouver trois. Fidèle au mot, Knut a envoyé un chèque de 0x $ 3,00 .



Comme vous pouvez le voir, ce n'est pas un vrai chèque. Knut envoyait de vrais chèques, mais a cessé en 2008 en raison d' une fraude généralisée . Maintenant, il envoie des «certificats de dépôt personnels» à la Banque de San Serriff (BoSS). Il dit qu'il est prêt à envoyer de l'argent réel si nécessaire, mais cela semble trop gênant.

J'ai trouvé deux fautes de frappe et une erreur historique. Je vais les énumérer par ordre décroissant de trivialité.

Typo numéro 1

La première faute de frappe se trouve à la page 392 du troisième volume «Tri et recherche», la huitième ligne à partir du bas: «Après une recherche infructueuse, il est parfois (parfois) conseillé de saisir un nouvel enregistrement dans le tableau contenant K ; la méthode qui fait cela s'appelle un algorithme de recherche et d'insertion. L'erreur est qu'au lieu de parfois devrait être parfois .

Bien sûr, une telle erreur n'est pas surprenante. Seulement dans cet article, il y aura certainement quelques fautes de frappe (pas de récompense pour les trouver). Ce qui est vraiment surprenant, c'est que cela n'a pas été remarqué depuis si longtemps. La page 392 n'est pas enfouie au fond de la section avec les mathématiques, c'est la toute première page du sixième chapitre de «Recherche»! Peut-être l'une des sections les plus lues du livre. En théorie, il devrait y avoir le moins de fautes de frappe, mais non.

Au fait, si vous avez déjà pensé à lire TAOCP, essayez-le. Beaucoup diront que ce guide n'est pas destiné à la lecture directe, mais ce n'est pas vrai. L'auteur a un point de vue clair et un style particulier. La seule chose qui empêche la lisibilité est la complexité des mathématiques. Cependant, il existe une solution simple: lisez jusqu'à ce que vous arriviez aux mathématiques que vous ne comprenez pas, sautez-la et ouvrez la section suivante que vous pouvez comprendre. En lisant de cette façon, je manque au moins 80% du livre, mais les 20% restants sont super!

Ils disent également que TAOCP est hors de propos , obsolète ou autrement inapplicable à la «vraie programmation». Ce n'est pas vrai non plus. Par exemple, dans la première section après l'introduction, la recherche d'un élément dans un tableau non trié est considérée. L'algorithme le plus simple est familier à tous les programmeurs. Exécutez le pointeur au début du tableau, puis procédez comme suit en boucle:

1. Vérifiez si l'élément actuel est souhaité. Si oui, renvoyez-le; sinon
   
2. Vérifiez si le pointeur est en dehors du tableau. Si oui, retournez une erreur; sinon
   
3. Augmentez le pointeur et continuez.

Considérez maintenant: combien de contrôles aux frontières cet algorithme nécessite-t-il en moyenne? Dans le pire des cas, lorsque le tableau ne contient pas d'élément, pour chaque élément de la liste, une vérification est requise, et en moyenne ce sera quelque chose comme $$$N / 2$. Un algorithme de recherche plus intelligent peut faire avec une seule vérification des frontières. Attachez l'élément souhaité à la fin du tableau, puis exécutez le pointeur au début du tableau et suivez ces étapes en boucle:

1. Vérifiez si l'élément actuel est souhaité. Si c'est le cas, nous retournons la réponse si le pointeur se trouve dans le tableau, ou une erreur s'il ne l'est pas. Sinon
   
2. Augmentez le pointeur et continuez.

D'une manière ou d'une autre, l'élément est garanti d'être trouvé et la vérification des frontières n'est effectuée qu'une seule fois, lorsque cela s'est produit. C'est une idée profonde, mais elle est assez simple même pour un programmeur débutant. Je ne peux probablement pas parler de la pertinence du travail pour les autres, mais j'ai immédiatement pu appliquer cette sagesse dans le code personnel et professionnel. Le livre TAOCP est plein de telles perles (en toute honnêteté, il y a beaucoup de choses étranges, comme le tri des bulles ).

"Recherche, recherche
Si longtemps
Recherche, recherche
Je voulais juste danser. "
- Luther Wandross, Recherche (1980)

Typo numéro 2

La deuxième faute de frappe se trouve dans le volume 4A, Algorithmes combinatoires, partie 1. À la page 60, nous décrivons la tâche de planifier les performances des comédiens dans divers casinos. Certains vrais comédiens sont cités en exemple, notamment Lily Tomlin, Strange Al Jankovic et Robin Williams, qui était encore en vie lorsque le livre est sorti. Whip donne toujours des noms complets dans l'index , donc Williams est appelé à la page 882 «Williams, Robin McLorim». Mais son deuxième prénom se termine par "n", et non par "m", c'est-à-dire McLoreen.

McLorin est le nom de jeune fille de sa mère. Elle était l'arrière-petite-fille d'Anselm Joseph McLorin, 34e gouverneur du Mississippi. Sa règle, apparemment, ne se souvenait de rien de bon. Extrait du livre Mississippi: Histoire :

«L'événement le plus important sous l'administration McLorin a été la déclaration de guerre d'Espagne par les États-Unis au printemps 1898 ... Malheureusement, la guerre a peut-être permis à certains responsables gouvernementaux de pratiquer la corruption. McLorin a été accusé de diverses pratiques douteuses, y compris le népotisme et l'utilisation excessive des pouvoirs de grâce. À l'ère de la sobriété, les critiques ont accusé le gouverneur de l'ivresse, ce qu'il a publiquement admis. »

Erreur historique

Considérez l' algorithme de multiplication traditionnel du programme scolaire. Combien cela nécessite-t-il des opérations de multiplication sur un bit? Supposons que vous vous multipliez $$$m$- numéro de bit $$$x$sur $$$n$-bit $$$y$. Tout d'abord, multipliez le premier chiffre $$$x$pour chaque chiffre $$$y$à tour de rôle. Multipliez ensuite le deuxième chiffre $$$x$pour chaque chiffre $$$y$à tour de rôle et ainsi de suite jusqu'à ce que vous passiez par tous les chiffres $$$x$. Ainsi, la multiplication traditionnelle nécessite $$$mn$multiplications primitives. En particulier, la multiplication de deux nombres par $$$n$les rejets nécessitent $$$n ^ 2$multiplications sur un seul bit.

C'est mauvais, mais vous pouvez optimiser le processus en utilisant la méthode développée par le mathématicien soviétique Anatoly Alekseevich Karatsuba. Supposons que $$$x$et $$$y$- nombres décimaux à deux chiffres; c'est-à-dire qu'il y a des nombres $$$a$, $$$b$, $$$c$, $$$d$tel que $$$x = (ab) _ {10}$et $$$y = (cd) _ {10}$(la généralisation de cet algorithme aux grands nombres nécessite certaines manipulations; bien que ce ne soit pas trop difficile, mais pour ne pas se tromper dans les détails, je préfère m'en tenir à un exemple simple). Alors $$$x = 10a + b$, $$$y = 10c + d$, $$$xy = (10a + b) (10c + d)$. La multiplication des binômes donne $$$xy = 100ac + 10ad + 10bc + bd$. Pour le moment, nous $$$n ^ 2 = 4$multiplication sur un seul bit: $$$ac$, $$$ad$, $$$bc$, $$$bd$. Maintenant, ajoutez et soustrayez $$ . Après quelques permutations, que je laisserai en exercice au lecteur, il s'avère $$$xy = 110ac + 11bd + 10 (a - b) (d - c)$- seulement trois multiplications à un chiffre! (Il existe des coefficients constants, mais ils ne peuvent être calculés qu'en ajoutant et en décalant les chiffres).

Ne demandez pas de preuve, mais l'algorithme de Karatsuba (généralisé récursivement à partir de l'exemple ci-dessus) améliore la méthode traditionnelle de multiplication avec $$$O (n ^ 2)$opérations avant $$$O (n ^ {(lg 3)})$. Veuillez noter qu'il s'agit d'une réelle amélioration de l'algorithme, pas d'une optimisation pour les calculs mentaux. En effet, l'algorithme n'est pas adapté au calcul dans l'esprit, car il nécessite une surcharge importante pour les opérations récursives. De plus, l'effet ne sera pleinement apparent que lorsque les chiffres deviendront suffisamment importants (heureusement, au lieu de l'algorithme de Karatsuba, des méthodes encore plus rapides sont arrivées: en mars 2019, un algorithme a été publié qui ne nécessitait que n log n multiplications; l'accélération ne s'applique qu'à des incroyablement grands chiffres).

Cet algorithme est décrit à la page 295 du deuxième volume, Algorithms Derived. Là, Knuth écrit: «Il est curieux que cette idée n'ait été découverte qu'en 1962 » lorsqu'un article a été publié décrivant l'algorithme de Karatsuba. Mais! En 1995, Karatsuba a publié un article, «Complexity of Computing», qui dit plusieurs choses: 1) vers 1956, Kolmogorov a suggéré que la multiplication ne peut pas se faire en moins de $$$O (n ^ 2)$étapes; 2) en 1960 , Karatsuba a assisté à un séminaire où Kolmogorov a présenté son hypothèse n². 3) «Exactement en une semaine» Karatsuba a développé l'algorithme «diviser pour mieux régner»; 4) en 1962, Kolmogorov a écrit et publié un article au nom de Karatsuba avec une description de l'algorithme. "Je n'ai découvert cet article qu'après sa réimpression."

Ainsi, l'erreur est que 1960 devrait être indiqué au lieu de 1962 . C’est tout.

Analyse

La recherche d'erreurs n'a pas exigé beaucoup de compétence.

1. La première erreur était aussi banale que possible et se trouvait dans une place relativement importante (le début du chapitre). N'importe quel idiot la trouverait; Je me suis juste avéré être cet idiot.
   
2. Trouver une deuxième faute de frappe exigeait de la chance et de la diligence, mais pas des compétences. L'index de "Williams" se trouve sur l'avant-dernière page du volume, une partie assez importante du livre. Je parcourais juste l'index (ce n'est pas aussi pathétique qu'il n'y paraît car les œufs de Pâques sont cachés dans les index de Knuth. Par exemple, il y a des entrées en arabe et en hébreu, et toutes deux pointent vers la page 66. Mais cette page ne mentionne pas non plus langues, au lieu de cela, il s'agit de «langues qui se lisent de droite à gauche»). Et mon attention a été attirée par le deuxième prénom. Depuis que je lis habituellement Wikipédia, j'ai vérifié Robin Williams et j'ai remarqué une divergence.
   
3. Je voudrais dire que j'ai mené une étude sérieuse pour trouver une erreur historique, mais en fait je viens de regarder la page Wikipedia sur l'algorithme de Karatsuba . Les toutes premières lignes disent: «L'algorithme de Karatsuba est un algorithme de multiplication rapide. Découvert par Anatoly Karatsuba en 1960 et publié en 1962. " Après cela, il ne restait plus qu'à plier deux fois.

À l'avenir, je voudrais trouver une erreur plus significative, en particulier dans le code de Knuth. J'aimerais aussi trouver un bug dans le premier volume, Fundamental Algorithms. Je l'aurais peut-être trouvé, mais pour une raison quelconque, il n'y a que les volumes 2, 3 et 4A dans la bibliothèque locale.

Faits financiers:

• Au total, ma contribution à TAOCP ne comprend que trois caractères: un ajoutant s , remplaçant m par n et 2 par 0 . Au prix de 2,56 $, ce sont des symboles assez lucratifs; si on vous payait ce genre d'argent, alors un article de 1000 mots (en moyenne, quatre caractères chacun) vous rapporterait dix pièces.
  
• Avec trois dollars hexadécimaux, je partage, avec 29 autres citoyens, la 69e place dans la liste des déposants les plus riches de la Banque de San Serriff (au 1er mai 2019).

Autres discussions sur les contrôles Knut

• Comment obtenir un chèque de Knut
  
  Lignes directrices générales pour trouver des bogues dans les livres de Knut. Surtout des erreurs techniques que je n'ai pas. Il y a une suggestion que j'ai prise au sérieux:
  
  

  Il est préférable d'attendre d'avoir collecté un ensemble d'erreurs à envoyer. En combinant plusieurs erreurs réelles mais pas très précieuses, vous augmenterez la probabilité que l'une d'elles soit réellement considérée comme une erreur ou un conseil. Si vous envoyez des erreurs une par une, chacune peut être rejetée individuellement.

  
  Je ne voulais pas envoyer de fautes de sens, mais j'ai obéi aux conseils et envoyé une lettre uniquement lorsque j'ai trouvé une erreur historique qui semblait suffisamment grave.
  
• Les chèques d'Ashutosh Mehra
  
  Ashutosh Mehra est le troisième contributeur le plus riche de San Serriff avec une énorme fortune de 0x $ 207, f0 en BoSS.
  
• Recherchez des erreurs non fonctionnelles dans le vrai code TeX
  
• Divers: # 1 # 2 # 3 # 4 # 5 # 6