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.