クヌースの『TAOCP』に数十年隠れていたバグを発見、定理として採用される

A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D)

クヌースの『The Art of Computer Programming』第2巻に掲載されている除算アルゴリズムD（Algorithm 4.3.1D）に、数十年間見過ごされてきたバグを発見した筆者が、その発見に至る経緯と詳細を解説。定理Bの証明に違和感を覚え、独自に証明を試みた結果、反例を発見。この発見はTAOCPの正誤表に「定理B（N. Kaluđerović, 2026）」として追加された。本記事では、多倍長整数の除算アルゴリズムの基礎から、バグの内容、長期間発見されなかった理由、LLVM実装における潜在的な問題までを詳述する。