Knuth经典算法竟藏数十年Bug
A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)
在实现Knuth《计算机程序设计艺术》中的Algorithm D长除法时，我意外发现了一个隐藏数十年的逻辑漏洞。原本看似无懈可击的Theorem B证明过程显得异常曲折，促使我尝试独立推导，最终找到了反例并修正了算法。这一发现不仅让我在TAOCP勘误表中留下了自己的名字，还顺带揭示了llvm实现中的一个潜在问题。本文将带你回顾长除法的原理，剖析这个Bug为何能潜伏如此之久，以及它是否可被利用。
然而，这次失败却给了我一个反例，推翻了Algorithm D算法，该算法被误认为正确已长达数十年。
- nk_kolja
我在 Knuth 的《计算机程序设计艺术》中发现了一个长除法算法（Algorithm D）的 Bug。这个问题之前在 HN 上讨论过几次 https://news.ycombinator.com/item?id=26562819，在其他网站上也有提及。
我给 Knuth 写了一封信，收到了一张支票和一份附有批注的回复。更新后的定理 B（自 1969 年以来一直未变）现在的日期已改为 2026 年。
在搜索存在漏洞的实现时，我还发现了一个 llvm 中的“Bug”，因此我也顺便对此做了一些补充说明。
- globular-toast
> “我特别高兴能做出这个修正，因为我觉得《计算机程序设计艺术》第二卷的读者们，看算法 4.3.1 D 的次数比看任何其他算法都多！”
如果你看看我手头第二卷这本书的书口边缘，会看到一条明显脏兮兮的痕迹。翻到那一页，确实就是算法 D！
我至少实现过几次多精度算术运算。我很想翻出那个搁置了十多年没碰过的旧项目，把修正加进去……
- ginko
这个页面在 Firefox 上的排版看起来非常破碎，行与行之间的间距大得离谱。不过在 Chromium 上渲染倒是正常的。