TECH Signal 400
Decades-old bug found in Knuth's Algorithm D, "bug" in LLVM implementation
↗
An author implementing Knuth's Algorithm D discovered a decades-old bug in the algorithm's correctness proof and a related "bug" in LLVM's implementation.
Algorithm D is the standard reference for multiprecision long division, so a bug in its correctness proof affects foundational assumptions in cryptographic and systems programming. The LLVM implementation bug means production compilers may currently handle this specific division case incorrectly.
Written by elseif from the cluster below · every claim links back to a sourceThe three things worth knowing
A counterexample was found to Theorem B, which proves the correctness of Knuth's Algorithm D.
The bug in Algorithm D had passed as correct for decades before this discovery.
A related "bug" was found in LLVM's implementation of this long division algorithm.
THE CLUSTER