Long Division: An Example of Dynamic Programming

Abstract

The familiar method of long division provides an excellent example of dynamic programming. A five-step division problem is solved by both methods. The five steps make up a five-stage dynamic program. The first step involves selecting a trial divisor, a decision, which minimizes the remainder after even division. This remainder is the state carried over to the next stage. Division proceeds recursively until the final stage is reached. Thus as is typical of the dynamic programming technique, one problem in five unknowns (the five-digit quotient) replaces the original problem by five simpler problems each of one unknown.