A long division story

I was working on an algorithm, Algorithm D, which is based on the long division method from Donald Knuth's "The Art of Computer Programming." I encountered an issue with Theorem B, which seemed unnatural and convoluted in its proof. While trying to prove the theorem myself, I stumbled upon a counterexample that revealed a flaw in Algorithm D. This led to the discovery of a new theorem regarding the correctness of the algorithm, all under the name of the person who found it.

I decided to build a library for arithmetic over prime fields as a small project to prepare for an interview. The project involved creating fixed-size multiprecision integers, arithmetic operations, and field operations, aiming to avoid division at all costs. Multiplication is simple and can be considered an axiom of natural numbers, while division is more complex and not defined everywhere, especially when dividing by zero.

Division with remainder is a more complicated operation that returns both the quotient and the remainder. However, the choice of remainder definition and size function can vary, resulting in different division algorithms.

After implementing long division using Knuth's Algorithm 4.3.1D from "The Art of Computer Programming," I found a bug in the implementation of this algorithm in LLVM. The bug was then expanded upon in the process of writing this blog post.