Optimization of the raster-scan circle-drawing algorithm based on predicate transformers

An approach to the optimization of raster-scan circle-drawing algorithms is presented. The approach is based on the program transformation theory, which is a subset of Dijkstra's weakest precondition calculus. In this way, care of the correctness of the algorithm is incorporated in the optimization process. The authors propose that a designer and an implementor define the problem together, translating quality requirements and technology constraints into algorithm requirements. Then the standard solution should be explained and optimized in terms of weakest precondition. Thanks to the approach with an invariant and a bound function, it is possible to separate aspects concerning optimization and correctness. The method is illustrated by the optimization of an integer case circle algorithm.