Jahrzehntelanger Bug in Knuths Langdivision entdeckt
A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
Beim Implementieren von Algorithmus D aus Knuths "The Art of Computer Programming" stieß der Autor auf einen subtilen Fehler im Beweis von Theorem B, der sich als echter Bug im Algorithmus entpuppte. Jahrzehntelang galt der Algorithmus als korrekt, doch ein Gegenbeispiel zeigt das Gegenteil. Der Beitrag erklärt die Langdivision von Grund auf, analysiert die Ursache des Bugs und warum er so lange unentdeckt blieb, und wirft einen Blick auf moderne Implementierungen. Zudem wird ein vermeintlicher Bug in der LLVM-Implementierung des Algorithmus diskutiert.
Der Beweis fühlte sich unnatürlich an, er nahm einen sehr verschlungenen Weg, um eine einfache Aussage zu beweisen, und isolierte einen Spezialfall, der kein Randfall war und mit dem Problem nichts zu tun zu haben schien.
- nk_kolja
Ich habe einen Bug in Algorithmus D gefunden, dem Langdivisionsalgorithmus in Knuths "The Art of Computer Programming". Er wurde auf HN ein paar Mal diskutiert https://news.ycombinator.com/item?id=26562819 sowie auf anderen Websites.
Ich habe einen Brief an Knuth geschickt und einen Scheck und eine kommentierte Antwort erhalten. Der aktualisierte Satz B, der seit 1969 unverändert war, ist jetzt auf 2026 datiert.
Während ich nach anfälligen Implementierungen suchte, fand ich auch einen "Bug" in llvm, also habe ich das auch etwas ausgeführt.
- enriquto
Das könnte sehr gut der epischste Beitrag in der HN-Geschichte sein.
EDIT: Ich erinnere mich gern an Algorithmus D... eine meiner ersten Programmiererfahrungen in den 90ern war der Versuch, Knuths Arithmetik-Algorithmen für Addition, Subtraktion usw. in 8086-asm zu implementieren. Ich habe sie bis zur langen Multiplikation richtig hinbekommen (das war eine enorme Anstrengung). Algorithmus D war zu gewaltig, um es überhaupt zu wagen. Ich bin sehr glücklich zu sehen, dass Leute im Jahr 2026 diese Algorithmen genau untersuchen.
- WalterBright
Toller Fund und gut geschrieben. Dieses Jahr, wenn ich mich richtig erinnere, haben über 40 Leute den Scheck bekommen, ~1000 haben ein Konto bei der Bank. Ich habe meinen dieses Jahr bekommen. Eine Übung, die ich seit 2012 alle paar Jahre wiederhole, um eine neue Programmiersprache oder einen neuen Ansatz zu lernen, hatte ein neueres Update, das dazu führte, dass sie zwei Off-by-one-Fehler hatte. Ich hatte dieses Jahr extra Zeit, also ging ich zum Anfang des Kapitels, um ein offenes Problem zu versuchen, und in den Vorbereitungen gab es einen weiteren Off-by-two-Fehler. Ich war ziemlich überrascht.
Das hat mich wirklich schätzen lassen, wie unwahrscheinlich es ist, einen Fehler zu finden. Es fühlt sich an, als wäre es geplant gewesen, dass ich ihn finde. Genau wie der Autor Kryptographie studierte und dann beschloss, ein paar Übungen zu machen, um seine Fähigkeiten zu verbessern, eine unwahrscheinliche Reise zu einem Scheck.