Home → Magazine Archive → January 1971 (Vol. 14, No. 1) → Comment on London's certification of algorithms 245 → Abstract

Comment on London's certification of algorithms 245

By K. A. Redish

Communications of the ACM, Vol. 14 No. 1, Pages 50-51

Save PDF
In his Certification of Algorithm 245 [1], Ralph L. London exhibits a common confusion between an algorithm, its representation, and its implementation on a processor—a code. In the present state of the art we can attempt, in general, to prove an algorithm and to test a code. For example, London states that “… the algorithm TREESORT 3 [2] is proved to perform properly its claimed task of sorting an array M[1:n] into ascending order.” While this is true of the algorithm, it is not true of the code unless we place restrictions on the array elements. The trouble arises in this example from the finite precision of processors; the Boolean expression AB (real A, B) will usually be implemented as A - B ≥ 0, which can fail due to floating point overflow or underflow.

The full text of this article is premium content


No entries found