Pulling a New Proof from Knuth's Fixed-Point Printer

4 months ago

Donald Knuth's 1989 paper 'A Simple Program Whose Proof Isn’t' discusses converting 16-bit fixed-point binary fractions to decimal fractions.
The post presents a new proof for Knuth's program P2, starting with a simpler program and transforming it step-by-step into P2.
The problem involves finding the shortest accurate, correctly rounded decimal for a given 16-bit binary fraction.
The post explores alternative solutions, including a simpler iterative program and a direct solution inspired by the Schubfach algorithm.
A historical perspective is provided, linking Knuth's problem to earlier work by D. Taranto and later by Steele and White.
The conclusion reflects on how programming tools influence program design and proof complexity, advocating for simpler proofs with modern tools.

Hasty Briefsbeta