The article presents a sample derivation and proof for Knuth's program (D. Knuth, 1990) that translates a binary fraction to a decimal fraction. The main technique used is the partition-and-recur approach, that is, partitioning the problem, deriving an algorithm represented by recurrences, and finally transforming the algorithm to a program in a straightforward manner. Practice with this example has given us more confidence that partition-and-recur is a practicable approach for derivation and proof of general algorithms and programs.
['Jinyun Xue', 'Ruth Davis']
A simple program whose derivation and proof is also