Name
Abstract | ||
|---|---|---|
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 A ≥ B (real A, B) will usually be implemented as A - B ≥ 0, which can fail due to floating point overflow or underflow. |
Year | DOI | Venue |
|---|---|---|
1971 | 10.1145/362452.362512 | Commun. ACM |
Keywords | Field | DocType |
in-place sorting,finite precision,metatheory,floating point overflow,array m,real a,london state,common confusion,certification,boolean expression,proof of algorithms,ralph l. london,array element,sorting,debugging,algorithm treesort,in place sorting | Arithmetic underflow,Programming language,Floating point,Computer science,In-place algorithm,Algorithm,Sorting,Theoretical computer science,Certification,Code (cryptography),Boolean expression,Debugging | Journal |
Volume | Issue | ISSN |
14 | 1 | 0001-0782 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| K. A. Redish | 1 | 19 | 8.76 |