Communications of the ACM

There is a new standard Fortran. The official title is “American National Standard Programming Language Fortran, X3.9-1978,” but it is more commonly referred to as “Fortran 77,” since its development was completed in 1977. It replaces the Fortran ...

Approximate queueing models for internal parallel processing by individual programs in a multiprogrammed system are developed in this paper. The solution technique is developed by network decomposition. The models are formulated in terms of CPU:I/O and ...

When sequential file structures must be used and binary searching is not feasible, jump searching becomes an appealing alternative. This paper explores variants of the classic jump searching scheme where the optimum jump size is the square root of the ...

This paper investigates the problem of optimal histogram matching using monotone gray level transformation, which always assigns all picture points of a given gray level i to another gray level T(i) such that if i ≥ j, then T(i) ≥ T(j). The objective is ...

It is possible to use a small counter to keep approximate counts of large numbers. The resulting expected error can be rather precisely controlled. An example is given in which 8-bit counters (bytes) are used to keep track of as many as 130,000 events ...

Solutions to the Dutch National Flag Problem have been given by Dijkstra [1] and Meyer [3]. Dijkstra starts with a simple program and arrives at an improved program by refinement. Both of the algorithms given by Dijkstra are shown to have an expected ...

This paper is a practical study of how to implement the Quicksort sorting algorithm and its best variants on real computers, including how to apply various code optimization techniques. A detailed implementation combining the most effective improvements ...

Scatter tables for open addressing benefit from recursive entry displacements, cutoffs for unsuccessful searches, and auxiliary cost functions. Compared with conventional methods, the new techniques provide substantially improved tables that resemble ...

In a two-level computer storage hierarchy, miss ratio measurements are often made from a “cold start”, that is, made with the first-level store initially empty. For large capacities the effect on the measured miss ratio of the misses incurred while ...

Following publication of our paper [2], questions arose with respect to the superiority of the TL structure over heaps,¹ particularly in the face of the remarks of Gonnet [3], concerning the use of heaps for the physical realization of the simulation ...