クヌースの『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実装における潜在的な問題までを詳述する。
失敗は、数十年間正しいとされてきたアルゴリズムDの反例を私にもたらし、それとともに、私の名を冠したアルゴリズムの正当性に関する定理をもたらした。
HNでの議論
50- nk_kolja
クヌースの『The Art of Computer Programming』の長除法アルゴリズムDにバグを見つけました。これはHNで何度か議論されました（https://news.ycombinator.com/item?id=26562819）し、他のウェブサイトでも取り上げられました。
クヌースに手紙を送ったところ、小切手と注釈付きの返信を受け取りました。1969年から変わっていなかった定理Bは、現在2026年付けとなっています。
脆弱な実装を探しているうちに、llvmにも「バグ」を見つけたので、それについても少し詳しく書きました。
- WalterBright
1980年代、DIV命令が存在する前のことですが、私は整数除算を実装しました。
小学3年生で教わったのと同じ長除法を使いましたが、10進数ではなく2進数で、シフトと減算を用いました。
これはまた、x87チップを持っていない人向けのFDIV（浮動小数点除算）の実装の基礎でもありました。
誰もそのバグを報告したことはありませんでした。
- enriquto
これはおそらくHN史上最も壮大な投稿でしょう。
編集：アルゴリズムDを懐かしく思い出します。90年代の私の最初のプログラミング体験の一つは、8086アセンブリでクヌースの加算や減算などの算術アルゴリズムを実装しようとすることでした。長い乗算までは正しくできました（それは大変な努力でした）。アルゴリズムDはあまりにも手ごわくて、挑戦しようとも思いませんでした。2026年に人々がこれらのアルゴリズムを注意深く見ているのを見て、とても嬉しく思います。
- nickdrozd
おめでとうございます！報酬が重要度に基づいていないのが面白いですね。エラーには0x$1.00、提案には0x$0.20と、何であっても決まっています。個人的には、銀行に0x$4.40あり、著者の0x$1.00より多いですが、私の4つのエラーと2つの提案のどれも、これほど重要ではありませんでした。本に名前が載るのはかなりクールですけどね！
このバグはアルゴリズムの英語の説明にのみ存在するのですよね？MIXやMMIXの実装にはバグはないのですか？
- ozten
十分なトークンがあれば、すべてのバグは浅いものになる。