--- title: Novak Kaluđerović - Kolja | daily.dev description: A deep dive into Knuth's Algorithm D long division algorithm from The Art of Computer Programming, describing how implementing multiprecision division for a... canonical: https://daily.dev/posts/novak-kalu-erovi---kolja-4ccsvuutc twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: Novak Kaluđerović - Kolja | daily.dev og:description: A deep dive into Knuth's Algorithm D long division algorithm from The Art of Computer Programming, describing how implementing multiprecision division for a... og:url: https://daily.dev/posts/novak-kalu-erovi---kolja-4ccsvuutc og:image: https://api.daily.dev/og/posts/4CCSVuUtC.png og:image:alt: Novak Kaluđerović - Kolja og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # Novak Kaluđerović - Kolja **[Lobsters](https://daily.dev/sources/lobsters)** · 30 min read · 0 upvotes · 0 comments ## Summary A deep dive into Knuth's Algorithm D long division algorithm from The Art of Computer Programming, describing how implementing multiprecision division for a cryptography library led to discovering a decades-old bug in Theorem B's proof. The bug arises only in odd machine word bases and was masked in Knuth's original MIX implementation due to a different division instruction semantics than modern hardware (ARM vs x86-style division). The author also found a related discrepancy (not quite a bug) in LLVM's APInt.cpp implementation stemming from an old typo in TAOCP that was corrected in 2005 but never updated in LLVM's code comments, and submitted a non-functional PR to fix it. Knuth acknowledged the correction, awarded a hexadecimal reward check, and the fix will appear in the 53rd printing of Volume II with errata published 2026-06-09. The post also covers background on long division algorithms (reducing long to medium to short division), normalization, and previews faster division techniques like Burnikel-Ziegler recursive division and division-by-constant methods. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### What was the bug found in Knuth's Algorithm D for long division in The Art of Computer Programming? Theorem B's bound on the trial quotient overshoot in Algorithm D's step D3 was not tight enough for odd machine word bases; the smallest counterexample uses base 3, with dividend u=(1,2,0,0)base3=45 and divisor v=(1,2,1)base3=16, where the correct quotient is 2 but the algorithm computes 5. The correction was filed 2026-05-14, with errata published 2026-06-09, appearing in the 53rd printing of TAOCP Volume II. _Track subtle algorithm corrections like Knuth's Algorithm D fix as they land, on daily.dev._ ### Why doesn't Knuth's Algorithm D division bug affect modern hardware like x86 or ARM? The bug only manifests when the machine word base is odd, and modern architectures use base 2^32 or 2^64, which are always even, so the degenerate overshoot case in Theorem B never triggers in practice. Even Knuth's original MIX machine used a generic base b, but MMIX fixed it at 2^64, so the flaw stayed dormant across implementations for decades. _Understanding edge cases like this helps developers judging algorithm correctness on daily.dev before shipping._ ### What discrepancy exists between LLVM's APInt.cpp Knuth division implementation and the corrected TAOCP text? LLVM's APInt.cpp checks qp == b in step D3, matching a typo present in TAOCP Volume II that was corrected to qp >= b in 2005; LLVM's comment and code still reflect the pre-2005 text. Because b is even, qp can only exceed b by exactly 1, so the == check happens to still produce correct results, though the correctness isn't proven anywhere in the book or the code. _Developers auditing widely-used libraries like LLVM's APInt can compare notes on subtle correctness gaps via daily.dev._ ## Similar posts on daily.dev - [research\!rsc: Pulling a New Proof from Knuth’s Fixed-Point Printer](https://daily.dev/posts/research-rsc-pulling-a-new-proof-from-knuth-s-fixed-point-printer-d6loesfme) · research\!rsc · 0 upvotes · 0 comments - [\[2604.07902\] Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets](https://daily.dev/posts/2604-07902-optimization-of-32-bit-unsigned-division-by-constants-on-64-bit-targets-uy09tvu32) · Hacker News · 0 upvotes · 0 comments --- Tags: [#general-programming](https://daily.dev/tags/general-programming), [#algorithms](https://daily.dev/tags/algorithms), [#cryptography](https://daily.dev/tags/cryptography) [View this post on daily.dev](https://daily.dev/posts/novak-kalu-erovi---kolja-4ccsvuutc) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"Novak Kaluđerović - Kolja","url":"https://daily.dev/posts/novak-kalu-erovi---kolja-4ccsvuutc","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/novak-kalu-erovi---kolja-4ccsvuutc"},"datePublished":"2026-08-15T00:51:13.237Z","dateModified":"2026-08-15T00:51:44.156Z","description":"A deep dive into Knuth's Algorithm D long division algorithm from The Art of Computer Programming, describing how implementing multiprecision division for a...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/343a1b49e25ca13d2d5185aeff356db0?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/343a1b49e25ca13d2d5185aeff356db0?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Lobsters","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Lobsters","logo":"https://media.daily.dev/image/upload/s--tl8v_Fku--/f_auto,t_logo/v1698841318/logos/lobste.jpg","url":"https://daily.dev/sources/lobsters"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/novak-kalu-erovi---kolja-4ccsvuutc","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"general-programming,algorithms,cryptography","timeRequired":"PT30M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Lobsters","item":"https://daily.dev/sources/lobsters"},{"@type":"ListItem","position":3,"name":"Novak Kaluđerović - Kolja"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/novak-kalu-erovi---kolja-4ccsvuutc#faq","mainEntity":[{"@type":"Question","name":"What was the bug found in Knuth's Algorithm D for long division in The Art of Computer Programming?","acceptedAnswer":{"@type":"Answer","text":"Theorem B's bound on the trial quotient overshoot in Algorithm D's step D3 was not tight enough for odd machine word bases; the smallest counterexample uses base 3, with dividend u=(1,2,0,0)base3=45 and divisor v=(1,2,1)base3=16, where the correct quotient is 2 but the algorithm computes 5. The correction was filed 2026-05-14, with errata published 2026-06-09, appearing in the 53rd printing of TAOCP Volume II. Track subtle algorithm corrections like Knuth's Algorithm D fix as they land, on daily.dev."}},{"@type":"Question","name":"Why doesn't Knuth's Algorithm D division bug affect modern hardware like x86 or ARM?","acceptedAnswer":{"@type":"Answer","text":"The bug only manifests when the machine word base is odd, and modern architectures use base 2^32 or 2^64, which are always even, so the degenerate overshoot case in Theorem B never triggers in practice. Even Knuth's original MIX machine used a generic base b, but MMIX fixed it at 2^64, so the flaw stayed dormant across implementations for decades. Understanding edge cases like this helps developers judging algorithm correctness on daily.dev before shipping."}},{"@type":"Question","name":"What discrepancy exists between LLVM's APInt.cpp Knuth division implementation and the corrected TAOCP text?","acceptedAnswer":{"@type":"Answer","text":"LLVM's APInt.cpp checks qp == b in step D3, matching a typo present in TAOCP Volume II that was corrected to qp >= b in 2005; LLVM's comment and code still reflect the pre-2005 text. Because b is even, qp can only exceed b by exactly 1, so the == check happens to still produce correct results, though the correctness isn't proven anywhere in the book or the code. Developers auditing widely-used libraries like LLVM's APInt can compare notes on subtle correctness gaps via daily.dev."}}]} ```