Search
Join ACM

February 1969 - Vol. 12 No. 2

February 1969 issue cover image

Features

News Feb 1 1969

President’s letter to the ACM membership: The journal

A great deal of concern has been expressed to me and to members of the Executive Committee and the Editorial Board about the new status of the Journal. Obviously, the concern is not over the $3 needed to subscribe to the Journal in the future. Those who are worried about the change, which substituted the new Computing Surveys for the Journal, see it as one more step in a process of change within ACM that has been going on for some time. They argue that the Association began as an academic, scientific, professional organization concerned with the more formal mathematical and scientific aspects of information processing, and their concern that the organization has changed character is quite legitimate.
Research and Advances Feb 1 1969

CODAS: a data display system

CODAS, a Customer Oriented Data System, is a user-oriented data retrieval and display system. The command language of the system provides the user with an easy means for specifying data retrieval and display requests. Data is displayed as tables and graphs produced in a format ready for publication. In this paper the statements of the request language and the general system design are described.
, , and
Computing Applications
Research and Advances Feb 1 1969

Variable length tree structures having minimum average search time

Sussenguth suggests in a paper (1963) that a file should be organized as a doubly-chained tree structure if it is necessary both to search and to update frequently. Such a structure provides a compromise between the fast search/slow update characteristics of binary searching and the slow search/fast update characteristics of serial searching. His method, however, contains the limiting restriction that all terminal nodes lie on the same level of the tree. This paper considers the effect of relaxing this restriction. First, trees which have the property that a priori the filial set of each node is well defined are studied. It is proved that coding the nodes within each filial set with respect to the number of terminal nodes reachable from each is necessary and sufficient to guarantee minimum average search time. Then the more general case (that is, where the entire structure of the tree is changeable) is treated. A procedure is developed for constructing a tree with a minimum average search time. A simple closed expression for this minimum average search time is obtained as a function of the number of terminal nodes. The storage capacity required to implement the doubly-chained tree structure on a digital computer is also determined. Finally, the total cost of the structure, using Sussenguth's cost criterion, is computed. It is shown that significant improvements in both the average search time and the total cost can be obtained by relaxing Sussenguth's restriction that all terminal nodes lie on the same level of the tree.
Artificial Intelligence and Machine Learning
Research and Advances Feb 1 1969

On arithmetic expressions and trees

A description is given of how a tree representing the evaluation of an arithmetic expression can be drawn in such a way that the number of accumulators needed for the computation can be represented in a straightforward manner. This representation reduces the choice of the best order of computation to a specific problem under the theory of graphs. An algorithm to solve this problem is presented.
Artificial Intelligence and Machine Learning
Research and Advances Feb 1 1969

Coding the Lehmer pseudo-random number generator

An algorithm and coding technique is presented for quick evaluation of the Lehmer pseudo-random number generator modulo 2 ** 31 - 1, a prime Mersenne number which produces 2 ** 31 - 2 numbers, on a p-bit (greater than 31) computer. The computation method is extendible to limited problems in modular arithmetic. Prime factorization for 2 ** 61 - 2 and a primitive root for 2 ** 61 - 1, the next largest prime Mersenne number, are given for possible construction of a pseudo-random number generator of increased cycle length.
, , and
Computing Applications
Research and Advances Feb 1 1969

The logarithmic error and Newton’s method for the square root

The problem of obtaining optimal starting values for the calculation of the square root using Newton's method is considered. It has been pointed out elsewhere that if relative error is used as the measure of goodness of fit, optimal results are not obtained when the inital approximation is a best fit. It is shown here that if, instead, the so-called logarithmic error is used, then a best initial fit is optimal for both types of error. Moreover, use of the logarithmic error appears to simplify the problem of determining the optimal initial approximation.
and
Systems and Networking
Research and Advances Feb 1 1969

Interval arithmetic determinant evaluation and its use in testing for a Chebyshev system

Two recent papers, one by Hansen and one by Hansen and R. R. Smith, have shown how Interval Arithmetic (I.A.) can be used effectively to bound errors in matrix computations. In the present paper a method proposed by Hansen and R. R. Smith is compared with straightforward use of I.A. in determinant evaluation. Computational results show the accuracy and running times that can be expected when using I.A. for determinant evaluation. An application using I.A. determinants in a program to test a set of functions to see if they form a Chebyshev system is then presented.
Research and Advances Feb 1 1969

Extremely portable random number generator

Extremely portable subroutines are sometimes needed for which moderate quality and efficiency suffice. Typically, this occurs for library functions (like random number generation and incore sorting) which are not entirely universal or are not used in a standardized way. The literature on random number generators does not seem to contain an algorithm that meets requirements of this sort. An extremely portable 8-line FORTRAN program is provided which is based on an important paper by Coveyou and MacPherson (1967). Using their methods, Fourier analysis is applied to the probability function for the consecutive n-tuples provided by our generator (with n less than or equal to 4). While the small modulus which must be used to maintain portability prevents the quality of the generator from being high, the generator compares well with the bounds established in the above mentioned paper.
Computing Applications
Research and Advances Feb 1 1969

Images from computers and microfilm plotters

Digital computers are widely used for the processing of information and data of all kinds, including the pictorial information contained in photographs and other graphical representations. Efficient conversion facilities for putting graphical information into the computer and retrieving it in graphical form are therefore much needed. One of the most commonly employed devices for obtaining permanent graphical output from digital computers is the microfilm plotter. Regrettably, present models have no provision for producing images with a continuous gray scale or “halftones.” In this note several programming techniques are described for obtaining halftone pictures from a microfilm plotter under the control of a digital computer. Illustrative examples of several methods are given.
Artificial Intelligence and Machine Learning
Research and Advances Feb 1 1969

Exclusive simulation of activity in digital networks

A technique for simulating the detailed logic networks of large and active digital systems is described. Essential objectives sought are improved ease and economy in model generation, economy in execution time and space, and a facility for handling simultaneous activities. The main results obtained are a clear and useful separation of structural and behavioral model description, a reduction of manual tasks in converting Boolean logic into a structural model, the elimination of manual processes in achieving exclusive simulation of activity, an event-scheduling technique which does not deteriorate in economy as the event queue grows in length, and a simulation procedure which deals effectively with any mixture of serial and simultaneous activities. The passage of time is simulated in a precise, quantitative fashion, and systems to be simulated may be combinations of synchronous and asynchronous logic. Certain aspects of the techniques described may be used for the simulation of network structures other than digital networks.
Architecture and Hardware

Recent Issues

Explore the Issue Archive
  1. November 2024 CACM cover
    November 2024 Vol. 67 No. 11
  2. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  3. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  4. August 2024 CACM cover
    August 2024 Vol. 67 No. 8