Home → Magazine Archive → January 1971 (Vol. 14, No. 1) → Minit algorithm for linear programming → Abstract

Minit algorithm for linear programming

By Å. Kolm, T. Dahlstrand

Communications of the ACM, Vol. 14 No. 1, Page 50

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