Sign In

Communications of the ACM

Table of Contents


Fortran 77

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 …

Models for parallel processing within programs: application to CPU: I/O and I/O: I/O overlap

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 …

Jump searching: a fast sequential search technique

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 …

Optimal histogram matching by monotone gray level transformation

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 ij, then T …

Counting large numbers of events in small registers

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 …

An analysis of algorithms for the Dutch National Flag Problem

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 areN …

Implementing Quicksort programs

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 …

Packed scatter tables

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 …

Cold-start vs. warm-start miss ratios

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 …

A comparison of heaps and the TL structure for the simulation event set

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

ACM forum